MIT OpenCourseWare http ocw mit edu 6 006 Introduction to Algorithms Spring 2008 For 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 w p k 1 0 i k 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 unde ned if there is a negative cycle on some path from u to v ve u v Figure 1 Negative Cycle Generic S P Algorithm Initialize Main Relax edge u v for v V d v v NIL d S 0 repeat select edge u v somehow if d v d u w u v d v d u w u v v u until you can t relax any more edges or you re tired or 1 Lecture 16 Shortest Paths II Bellman Ford 6 006 Spring 2008 Complexity Termination Algorithm will continually relax edges when there are negative cycles present 1 u 0 1 1 0 1 2 d u 1 4 3 2 etc 2 1 0 v 1 4 Figure 2 Algorithm may not terminate due to negative Cycles Complexity could be exponential time with poor choice of edges v0 T n 3 2T n 2 T n 2 n 2 v1 v2 v3 v4 v5 v6 4 8 10 12 13 10 11 8 9 14 13 12 11 10 ORDER v0 v1 v1 v2 all of v2 vn v0 v2 4 6 all of v2 vn Figure 3 Algorithm could take exponential time 2 Lecture 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 ve years after you graduate Exponential Bad Polynomial Good T n C1 C2T n C3 T n C1 C2T n C3 if C2 1 trouble Divide Explode C2 1 okay provided C3 1 if C3 1 Divide Conquer Figure 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 1 1 1 B 1 0 4 4 2 2 3 3 5 E 2 1 8 2 C 6 5 B 1 2 3 7 4 A 1 0 4 3 3 5 E 2 1 8 2 D C 2 End of pass 1 2 3 7 4 A 1 6 5 D 1 1 3 1 2 2 3 End of pass 2 and 3 and 4 Figure 5 The numbers in circles indicate the order in which the values are computed 3 Lecture 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 v v1 vk s vi s vi 1 w vi 1 vi S p v0 v2 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 4
View Full Document
Unlocking...