DOC PREVIEW
MIT 6 006 - Lecture Notes

This preview shows page 1-2 out of 5 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

MIT OpenCourseWare http://ocw.mit.edu6.006 Introduction to AlgorithmsSpring 2008For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.� Lecture 16 Shortest Paths II: Bellman-Ford 6.006 Spring 2008 Lecture 16: Shortest Paths II: Bellman-Ford Lecture Overview Review: Notation • • Generic S.P. Algorithm • Bellman Ford Algorithm – Analysis – Correctness Recall: path p = < v0, v1, . . . , vk > (v1, vi+1) �E 0 ≤ i < k k−1w(p) = w(vi, vi+1) i−0 Shortest path weight from u to v is δ(u, v). δ(u, v) is ∞ if v is unreachable from u, undefined if there is a negative cycle on some path from u to v. uv-veFigure 1: Negative Cycle Generic S.P. Algorithm Initialize: for v � V : d [v] ← ∞Π [v] NIL← d[S] 0← Main: repeat select edge (u, v) [somehow] ⎡ if d[v] > d[u] + w(u, v) : “Relax” edge (u, v) ⎢⎣ d[v] ← d[u] + w(u, v) π[v] u← until you can’t relax any more edges or you’re tired or . . . 1Lecture 16 Shortest Paths II: Bellman-Ford 6.006 Spring 2008 Complexity: Termination: Algorithm will continually relax edges when there are negative cycles present. 0v134-1ud[u]1211-40-1-2210etcFigure 2: Algorithm may not terminate due to negative CyclesComplexity could be exponential time with poor choice of edges. v0v1v2v3v4v5v64 8 10 12 13 141310 11 124 6 8 9 1011 (v0, v1) (v1, v2)all of v2, vn (v0, v2) all of v2, vnT(n) = θ(2n/2) T(n) = 3 + 2T(n-2) ORDERFigure 3: Algorithm could take exponential time 2Lecture 16 Shortest Paths II: Bellman-Ford 6.006 Spring 2008 5-Minute 6.006 Here’s what I want you to remember from 6.006 five years after you graduate T(n) = C1 + C2T(n - C3)T(n) = C1 + C2T(n / C3)Exponential BadPolynomial Goodif C2 > 1, trouble! Divide & Explode C2 > 1 okay provided C3 > 1 if C3 > 1Divide & ConquerFigure 4: Exponential vs. Polynomial Bellman-Ford(G,W,S) Initialize () for i = 1 to | v | −1 for each edge (u, v)�E: Relax(u, v) for each edge (u, v)�E do if d[v] > d[u] + w(u, v) then report a negative-weight cycle exists At the end, d[v] = δ(s, v), if no negative-weight cycles B5A ECD4-3-12213∞-1∞∞∞01138265474 22 3End of pass 1B5A ECD4-3-12213-11∞∞201138265471 -22 3End of pass 2 (and 3 and 4)Figure 5: The numbers in circles indicate the order in which the δ values are computed 3Lecture 16 Shortest Paths II: Bellman-Ford 6.006 Spring 2008 Theorem: If G = (V, E) contains no negative weight cycles, then after Bellman-Ford executes d[v] = δ(u, v) for all v�V . Proof: v�V be any vertex. Consider path p from s to v that is a shortest path with minimum number of edges. p:Sv0v1v2vkvδ (s, vi) = δ (s, vi-1) + w (vi-1,vi) Figure 6: Illustration for proof Initially d[v0] = 0 = δ(S, V0) and is unchanged since no negative cycles. After 1 pass through E, we have d[v1] = δ(s, v1) After 2 passes through E, we have d[v2] = δ(s, v2) After k passes through E, we have d[vk] = δ(s, vk) No negative weight cycles = ⇒ p is simple = ⇒ p has ≤| V | −1 edges Corollary If a value d[v] fails to converge after | V | −1 passes, there exists a negative-weight cycle reachable from s.


View Full Document

MIT 6 006 - Lecture Notes

Documents in this Course
Quiz 1

Quiz 1

7 pages

Quiz 2

Quiz 2

12 pages

Quiz 2

Quiz 2

9 pages

Quiz 1

Quiz 1

10 pages

Quiz 2

Quiz 2

11 pages

Quiz 1

Quiz 1

12 pages

Graphs

Graphs

27 pages

Load more
Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?