Menu
In "Introduction to algorithms, 3rd edition" exercise 24.3-5 wants an example that this is wrong (not always true). Is that possible? In my mind this is impossible because every edge is relaxed at a time when the path to the current vertice is already decided.
Word for word:
Professor N. claims to have a proof of correctness of Dijkstra's algorithm. He claims that Dijkstra's algorithm relaxes the edges of every shortest path in the graph in the order in which they appear on the path, and therefore the path-relaxation property applies to every vertex reachable from the source. Show the professor is mistaken by constructing a directed graph for which Dijkstra's algorithm could relax the edges of a shortest path out of order.
369
Relaxing an edge, (a concept you can find in other shortest-path algorithms as well) is trying to lower the cost of getting to a vertex by using another vertex. where est(S,a) is the current estimate of the distance, and dist(a,b) is the distance between two vertices that are neighbors in the graph.
(i) T F [2 points] Dijkstra's shortest-path algorithm may relax an edge more than once in a graph with a cycle.
Dijkstra's Algorithm finds the shortest path between a given node (which is called the "source node") and all other nodes in a graph. This algorithm uses the weights of the edges to find the path that minimizes the total distance (weight) between the source node and all other nodes.
The single - source shortest paths are based on a technique known as relaxation, a method that repeatedly decreases an upper bound on the actual shortest path weight of each vertex until the upper bound equivalent the shortest - path weight.
Consider the following directed graph :(A,B),(A,C),(B,D),(C,D), (D,E)with edge weights w(A,B)=1,w(A,C)=1,w(B,D)=0,w(C,D)=0, w(D,E)=1.The source vertex is A. A possible permutation of edges relaxed in the Dijkstra’s algorithm is (A,B), (A,C), (B,D), (D,E), (C,D). Besides, A.d=0, B.d=1, C.d=1, D.d=1, E.d=2 after performing the Dijkstra’s algorithm. There are two shortest paths from A to E, one is ABDE, and the other is ACDE. The contradiction is to the second path, edge (C,D) should be always relaxed before (D,E).
68
I think the key phrase in the wording is that dijkstra's algorithm "relaxes the edges of every shortest path in the graph..."
That alone is a lie if there are multiple shortest paths of the same cost.
Consider this graph: A -> B, A -> C, B -> D, C -> D. Source is A and Destination is D. Every edge weight is 1. There are two paths from A to D, one through B and one through C. However one edge B->D or C->D never gets relaxed.
Still not convinced because dijkstra terminates before evaluating the other edge into D? Toss in an extra edge D->E and set the Destination to E. The path from A->D through B is the same cost as A->D through C and they are both cheaper than the cost from A->E. However you will never relax the second edge into D since the algorithm only relaxes edges to vertices that it does not already know the shortest path to.
41
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
