Log out Go to App
Go to App

Learning Materials

Features

Discover

Chapter 4: Q8E (page 132)

Professor F. Lake suggests the following algorithm for finding the shortest path from node to node t in a directed graph with some negative edges: add a large constant to each edge weight so that all the weights become positive, then run Dijkstra’s algorithm starting at node s , and return the shortest path found to node t .

Is this a valid method? Either prove that it works correctly, or give a counterexample.

Short Answer

Expert verified

Yes, this is a valid method.

Step by step solution

01

Explain Dijkstra’s algorithm

Dijkstra’s shortest-path algorithm marks all the distance of all the vertices as infinity. As the algorithm runs, when each vertex is visited, the distance between the vertices is calculated and the lowest distance values are updated at each iteration.

02

Is the given method is valid.

Consider the directed graph that has the nodes s,p,q,t , The shortest path from node s to node t has to be calculated. Consider that some of the nodes from s to t have negative weight edges that is -2. Add the larger constant weight 5 to all the edges that makes the edge values as 3, that makes all the negative edges to positive edges.

Run Dijkstra’s algorithm and the shortest path will be returned.

Therefore, the given method is valid and it is proved

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

Give an O|V|2algorithm for the following task.

Input:An undirected graph G=(V,E); edge lengths Ie>0;an edge e∈E.

Output:The length of the shortest cycle containing edge e

There is a network of roads G=(V,E) connecting a set of cities . Each road in E has an associated length Ie. There is a proposal to add one new road to this network, and there is a list E' of pairs of cities between which the new road can be built. Each such potential road localid="1659075853079" e'∈E' has an associated length. As a designer for the public works department you are asked to determine the road localid="1659075866764" e'∈E'whose addition to the existing network G would result in the maximum decrease in the driving distance between two fixed cities s and t in the network. Give an efficient algorithm for solving this problem.

Give an algorithm that takes as input a directed graph with positive edge lengths, and returns the length of the shortest cycle in the graph (if the graph is acyclic, it should say so). Your algorithm should take time at most O|V3|.

Consider a directed graph in which the only negative edges are those that leaves; all other edges are positive. Can Dijkstra's algorithm, started at s, fail on such a graph? Prove your answer.

Shortest paths are not always unique: sometimes there are two or more different paths with the minimum possible length. Show how to solve the following problem in O((|V|+|E|)log|V|)time.

Input:An undirected graph G=(V,E);edge lengths le>0; starting vertex s∈V.

Output:A Boolean array for each node u , the entry usp[u]should be true if and only if there is a unique shortest path s to u (Note:usp[s]=true)
See all solutions

Recommended explanations on Computer Science Textbooks

Computer Network

Read Explanation

Game Design in Computer Science

Read Explanation

Databases

Read Explanation

Big Data

Read Explanation

Algorithms in Computer Science

Read Explanation

Data Representation in Computer Science

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free