1. The Bellman-Ford and Floyd-Warshall Algorithms we described in class compute the lengths of the shortest...

 

Transcribed Image Text:

1. The Bellman-Ford and Floyd-Warshall Algorithms we described in class compute the lengths of the shortest paths. However, the algorithms did not address the question of actually outputting the shortest path. Describe how to modify the Bellman-Ford algorithm to keep track of some additional information that enables reconstructing the shortest path once the algorithm terminates. (Hint: Use a technique similar to what we did for Dijkstra's Algorithm) 2. Now, modify the Floyd-Warshall Algorithm to enable us to reconstruct (in linear time) the shortest paths. 4. Given two sequences A B(1), B(2),..., B(m), we wish to find the length of the longest common subsequence, that is the maximum such that there are indices (A(1), A(2),..., A(n)) and B = i 1. The Bellman-Ford and Floyd-Warshall Algorithms we described in class compute the lengths of the shortest paths. However, the algorithms did not address the question of actually outputting the shortest path. Describe how to modify the Bellman-Ford algorithm to keep track of some additional information that enables reconstructing the shortest path once the algorithm terminates. (Hint: Use a technique similar to what we did for Dijkstra's Algorithm) 2. Now, modify the Floyd-Warshall Algorithm to enable us to reconstruct (in linear time) the shortest paths. 4. Given two sequences A B(1), B(2),..., B(m), we wish to find the length of the longest common subsequence, that is the maximum such that there are indices (A(1), A(2),..., A(n)) and B = i