2004 SDU,Lecture 8 Single-Source Shortest Paths Problems,Related Notions and Variants of Shortest Paths Problems Properties of Shortest Paths and Relaxation The Bellman-Ford Algorithm Single-Source Shortest Paths in Directed Acyclic Graphs, 2008 SDU 2,Shortest PathsNotions Related,Given a weighted, directed graph G = (V, E; W), the weight of path p = is the sum of the weights of its constituent edges, that is, Define the shortest-path weight from u to v by A shortest path from vertex u to v is any path p with weight w(p) = (u, v)., 2008 SDU 3,Single-source shortest path problem,Input: A weighted directed graph G=(V, E, w), and a source vertex s. Output: Shortest-path weight from s to each vertex v in V, and a shortest path from s to each vertex v in V if v is reachable from s., 2008 SDU 4,Notes to Shortest-Paths,For single-source shortest-paths problem Negative-weight edge and Negative-weight cycle reachable from s Cycles Can a shortest path contain a cycle?, 2008 SDU 5,Property of Shortest Paths,Lemma 24.1 (Subpaths of shortest paths are shortest paths) Given a weighted, directed graph G = (V, E; W), let p = be a shortest path from vertex v1 to vertex vk and, for any i and j such that 1 i j k, let pij = be the subpath of p from vertex vi to vertex vj. Then, pij is a shortest path from vi to vj. Why? Can you give a proof?, 2008 SDU 6,Relaxation,Relaxation: Kingsoft 2003, American Traditional Dictionary: A method of solving equations in which the errors resulting from an initial approximation are reduced by succeeding approximations until all errors are within specified limits. In our shortest-paths problem, we maintain an attribute dv, which is a shortest-path estimate from source s to v. The term RELAXATION is used here for an operation that tightens dv, or the difference of dv and (s, v)., 2008 SDU 7,Relaxation-Initialization,The initial estimate of (s, v) can be given by:, 2008 SDU 8,Relaxation Process,Relaxing an edge (u, v) consists: Testing whether we can improve the shortest path to v found so far by going through u, and if so, Updating dv and v. A relaxation step may either decrease the value of the shortest-path estimate dv and update vs predecessor v, or cause no change., 2008 SDU 9,A Relaxation Step, 2008 SDU 10,Properties of Shortest Paths and Relaxation,Assume there is no negative cycle reachable from s Triangle inequality (Lemma 24.10) For any edge (u, v) E, we have (s, v) (s, u) + w(u, v) Upper-bound property (Lemma 24.11) We always have dv (s, v) for all vertices v V, and once dv achieves the value (s, v), it never changes. No-path property (Lemma 24.12) If there is no path from s to v, then we always have dv = (s, v) = ., 2008 SDU 11,Properties of Shortest Paths and Relaxation,Convergence property (Lemma 24.14) If s u v is a shortest path from s to v in G, and if du = (s, u) at any time prior to relaxing edge (u, v), then dv = (s, v) at all times afterward. Path-relaxation property (Lemma 24.15) If p = is a shortest path from s to vk, and the edges of p are relaxed in the order (s, v1), (v1, v2), , (vk-1, vk), then after relax all the edges, dvk = (s, vk). Note that other relaxations may take place among these relaxations., 2008 SDU 12,Properties of Shortest Paths and Relaxation,Predecessor-subgraph property (Lemma 24.17) Once dv = (s, v) for all v V, the predecessor subgraph is a shortest-paths tree rooted at s.,Note: Proofs for all these properties can be found in your textbook, Page 230-236., 2008 SDU 13,The Bellman-Ford Algorithm,Solve the single-source shortest-paths problem The algorithm returns a boolean value indicating whether or not there is a negative-weight cycle that is reachable from the source. If there is a negative-weight cycle reachable from the source s, the algorithm indicates no solution exists. If there are no such cycles, the algorithm produces the shortest paths and their weights. Exercise 24.1-4, 2008 SDU 14,The Bellman-Ford O(VE) Algorithm, 2008 SDU 15, 2008 SDU 16,Correctness of The Bellman-Ford,Lemma 24.2 Let G = (V, E) be a weighted, directed graph with source s and weight function w: ER, and assume that G contains no negative cycles that are reachable from s. Then, after the | V | - 1 iterations of the for loop of lines 2-4 of BELLMAN-FORD, we have dv = (s, v) for all vertices v., 2008 SDU 17,Proof of Lemma 24.2