COP 3503 USF Bellman Ford and Floyd Warshall Algorithms Project

Assignment

Modify your Programming Assignment 2 code to implement the Bellman-Ford and Floyd-Warshall algorithms.

Input is identical in format to Programming Assignment 2, and will consist of a number of vertices and a list of doubly-connected edges along with their costs.

The edges aredoubly-connected.  There will be no negative cycles (or, for that matter, negative weights).

Output for Bellman-Ford is identical in format to Programming Assignment 2, except you will print 0 and 0 for the distance and parent on the source line instead of -1 and -1.

Output for Floyd-Warshall consists of:

You do not need to retain paths for Floyd-Warshall.

Specifics

Read from cop3503-asn3-input.txt.  Pathfinding Again
COP3503 COMPUTER SCIENCE II
DR. MATTHEW B. GERBER
PORTIONS FROM SEAN SZUMLANSKI, MICHAEL MCALPIN,
WIKIPEDIA, AND WOLFRAM MATHWORLD
Bellman-Ford Algorithm
◦ The Bellman-Ford Algorithm is similar to
Dijkstra’s, but lacks Dijkstra’s effectively greedy
characteristics
◦ It simply re-computes all weights ( 𝑉 − 1)
times – the maximum length of an acyclic path
◦ This is slower than Dijkstra’s algorithm – but can
handle negative numbers, which Dijkstra’s
algorithm cannot
◦ It breaks if there’s a cycle with a negative
weight…
◦ …but it can also detect those!
◦ Give every node a current distance of infinity
◦ (except our source node)
◦ Mark every node’s parent as undefined
◦ (except our source node)
◦ Repeat 𝑉 − 1 times:
◦ For each edge 𝑒 = (𝑢, 𝑣):
◦ Let 𝑤 = 𝑒. 𝑤𝑒𝑖𝑔ℎ𝑡
◦ If 𝑢. 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 + 𝑤 < 𝑣. 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 ◦ Let 𝑣. 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 = 𝑢. 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 + 𝑤 ◦ 𝑣. 𝑝𝑎𝑟𝑒𝑛𝑡 = 𝑢 ◦ For each edge 𝑒 = (𝑢, 𝑣): ◦ Let 𝑤 = 𝑒. 𝑤𝑒𝑖𝑔ℎ𝑡 ◦ If 𝑢. 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 + 𝑤 < 𝑣. 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 ◦ Throw exception: Negative-weight cycle Floyd-Warshall Algorithm ◦ Consider graph 𝐺 = {𝑉, 𝐸} with 𝑉 = {1, 2, … , 𝑛} and no negative cycles. Floyd-Warshall Algorithm ◦ Consider graph 𝐺 = {𝑉, 𝐸} with 𝑉 = {1, 2, … , 𝑛} and no negative cycles. ◦ Consider prefix 𝑉! : vertices {1, 2, … , 𝑘}, 𝑘 ≤ 𝑛. Floyd-Warshall Algorithm ◦ Consider graph 𝐺 = {𝑉, 𝐸} with 𝑉 = {1, 2, … , 𝑛} and no negative cycles. ◦ Consider prefix 𝑉! : vertices {1, 2, … , 𝑘}, 𝑘 ≤ 𝑛. ! ◦ Consider path 𝑝"# : the shortest path from 𝑎 to 𝑏 with all intermediate vertices in 𝑉! . Floyd-Warshall Algorithm ◦ Consider graph 𝐺 = {𝑉, 𝐸} with 𝑉 = {1, 2, … , 𝑛} and no negative cycles. ◦ Consider prefix 𝑉! : vertices {1, 2, … , 𝑘}, 𝑘 ≤ 𝑛. ! ◦ Consider path 𝑝"# : the shortest path from 𝑎 to 𝑏 with all intermediate vertices in 𝑉! . ◦ One of two things is true: # #$% ◦ 𝑝!" = 𝑝!" . # ◦ 𝑝!" has vertex 𝑘 in it exactly once. # # ◦ Then we can consider prefix 𝑝!# and suffix 𝑝#" … ◦ But all their intermediate vertices have to be in 𝑉#$% ! # #$% # #$% ◦ Then 𝑝!# = 𝑝!# and 𝑝#" = 𝑝#" . Floyd-Warshall Algorithm ◦ Consider graph 𝐺 = {𝑉, 𝐸} with 𝑉 = {1, 2, … , 𝑛} and no negative cycles. ◦ Consider prefix 𝑉! : vertices {1, 2, … , 𝑘}, 𝑘 ≤ 𝑛. ! ◦ Consider path 𝑝"# : the shortest path from 𝑎 to 𝑏 with all intermediate vertices in 𝑉! . ◦ One of two things is true: # #$% ◦ 𝑝!" = 𝑝!" . # ◦ 𝑝!" has vertex 𝑘 in it exactly once. # # ◦ Then we can consider prefix 𝑝!# and suffix 𝑝#" … ◦ But all their intermediate vertices have to be in 𝑉#$% ! # #$% # #$% ◦ Then 𝑝!# = 𝑝!# and 𝑝#" = 𝑝#" . So we can observe that the weight of the shortest path from 𝑎 to 𝑏 through 𝑉! is: ! 𝑑"# =& the weight of edge (𝑎, 𝑏) !$% !$% !$% min 𝑑"# , 𝑑"! + 𝑑!# if 𝑘 = 0 if 𝑘 ≥ 1 This would be a nightmare to actually implement recursively – but with bottom-up dynamic programming, it’s not too bad. Floyd-Warshall Algorithm ◦ Consider graph 𝐺 = {𝑉, 𝐸} with 𝑉 = {1, 2, … , 𝑛} and no negative cycles. ◦ Consider prefix 𝑉! : vertices {1, 2, … , 𝑘}, 𝑘 ≤ 𝑛. ! ◦ Consider path 𝑝"# : the shortest path from 𝑎 to 𝑏 with all intermediate vertices in 𝑉! . ◦ One of two things is true: # #$% ◦ 𝑝!" = 𝑝!" . # ◦ 𝑝!" has vertex 𝑘 in it exactly once. # # ◦ Then we can consider prefix 𝑝!# and suffix 𝑝#" … ◦ But all their intermediate vertices have to be in 𝑉#$% ! # #$% # #$% ◦ Then 𝑝!# = 𝑝!# and 𝑝#" = 𝑝#" . So we can observe that the weight of the shortest path from 𝑎 to 𝑏 through 𝑉! is: ! 𝑑"# =& the weight of edge (𝑎, 𝑏) !$% !$% !$% min 𝑑"# , 𝑑"! + 𝑑!# if 𝑘 = 0 if 𝑘 ≥ 1 Floyd-Warshall Algorithm Initialization: ! 𝑑"# =& the weight of edge (𝑎, 𝑏) !$% !$% !$% min 𝑑"# , 𝑑"! + 𝑑!# if 𝑘 = 0 if 𝑘 ≥ 1 ◦ Let 𝑛 = |𝑉|. ◦ Create a 2D array 𝑑[𝑛][𝑛] of distances all at +∞. ◦ For each vertex 𝑣, let 𝑑 𝑣 𝑣 = 0. ◦ For each edge e = (𝑎, 𝑏, 𝑤𝑒𝑖𝑔ℎ𝑡), let 𝑑 𝑎 𝑏 = 𝑤𝑒𝑖𝑔ℎ𝑡. Iteration: ◦ For 𝑘 = 1. . 𝑛 ◦ For 𝑎 = 1. . |𝑛| ◦ For 𝑏 = 1. . |𝑛| ◦ If 𝑑 𝑎 𝑘 + 𝑑 𝑘 𝑏 < 𝑑 𝑎 [𝑏], then let 𝑑 𝑎 𝑏 = 𝑑 𝑎 𝑘 + 𝑑 𝑘 [𝑏].