does anyone know how to do this one? Suppose that we are given a weighted, direc
ID: 3610155 • Letter: D
Question
does anyone know how to do this one? Suppose that we are given a weighted, directed graph G=(V,E)in which edges that leave the source vertix s may havenegative weightes, all other edge weights are nonnegative, andthere are no negative-weight cycles. Argue that Dijkstra'salgrorithm correctly finds the shortest paths from s inthis graph. Dijkstra's Algorith does anyone know how to do this one? Suppose that we are given a weighted, directed graph G=(V,E)in which edges that leave the source vertix s may havenegative weightes, all other edge weights are nonnegative, andthere are no negative-weight cycles. Argue that Dijkstra'salgrorithm correctly finds the shortest paths from s inthis graph. Dijkstra's Algorith Suppose that we are given a weighted, directed graph G=(V,E)in which edges that leave the source vertix s may havenegative weightes, all other edge weights are nonnegative, andthere are no negative-weight cycles. Argue that Dijkstra'salgrorithm correctly finds the shortest paths from s inthis graph. Dijkstra's AlgorithExplanation / Answer
Dijkstra’s Algorithm:
Input: Graph G, with each edge e having a length len(e), and astart node s.
Initialize: tree = {s}, no edges. Label s as having distance 0to itself.
Invariant: nodes in the tree are labeled with the correctdistance to s.
Repeat:
1. For each neighbor x of the tree, compute an (over)-estimateof its distance to s:
In other words, by our invariant, this is the length ofthe shortest path to x whose only edge not in the tree is the verylast edge.
2. Insert the node x of minimum distance into tree, connectingit via the argmin (the edge e used to get distance(x) in theexpression
Dijkstra’s algorithm correctly produces a shortest pathtree from start node s. Specifically, even if some of distances instep 1 are too large, the minimum one is correct.
Proof: Say x is the neighbor of the tree of smallestdistance(x). Let P denote the true shortest path from s to x,choosing the one with the fewest non-tree edges if there are ties.What we need to argue is that the last edge in P must come directlyfrom the tree. Let’s argue this by contradiction. Supposeinstead the first non-tree vertex in P is some node y != x. Then,the length of P must be at least distance(y), and by definition,distance(x) is smaller (or at least as small if there is a tie).This contradicts the definition of P.
Dijkstra's algorithm is very fast, but it suffers from itsinability to deal with negative edge weights. Having negative edgesin a graph may also introduce negative weight cycles that make usrethink the very definition of "shortest path". Fortunately, thereis an algorithm that is more tolerant to having negative edges– the BellmanFord algorithm.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.