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]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 ∞ ∞ ∞
Example of bellman-Ford AB C E B 000 E)0-14∞ D 4 c 2001 by Charles E Leiserson Introduction to Agorithms Day 31 L18.6
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 31 L18.6 –1∞ 0 –1 ∞∞∞ Example of Bellman-Ford AA BB EE CC DD –1 4 1 2 –3 2 5 3 ABCDE 0 ∞∞∞∞ 0 ∞ 4 ∞ 0 –1 4 ∞∞
Example of bellman-Ford AB C E B 000 E)0-14∞ 0-12∞ D c 2001 by Charles E Leiserson Introduction to Agorithms Day 31 L18.7
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 31 L18.7 4 0 –1 2 ∞ ∞ 2 –1∞ 0 –1 ∞∞∞ Example of Bellman-Ford AA BB EE CC DD –1 4 1 2 –3 2 5 3 ABCDE 0 ∞∞∞∞ 0 ∞ ∞ 0 –1 4 ∞∞
Example of bellman-Ford AB C E B 000 E)0-14∞ 0-12∞ D c 2001 by Charles E Leiserson Introduction to Agorithms Day 31 L18.8
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 31 L18.8 –1∞ Example of Bellman-Ford AA BB EE CC DD –1 4 1 2 –3 2 5 3 0 ∞ 2 ∞ 0 –1 2 ∞ ∞ 0 –1 ∞∞∞ ABCDE 0 ∞∞∞∞ 0 –1 4 ∞∞
Example of bellman-Ford AB C E B人、2 000 E)0-14∞ 0-12∞ D 0-12∞1 c 2001 by Charles E Leiserson Introduction to Agorithms Day 31 L18.9
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 31 L18.9 –1∞ Example of Bellman-Ford AA BB EE CC DD –1 4 1 2 –3 2 5 3 0 2 ∞ 0 –1 2 ∞ ∞ 0 –1 ∞∞∞ ABCDE 0 ∞∞∞∞ 0 –1 4 ∞∞ 1 0 –1 2 ∞ 1
Example of bellman-Ford AB C E B 000 E 14∞ 12∞ D 0000 12∞1 c 2001 by Charles E Leiserson Introduction to Agorithms Day 31 L18.10
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 31 L18.10 ∞1 0 –1 2 1 1 –1∞ Example of Bellman-Ford AA BB EE CC DD –1 4 1 2 –3 2 5 3 0 2 0 –1 2 ∞ ∞ 0 –1 ∞∞∞ ABCDE 0 ∞∞∞∞ 0 –1 4 ∞∞ 1 0 –1 2 ∞ 1