c Balaji Raghavachari 186 Algorithm Design and Analysis c Balaji Raghavachari 187 Algorithm Design and Analysis Correctness of Dijkstra s algorithm Otherwise let y be the rst vertex on the path from s that is outside S By loop invariant y d s y Using induction on the number of calls to the Relax procedure u d is an upper bound on s u the shortest path distance from s to u Since all edge weights are nonnegative s y s u Therefore y d s y s u u d Loop invariant at the start of each iteration of the while loop u d s u for all vertices u S Also for vertices in v V S v d is the length of a shortest path from s to v whose internal vertices are only from S But u d is minimum in V S and therefore u d y d Therefore u d y d and hence s u u d To show that the loop invariant holds after vertex u is added to S consider v V S If shortest path from s to v whose internal nodes are only from S goes through u then the call to Relax u v updates v d to be u d w u v Consider vertex u with minimum u d returned by Extract Min We show that u d s u Consider shortest path P from s to u If all internal nodes of P are from S then u d s u see loop invariant c Balaji Raghavachari 191 Algorithm Design and Analysis c Balaji Raghavachari 192 Algorithm Design and Analysis Speeding up the algorithm Shortest paths by extension To compute An for a given matrix A instead of n matrix multiplications we can solve the problem using O log n matrix multiplications by repeated squaring Consider the following recursive characterization of shortest paths let dk u v be the length of a shortest path from vertex u to vertex v that contains at most k edges The base case is d1 u v w u v For longer paths the recurrence is Why extend paths only one edge at a time Why not split the shortest path into two roughly equal parts New formulation dk 1 u v min dk u p w p v d2k u v min dk u m dk m v p V m V We need to calculate d V 1 u v since any simple shortest path contains at most V 1 edges Above recursive scheme can be implemented as a dynamic program that runs in O V 4 time With this formulation k doubles in each step Therefore in O log V iterations we get the answer Dynamic program implements this recurrence in O V 3 log V time Temporary matrix T is used to store D2k to reduce space used c Balaji Raghavachari 193 Algorithm Design and Analysis c Balaji Raghavachari APSP by extension dynamic program 195 Algorithm Design and Analysis d u v min d u v d k 1 u k d 4 3 7 1 5 6 4 5 D1 D2 D4 0 3 7 4 0 3 7 2 4 0 1 3 2 4 0 1 7 3 0 4 1 7 3 0 4 1 1 4 0 4 0 5 11 7 4 0 5 3 2 5 0 2 1 5 0 2 2 1 5 0 2 6 0 8 1 6 0 8 5 1 6 0 c Balaji Raghavachari 196 Algorithm Design and Analysis Sample run of Floyd Warshall s algorithm for APSP k 1 for u V do for v V do D u v w u v for k 1to V do for u V do for v V do D u v min D u v D u k D k v 2 4 2 7 3 k v 4 3 1 5 6 4 D 1 D 2 0 3 7 4 0 3 7 4 0 3 7 4 0 1 7 0 1 7 0 1 7 4 0 4 0 4 0 5 11 4 2 5 0 2 5 5 0 2 2 5 5 0 2 6 0 6 0 6 0 0 3 7 4 4 0 3 1 4 4 0 1 3 2 4 0 1 7 3 0 4 1 1 3 0 4 1 1 4 0 5 11 7 4 0 5 3 7 4 0 5 3 2 1 5 0 2 2 1 5 0 2 2 1 5 0 2 6 0 8 5 1 6 0 8 5 1 6 0 D 3 7 1 5 D 0 Dynamic program for computing d n ij runs in O V 3 2 2 7 Dynamic program based on a new recurrence Vertices are numbered 1 2 V De ne d k u v to be the length of a shortest path from u to v in which only nodes 1 2 k may be used as internal nodes Clearly d 0 u v w u v For k 0 k 1 4 3 1 Floyd Warshall algorithm k Algorithm Design and Analysis Sample run of APSP by extension AP SP G for u V do for v V do D u v w u v k 1 while k V 1 do for u V do for v V do T u v D u v Temporary matrix for m V do if T u v D u m D m v then T u v D u m D m v D T Copy D2k from T back to D k 2 k return D c Balaji Raghavachari 194 D 4 D 5
View Full Document
Unlocking...