6 006 Introduction to Algorithms Lecture 14 Prof Patrick Jaillet Lecture overview Shortest paths Definition Generic algorithm Some properties Readings CLRS 24 intro Paths in graphs Consider a directed graph G V E with edgeweight function w E R The weight of path p v1 v2 vk is defined to be the sum of all weights on the path i e w p w v1 v2 w vk 1 vk Example v1 4 v2 2 v3 5 v4 1 v5 w p 2 Shortest paths definition A shortest path from u to v is a path of minimum weight from u to v The shortest path weight u v from u to v is defined as the weight of any shortest path from u to v Special cases 1 no path from u to v exists u v you cannot get there from here 2 negative weight cycles undefined Well definedness of shortest paths If a graph G contains a negative weight cycle then some shortest paths may not exist C 4 S 2 A B 2 3 E 2 6 1 D Negative weight cycles s c undefined algorithm should detect such situations Single source shortest path problem Problem Given a directed graph G V E with edge weight function w and a node s find s v and a corresponding path for all v in V Today Generic algorithm and some structural properties Next three lectures Bellman Ford deals with negative weights Dijkstra algorithm fast and faster but assumes nonnegative weights Digression Question why can t we just enumerate all paths to find the shortest one Answer there can be exponentially many of them s v1 v2 2n different paths from s to vn 3n 1 vertices vn Useful data structures d v length of best path from s to v so far initialization d s 0 d v otherwise at any step update d v so that d v s v v predecessor of v on a best path so far initialization s s v nil otherwise A generic algorithm d s 0 s s for each v V s do d v v nil initialization while there is an edge u v E s t d v d u w u v do select one such edge somehow set d v d u w u v v u endwhile relaxation step the trick is in the somehow step Will not stop when negative cycles 1 u 0 d u 1 1 0 1 2 1 4 2 etc 3 2 1 0 v 1 4 What if no negative cycle 4 v1 4 2 v2 4 4 v3 8 4 2 1 v4 10 6 2 v5 1 v6 12 13 10 11 8 9 6 7 1 2 1 v7 14 13 12 11 10 9 8 7 1 2 Analysis for previous example Let n 1 be the number of vertices T n number of relaxations on v1 vn 1 Relax v1 v2 and v2 v3 Relax v1 v3 We have T n 2 T n 2 1 T n 2 2 T n 2 3 T n 2n 2 Recursion on v3 vn 1 Conclusion need to be careful how we relax Another digression 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 Optimal substructure Theorem A subpath of a shortest path is a shortest path Proof By contradiction p0j p v0 pij vi pjk vj pij vk Triangle inequality Theorem For all u v x V we have u v u x x v Proof u v u u x v x v x
View Full Document
Unlocking...