Shortest Path Problems 01 13 19 The Shortest Path problems in a directed and weighted graph G V E w include Single source shortest path problem find a shortest path from a given source s to every vertex v V Single destination shortest path problem find a shortest path to a given destination d from every vertex v V By reversing the direction of each edge Single source shortest path problem Single pair u v shortest path problem All pairs shortest path problem For each vertex s V call single source shortest path algorithm Non negative weight vs negative weight Definitions The weight of a path p v0 v1 vk is k w p w vi 1 vi i 1 The shortest path weight from u to v is min w p u p v p u v u v otherwise A shortest path from vertex u to vertex v is then defined as any path p with w p u v 01 13 19 Subpath Optimality Property Let p v1 v2 vk be a shortest path from vertex v1 to vertex vk Let pij vi vi 1 vj be the subpath of p from vertex vi to vertex vj Then pij is a shortest path from vi to vj Representation of a shortest path There is no need to store the path We only need to store the predecessor at each node 01 13 19 Relaxation Technique The idea of shortest path algorithms is based on the relaxation technique We initialize distance to the source to Initialize Single Source G s 1 for each vertex v V G do 2 v d 3 v nil 4 s d 0 01 13 19 We adjust reduce the distance whenever we visit an edge Relax u v w 1 if v d u d w u v 2 then v d u d w u v 3 v u set parent pointer Dijkstra s Single Source Shortest Path Alg 5 Relax 5 2 2 9 5 7 5 2 2 6 6 The idea of the algorithm is similar to Prim s MST algorithm Use a greedy approach Use a priority queue Q the key is the distance to the source Processed vertices are removed from Q and stored in a set S S 01 13 19 Q Dijkstra s Single Source Shortest Path Alg Dijkstra SP G w s 1 Initialize Single Source G s 2 S 3 Q V G 4 while Q do 5 u Extract Min Q 6 S S u 7 for each vertex v u adj do 8 Relax u v w 10 2 3 0 5 01 13 19 1 8 9 9 4 6 7 5 2 10 7 2 3 0 5 1 8 4 5 2 7 3 6 1 3 5 9 4 6 2 2 1 8 3 0 5 4 7 5 10 9 2 10 2 0 7 10 6 7 2 5 13 9 10 0 1 14 9 4 6 7 5 2 7 Running Time of Dijkstra s Algorithm 01 13 19 The running time depends on how we implement Q If we use a simple array to implement Q Extract Min takes O V while loop repeats O V times the total of vertices in adjacency lists O E The total running time is O V 2 E If we use a binary heap to implement Q Build heap takes O V Extract Min takes O lg V v d u d w u v in Relax decrease key O lg V The total running time is O E V lg V O E lg V if the graph is connected If we use a Fibonacci heap to implement Q The total running time is O V lg V E Correctness of Algorithms 01 13 19 For all predefined inputs precondition the algorithm produces correct outputs postconditions Partial Correctness If the preconditions are satisfied and if the program terminates then the postconditions are satisfied Core loop invariant and induction Termination If the preconditions are satisfied then the algorithm terminates in finite steps strictly decreasing order on finite set Correctness of Dijkstra s Algorithm Partial correctness and termination Precondition weighted graph G V E W and s V and w 0 Postcondition d u s u Loop invariant u u S d u s u S V when exiting the loop Therefore the postcondition is true Use mathematical induction 01 13 19 Step 1 For iteration 1 S s and d s s s 0 the loop invariant is true Correctness of Dijkstra s Algorithm contd Step 2 We assume that it is true when S has k elements and wish to prove it is still true when another element k 1 th u is added to S S z s u y x S z s x 01 13 19 u Vertex u is not connected to S This is not possible otherwise y should be chosen in step 5 by extract min Q Since x and z are in S and d x s x and d z s z u must have been relaxed from x and z and d u min d x w x u d z w z u Correctness of Dijkstra s Algorithm Termination The termination property can be proved based on the facts There are finite number of elements in Q Initially Q V The size of Q decrease by one in each iteration therefore the size of the Q decreases strictly Conclusion the algorithm will terminate 01 13 19 Negative Weight Edges When do we need a graph with negative weight edges 4 3 5 s 0 6 3 5 d 3 2 3 s 0 2 8 d 3 2 6 What is the shortest distance from s to d 01 13 19 It will be if there is a negative weight cycle In the following discussion we will assume there is not a negative weight cycle in the given graph Bellman Ford s Single Source Algorithm Dijkstra s algorithm non negative weight only Bellman Ford s algorithm also negative weights Bellman Ford G w s 1 Initialize Single Source G s 2 for i 1 to V 1 do 3 4 5 6 7 8 01 13 19 for each edge u v E do O V O V E Relax u v w for each vertex v u adj do O E if d v d u w u v then return False there is a negative cycle return True there is not a negative cycle Total running time O V E Bellman Ford s Algorithm Example t 6 x 5 2 8 s 0 7 2 y 3 4 6 7 x 4 5 2 8 7 2 7 y 9 3 4 6 2 z 9 7 2 z x 4 5 2 8 7 7 y 3 4 after pass 2 t 2 0 2 2 7 z 9 x 4 5 8 0 7 6 7 after pass 3 01 13 19 7 y 3 4 t 6 after pass 1 t 2 0 2 2 7 initialization …
View Full Document
Unlocking...