All Pairs Shortest Path and Recursive Formulation
Explore the concept of finding the shortest paths between all pairs of vertices in a graph using dynamic programming. Discover the recursive formulation to determine the shortest path length using intermediate vertices. Delve into the complexities of solving such problems efficiently.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Shortest path In lecture, the following problem was discussed: Input: A graph ?(?,?), with edge weights ??, and ?,? ? Output: The shortest path (length) from ? to ? in ? and Dijkstra s algorithm was found to be the optimal algorithm. If instead we want to find the shortest path from ? to all vertices, we can still use Dijkstra s. However, if we want to find the shortest path from all vertices to all vertices, the problem becomes much more difficult.
All pairs shortest path (APSP) The problem is defined as follows: Input: A graph ?(?,?), with edge weights ?? Output: For all ?,? pairs, the shortest path (length) from ? to ? in ? To simplify the algorithm, we will also require that no negative cycles exist in the graph. To solve this, we ll use dynamic programming.
Breaking down the problem Suppose we know the shortest paths from all ? ? to all ? ?, which don t use ? as an intermediate vertex. That is, if the shortest path from ? to ? uses ? we don t know that path, but if the second shortest path doesn t use ?, we know that path. We also know the shortest path from any vertex to ? and from ? to any vertex, since in neither case is ? is an intermediate vertex.
Breaking down the problem Suppose we know the shortest paths from all ? ? to all ? ?, which don t use ? as an intermediate vertex. There s two cases to consider for each ?,? pair: ? is on the shortest path from ? to ?. What is the shortest ?,? path length here? ? isn t on the shortest path from ? to ?. What is the shortest ?,? path length here? Once we know these two path lengths, which do we pick?
Generalization Let s generalize the previous problem suppose we know all shortest paths for all ?,? pairs using only intermediate vertices in ?, a subset of ?, and we want to know all the shortest paths using only intermediate vertices in ? {?}. Again, there are two cases: The shortest path using only ? ? contains ?. What is the shortest ?,? path length using only ? ? in this case? The shortest path using only ? {?} doesn t contain ?. What is the shortest ?,? path length using only ? ? in this case?
Recursive formulation Let us define an arbitrary order on the vertices, i.e. let ? = {1,2,3, ?}. Let ?(?,?,?) be the shortest path length from ? to ? using only intermediate vertices {1,2,3, ?}. Then: If ? is on the shortest path, ? ?,?,? = ? ?,?,? 1 + ?(?,?,? 1) Else, ? ?,?,? = ?(?,?,? 1) Equivalently, ? ?,?,? = min ? ?,?,? 1 ,? ?,?,? 1 + ? ?,?,? 1 In what order should we solve the subproblems? (i.e. how should we iterate over ?,?,??
Base cases For the base cases if we can t use any intermediate vertices, then what is the shortest path from ? to ?? What s the shortest path from a vertex to itself?
First version def APSP(G): SP = 3-D array indexed 1 to n, 1 to n, 0 to n For each vertex i: SP[i][i][0] = 0 For each edge (i, j): SP[i][j][0] = e(i,j) For k from 1 to n: For i from 1 to n: For j from 1 to n: SP[i][j][k] = min(SP[i][j][k-1], SP[i][k][k-1]+SP[k][j][k-1]) Return SP[1:n][1:n][n]
Analysis Our DP table is clearly size ?(?3), and each update takes ?(1) time, so the runtime is simply ?(?3). This runtime is pretty good there are various improvements, but they come with nuances. However, we can very easily improve on the spatial complexity.
Improving the algorithm One nice property of this algorithm: If we compute in increasing ? order, once we compute ?(?,?,?), we don t need to store ?(?,?,? 1). We won t use ?(?,?,? 1) to compute any ? ?,?,? + 1 ,? ?,?,? + 2 because the difference in the third argument is 2 or greater. We won t use ?(?,?,? 1) to compute any ?(?,?,?) unless ? = ? or ? = ?, in which case ?(?,?,?) and ?(?,?,? 1) are the same. Thus, at any stage in the algorithm, we only need to store ?(?,?,?) for the most recent ? value.
Second version def APSP(G): SP = 2-D array indexed 1 to n, 1 to n For each vertex i: SP[i][i] = 0 For each edge (i, j): SP[i][j] = e(i,j) For k from 1 to n: For i from 1 to n: For j from 1 to n: SP[i][j]= min(SP[i][j], SP[i][k]+SP[k][j]) Return SP
Improvements Now, we only require ?(?2) space at no cost to correctness or runtime. This is the Floyd-Warshall algorithm. The algorithm was developed in 1962, and until 2014, all improvements on it required the graph to hold specific properties.
