6 006 Introduction to Algorithms Lecture 15 Prof Patrick Jaillet Lecture overview Shortest paths II Review definition properties generic algorithm Bellman Ford algorithm for the case with negative weights CLRS 24 1 NO s Single source shortest path problem Problem Given a directed graph G V E with edge weight function w E R and a node s find the shortest path weight s v and a corresponding shortest path from s to each v in V Special cases 1 if no path from s to v exists s v 2 if negative weight cycles in G problem is not well defined Negative cycles with such cycles problem is not well defined C 4 S 2 A B 2 3 E 2 6 1 D 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 Generic algorithm data structures d v length of best path from s to v so far initialization d s 0 d v otherwise idea iteratively decrease d v while maintaining 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 steps about the somehow step doesn t stop when negative cycles 1 su 0 d s d u 1 1 0 1 2 1 4 2 etc 3 2 1 0 v 1 4 bad choice of somehow can lead to exponential running time 4 v1 4 2 v2 4 4 v3 8 2 relax v1 v2 relax v2 v3 relax v1 v3 relax v3 v4 relax v3 v4 1 v4 10 2 v5 1 v6 12 13 10 11 4 6 8 relax v6 v7 relax v5 v7 6 relax v3 v5 relax v5 v6 relax v6 v7 relax v5 v7 9 7 1 v7 14 13 12 11 10 9 8 7 Bellman Ford algorithm d s 0 s s for each v V s do d v v nil initialization 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 v u for each edge u v E do if d v d u w u v then report a negative cycle O n relaxation steps O mn final steps O m Bellman Ford example 4 v1 4 2 v2 4 v3 2 1 v4 2 v5 1 v6 1 v7 Assume we scan edges from right to left 4 4 4 4 4 4 6 6 6 6 7 7 6 7 7 If we scan left to right 4 4 6 Bellman Ford another example E v1 v2 v1 v4 v2 v3 v4 v2 0 end of first iteration v1 5 2 1 2 v4 5 4 v2 end of second iteration 2 v3 the shortest paths from v1 4 3 Bellman Ford Correctness I Theorem 1 If G V E contains no negative weight cycles then at the end of the algorithm d v s v for all v V Proof By induction on the following property P i After i iterations of the relaxation steps if d v it is the weight of some path from s to v if there is a path from s to v with at most i edges then d v at most the weight of the shortest path from s to v with at most i edges Bellman Ford Correctness II Theorem 2 The algorithm correctly reports the existence of a negative cycle in G V E Proof If G V E contains a negative cycle then there is always an edge that can be relaxed and the algorithm will then correctly report it Conversely if the algorithm reports a negative cycle then there must be a cycle in a shortest path at the end of the final steps and this must then be a negative cycle This graph has a special structure Which And how to use it with Bellman Ford E v1 v2 v1 v4 v2 v3 v4 v2 v1 5 2 v4 4 v2 2 v3 think about it for next time
View Full Document
Unlocking...