Introduction to algorithms 6.046J/18,401J/SMA5503 Lecture 18 Prof erik demaine
Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 18 Prof. Erik Demaine
Negative-weight cycles Recall: If a graph G=(V, E) contains a negative weight cycle then some shortest paths may not exist Example: <0 Bellman-Ford algorithm: Finds all shortest-pat lengths from a sources e y to all ve yor determines that a negative-weight cycle exists c 2001 by Charles E Leiserson Introduction to Algorithms Day 31 L18.2
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 31 L18.2 Negative-weight cycles Recall: If a graph G = (V, E) contains a negativeweight cycle, then some shortest paths may not exist. Example: uu vv … < 0 Bellman-Ford algorithm: Finds all shortest-path lengths from a source s ∈ V to all v ∈ V or determines that a negative-weight cycle exists
Bellman- Ford algorithm ds]<0 for eachvE V-s initialization doal]←∞ for i<l to do for each edge(u,v) E do if[vi>du+ w(u, v) relaxation then dlv]←+w(al,y)∫step for each edge(l2y)∈E do if dv>du+w(u, v) then report that a negative-weight cycle exists At the end dv=8(s, v). Time=O(VE) c 2001 by Charles E Leiserson Introduction to Agorithms Day31L18.3
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 31 L18.3 Bellman-Ford algorithm d[s] ← 0 for each v ∈ V – {s} do d[v] ← ∞ for i ← 1 to |V| – 1 do for each edge (u, v) ∈ E do if d[v] > d[u] + w(u, v) then d[v] ← d[u] + w(u, v) for each edge (u, v) ∈ E do if d[v] > d[u] + w(u, v) then report that a negative-weight cycle exists initialization At the end, d[v] = δ(s, v). Time = O(VE). relaxation step
Example of bellman-Ford AB C E B 0 E D c 2001 by Charles E Leiserson Introduction to Agorithms Day 31 L18.4
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 31 L18.4 Example of Bellman-Ford AA BB EE CC DD –1 4 1 2 –3 2 5 3 ABCDE 0 ∞∞∞∞ ∞ 0 ∞ ∞ ∞
Example of Bellman-Ford AB C E B 2 000 E D c 2001 by Charles E Leiserson Introduction to Agorithms Day 31 L18.5
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 31 L18.5 –1∞ 0 –1 ∞∞∞ Example of Bellman-Ford AA BB EE CC DD –1 4 1 2 –3 2 5 3 ABCDE 0 ∞∞∞∞ 0 ∞ ∞ ∞