CODEWITHSUNDEEP
algorithmgraph
Bob Wang
Bob Wang

Reputation: 73

Why does Floyd Warshall's algorithm succeed?

What is to stop a better intermediate path from being found in a later iteration of the outer loop (loops over all possible intermediate vertices) that goes through an earlier one that was already iterated over?

Upvotes: 2

Views: 908

Answers (1)

Ekesh Kumar
Ekesh Kumar

Reputation: 525

I think that you have a misunderstanding of how the Floyd-Warshall algorithm works. For reference, here's an implementation (from https://cp-algorithms.com/graph/all-pair-shortest-path-floyd-warshall.html):

for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]); 
        }
    }
}

The outermost loop does not loop over all intermediate vertices. When computing the shortest path from i to j, the outermost loop defines the set of vertices that can be a part of the path from i to j. In particular, if we label our n vertices 1, 2, 3, ..., n, then the value of k specifies that we can only visit vertices from the set {1, 2, ..., k} on that iteration. You can see that, as k -> n, the d[i][j] values eventually converge to our solution (since a true "shortest path" should be allowed to use any vertex as an intermediate).

Why do we break it down in this manner? Because if we know the solution for a fixed value of k, then we can easily construct the solution for k + 1. This is a key principle of dynamic programming, and you should try to understand how the recurrence d[i][j] = min(d[i][j], d[i][k] + d[k][j]) exhausts all possibilities.

Now to answer your question more directly, it doesn't matter if a newly computed path using the set {1, 2, ..., k} uses the results from the previous iteration of the outermost loop. This is true because the set {1, 2, ..., k - 1} is a subset of {1, 2, ..., k}, so it would be perfectly fine if we did reuse our previously shorted computed path. The key idea is that we have the option to use the newly added vertex k.

Upvotes: 6

Related Questions