L14 - Graph Algorithms - Shortest Path.pdf

CP312 Algorithm Design and Analysis I LECTURE 14: GRAPH ALGORITHMS – SHORTEST PATH Weight of a Path Given a weighted directed graph 𝐺 = (𝑉, 𝐸) with weight function 𝑤, the weight of a path 𝑝 = (𝑣1 , 𝑣2 , … , 𝑣𝑘 ) is defined to be: 𝑘−1 𝑤 𝑝 = ෍ 𝑤(𝑣𝑖 , 𝑣𝑖+1 ) 𝑖=1 Example: 4 𝑣1 𝑣2 −2 −5 𝑣3 𝑣4 1 𝑣5 𝑤 𝑝 =...

CP312 Algorithm Design and Analysis I LECTURE 14: GRAPH ALGORITHMS – SHORTEST PATH Weight of a Path Given a weighted directed graph 𝐺 = (𝑉, 𝐸) with weight function 𝑤, the weight of a path 𝑝 = (𝑣1 , 𝑣2 , … , 𝑣𝑘 ) is defined to be: 𝑘−1 𝑤 𝑝 = ෍ 𝑤(𝑣𝑖 , 𝑣𝑖+1 ) 𝑖=1 Example: 4 𝑣1 𝑣2 −2 −5 𝑣3 𝑣4 1 𝑣5 𝑤 𝑝 = −2 Shortest Path Problem Problem: Find a shortest path between a vertex 𝑠 and every other vertex in the graph. Input: A weighted directed graph 𝐺 = (𝑉, 𝐸) and a source vertex 𝑠. Output: A set of paths from vertex 𝑠 to every other vertex 𝑣 such that for every path 𝑝 = (𝑠, … , 𝑣) the weight of the path 𝑤(𝑝) is minimized. 𝛿 𝑠, 𝑣 = min{𝑤 𝑝 ∶ 𝑝 is a path from 𝑠 to 𝑣} Shortest Path: Optimal Substructure Theorem: A subpath of a shortest path is also a shortest path. 𝛿(𝑣1 , 𝑣6 ) 𝑣1 𝑣2 𝑣3 𝑣4 𝑣7 𝑣5 𝑣6 Proof Sketch: Suppose that this is the shortest path from 𝑣1 to 𝑣6 Then, by the theorem, (𝑣2 , 𝑣3 , 𝑣4 , 𝑣5 ) must be the shortest path from 𝑣2 to 𝑣5. If not then this means there is another shortest path from 𝑣2 to 𝑣5 , which means that there is a shorter path from 𝑣1 to 𝑣6 Contradicting our assumption! Shortest Path Problem Idea: A Greedy approach 1. Maintain a set 𝑋 of vertices whose shortest-path distances from 𝑠 are known. 2. At each step, add to 𝑋 the vertex 𝑣 ∈ 𝑉 − 𝑋 whose distance estimate from 𝑠 is minimal. 3. Update the distance estimates of vertices adjacent to 𝑣 Dijkstra’s Algorithm Dijkstra(𝑉, 𝐸, 𝑠): 𝑑 𝑠 =0 for each 𝑢 ∈ 𝑉 − {𝑠} 𝑑[𝑣] = ∞ 𝑋=∅ 𝑄=𝑉 while 𝑄 ≠ ∅ 𝑢 = GET-MIN(𝑄) 𝑋 = 𝑋 ∪ {𝑢} for each 𝑣 ∈ 𝐴𝑑𝑗[𝑢] if 𝑑 𝑣 > 𝑑 𝑢 + 𝑤(𝑢, 𝑣) 𝑑 𝑣 = 𝑑 𝑢 + 𝑤(𝑢, 𝑣) // 𝐺 is a graph with non-negative edge weights // 𝑄 is a priority-queue (e.g. min-heap) // Update distances Dijkstra’s Algorithm: Example Graph with non-negative edge weights B A D 2 10 4 1 8 7 9 3 2 C E Dijkstra’s Algorithm: Example Graph with non-negative edge weights Initialize: Q: A 0 B C D E ∞ ∞ ∞ ∞ B A 10 3 X: 2 ∞ 4 0 D 1 ∞ C ∞ 8 7 9 2 ∞ E Dijkstra’s Algorithm: Example Graph with non-negative edge weights ‘A’← GET-MIN(𝑄) Q: A 0 B C D E ∞ ∞ ∞ ∞ B A 10 3 X: A 2 ∞ 4 0 D 1 ∞ C ∞ 8 7 9 2 ∞ E Dijkstra’s Algorithm: Example Graph with non-negative edge weights Decrease 𝑑 via edges leaving A Q: A 0 B C D E ∞ 10 ∞ 3 ∞ ∞ ∞ ∞ B A 10 3 X: A 2 10 4 0 D 1 3 C ∞ 8 7 9 2 ∞ E Dijkstra’s Algorithm: Example Graph with non-negative edge weights ‘C’← GET-MIN(𝑄) Q: A 0 B C D E ∞ 10 ∞ 3 ∞ ∞ ∞ ∞ B A 10 3 X: A C 2 10 4 0 D 1 3 C ∞ 8 7 9 2 ∞ E Dijkstra’s Algorithm: Example Graph with non-negative edge weights Decrease 𝑑 via edges leaving C Q: A 0 B C D E ∞ 10 ∞ 3 ∞ ∞ 11 ∞ ∞ 5 7 B A 10 3 X: A C 2 7 4 0 D 1 3 C 11 8 7 9 2 5 E Dijkstra’s Algorithm: Example Graph with non-negative edge weights ‘E’← GET-MIN(𝑄) Q: A 0 B C D E ∞ 10 ∞ 3 ∞ ∞ 11 ∞ ∞ 5 7 B A 10 3 X: A C E 2 7 4 0 D 1 3 C 11 8 7 9 2 5 E Dijkstra’s Algorithm: Example Graph with non-negative edge weights Decrease 𝑑 via edges leaving E Q: A 0 B C D E ∞ 10 ∞ 3 ∞ ∞ 11 11 ∞ ∞ 5 7 7 X: A C E B A 10 3 2 7 4 0 D 1 3 C 11 8 7 9 2 5 E Dijkstra’s Algorithm: Example Graph with non-negative edge weights ‘B’← GET-MIN(𝑄) Q: A 0 B C D E ∞ 10 ∞ 3 ∞ ∞ 11 11 ∞ ∞ 5 7 7 X: A C E B B A 10 3 2 7 4 0 D 1 3 C 11 8 7 9 2 5 E Dijkstra’s Algorithm: Example Graph with non-negative edge weights Decrease 𝑑 via edges leaving B Q: A 0 B C D E ∞ 10 ∞ 3 ∞ ∞ 11 11 9 ∞ ∞ 5 7 7 X: A C E B B A 10 3 2 7 4 0 D 1 3 C 9 8 7 9 2 5 E Dijkstra’s Algorithm: Example Graph with non-negative edge weights Decrease 𝑑 via edges leaving B Q: A 0 B C D E ∞ 10 ∞ 3 ∞ ∞ 11 11 9 ∞ ∞ 5 7 7 X: A C E B B A 10 3 D 2 7 4 0 D 1 3 C 9 8 7 9 2 5 E Same analysis as Prim’s algorithm! Analysis of Dijkstra’s Algorithm Θ(|𝑉|) |𝑉| times |𝐴𝑑𝑗 𝑢 | times Dijkstra(𝑉, 𝐸, 𝑠): 𝑑 𝑠 =0 for each 𝑢 ∈ 𝑉 − {𝑠} 𝑑[𝑣] = ∞ 𝑋=∅ 𝑄=𝑉 while 𝑄 ≠ ∅ 𝑢 = GET-MIN(𝑄) 𝑋 = 𝑋 ∪ {𝑢} for each 𝑣 ∈ 𝐴𝑑𝑗[𝑢] if 𝑑 𝑣 > 𝑑 𝑢 + 𝑤(𝑢, 𝑣) 𝑑 𝑣 = 𝑑 𝑢 + 𝑤(𝑢, 𝑣) // 𝐺 is a graph with non-negative edge weights // 𝑄 is a priority-queue (e.g. min-heap) // Update distances If priority queue is a binary heap then 𝑇 𝑛 = 𝑂(𝐸 lg 𝑉) A drawback with Dijkstra Suppose you want to find the shortest path from 𝑣1 to every other vertex using Dijkstra’s algorithm for the following graph. 10 10 𝑣1 𝑣2 7 1 𝑣3 Dijkstra says: 𝑣1 𝑣2 𝑣3 0 10 7 𝑣1 Dijkstra’s algorithm does not yield the shortest path for graphs with negative weight edges Dijkstra says: 𝑣2 7 −5 𝑣3 Incorrect 𝑣1 𝑣2 𝑣3 0 10 7 Negative-Weight Cycles If a graph 𝐺 contains a negative-weight cycle, then some shortest paths may not exist. −5 𝑦 𝑥 1 −2 𝑣1 𝑣2 10 𝑣3 12 𝑣4 1 𝑣5 4 𝑣6 −1 Nonnegative-Weight Cycles If a graph 𝐺 contains only nonnegative-weight cycles, then all shortest paths exist. 5 𝑦 𝑥 1 −2 𝑣1 𝑣2 10 𝑣3 12 𝑣4 1 But can a shortest path contain a cycle? ◦ No. Why? 𝑣5 4 𝑣6 −1 Bellman-Ford Algorithm Just like Dijkstra’s algorithm, Bellman-Ford finds all the shortestpath lengths from a source 𝑠 ∈ 𝑉 to all other vertices 𝑣 ∈ 𝑉 Unlike Dijkstra, Bellman-Ford can handle negative weight edges and can even determine if a negative-weight cycle exists. ◦ In which case, we will know that some shortest paths may not exist. Bellman-Ford Algorithm BellmanFord(𝑉, 𝐸, 𝑠): 𝑑 𝑠 =0 for each 𝑢 ∈ 𝑉 − {𝑠} 𝑑[𝑣] = ∞ for 𝑖 = 1 to 𝑉 − 1 for each edge 𝑢, 𝑣 ∈ 𝐸 if 𝑑 𝑣 > 𝑑 𝑢 + 𝑤(𝑢, 𝑣) 𝑑 𝑣 = 𝑑 𝑢 + 𝑤(𝑢, 𝑣) for each edge 𝑢, 𝑣 ∈ 𝐸 if 𝑑 𝑣 > 𝑑 𝑢 + 𝑤(𝑢, 𝑣) return NEG_CYCLE // Initialization // |𝑉| − 1 passes // Order does not matter // Update distances // Check for convergence At the end 𝑑 𝑣 = 𝛿(𝑠, 𝑣) Bellman-Ford Algorithm: Example B 2 -1 A 3 2 1 4 Edges = 𝐵, 𝐸 , 𝐵, 𝐷 , 𝐷, 𝐵 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐷, 𝐶 , 𝐵, 𝐶 , 𝐸, 𝐷 E -3 C 5 D Bellman-Ford Algorithm: Example B Initialize: A 0 B C D E ∞ ∞ ∞ ∞ ∞ 2 -1 A 3 0 2 1 4 𝐵, 𝐸 , 𝐵, 𝐷 , 𝐷, 𝐵 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐷, 𝐶 , 𝐵, 𝐶 , 𝐸, 𝐷 ∞ -3 ∞ Edges = E C 5 ∞ D Bellman-Ford Algorithm: Example B First pass of distance updates: A 0 0 B C D E ∞ -1 ∞ 2 ∞ ∞ ∞ ∞ −1 2 -1 A 3 0 2 1 4 𝐵, 𝐸 , 𝐵, 𝐷 , 𝐷, 𝐵 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐷, 𝐶 , 𝐵, 𝐶 , 𝐸, 𝐷 ∞ -3 2 Edges = E C 5 ∞ D Bellman-Ford Algorithm: Example B Second pass of distance updates: A 0 0 B C D E ∞ -1 ∞ 2 0 -1 2 ∞ ∞ -2 ∞ ∞ 1 −1 2 -1 A 3 0 2 1 4 𝐵, 𝐸 , 𝐵, 𝐷 , 𝐷, 𝐵 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐷, 𝐶 , 𝐵, 𝐶 , 𝐸, 𝐷 1 -3 2 Edges = E C 5 −2 D If after 𝑉 − 1 iterations, the distances do not stabilize, there is a negative cycle Bellman-Ford Algorithm: Example B Third pass of distance updates: A 0 0 B C D E ∞ -1 ∞ 2 0 0 -1 -1 2 2 ∞ ∞ -2 -2 ∞ ∞ 1 1 −1 -1 A 3 0 2 1 4 Notes: Values decrease monotonically Edges = 2 𝐵, 𝐸 , 𝐵, 𝐷 , 𝐷, 𝐵 , 𝐴, 𝐵 , 𝐴, 𝐶 , 𝐷, 𝐶 , 𝐵, 𝐶 , 𝐸, 𝐷 E 1 -3 2 C 5 −2 D Analysis of Bellman-Ford Algorithm Θ(|𝑉|) Θ( 𝑉 × |𝐸|) Θ(|𝐸|) BellmanFord(𝑉, 𝐸, 𝑠): 𝑑 𝑠 =0 for each 𝑢 ∈ 𝑉 − {𝑠} 𝑑[𝑣] = ∞ for 𝑖 = 1 to 𝑉 − 1 for each edge 𝑢, 𝑣 ∈ 𝐸 if 𝑑 𝑣 > 𝑑 𝑢 + 𝑤(𝑢, 𝑣) 𝑑 𝑣 = 𝑑 𝑢 + 𝑤(𝑢, 𝑣) for each edge 𝑢, 𝑣 ∈ 𝐸 if 𝑑 𝑣 > 𝑑 𝑢 + 𝑤(𝑢, 𝑣) return NEG_CYCLE // Initialization 𝑻 𝒏 = 𝚯(𝑽𝑬) // Update distances // Check for convergence Bellman-Ford Algorithm: Correctness Theorem: If 𝐺 = (𝑉, 𝐸) contains no negative-weight cycles then after the Bellman-Ford algorithm completes execution, 𝑑 𝑣 = 𝛿(𝑠, 𝑣) for all 𝑣 ∈ 𝑉 Proof: Let 𝑣 ∈ 𝑉 be any vertex, and consider a shortest path 𝑝 from 𝑠 to 𝑣 with the minimum number of edges. 𝑝 ≤ 𝑉 −1 𝑝: 𝑠 𝑣1 𝑣2 𝑣3 … 𝑣 Since 𝑝 is a shortest path, by the optimal substructure property we have: 𝛿 𝑠, 𝑣𝑖 = 𝛿 𝑠, 𝑣𝑖−1 + 𝑤(𝑣𝑖−1 , 𝑣𝑖 ) Bellman-Ford Algorithm: Correctness 𝑝: 𝑠 𝑣1 𝑣2 𝑣3 … 𝑣 Initially, 𝑑 𝑠 = 0 = 𝛿(𝑠, 𝑣0 ) and 𝑑[𝑠] will be unchanged after every pass. After pass 1 through 𝐸, we have 𝑑 𝑣1 = 𝛿(𝑠, 𝑣1 ) After pass 2 through 𝐸, we have 𝑑 𝑣2 = 𝛿(𝑠, 𝑣2 ) … After pass 𝑉 − 1 through 𝐸, we have 𝑑 𝑣 = 𝛿(𝑠, 𝑣) The number of actual passes depends on the order of edges visited per pass Variants of the Shortest Path Problem Unweighted (weight 1) shortest path ◦ Depth-first search or Breadth-first search ◦ Takes Θ(𝑉 + 𝐸) time Single-destination shortest path All-pairs shortest path ◦ Floyd-Warshall algorithm