HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Can the loops be in any order in the Floyd-Warshall algorithm?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
floydcanorderthewarshallanyloopsalgorithm

Problem

I have a question about the Floyd Warshall algorithm. Here is the code from the Wikipedia page:

let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
for each edge (u, v) do
    dist[u][v] ← w(u, v)  // The weight of the edge (u, v)
for each vertex v do
    dist[v][v] ← 0
for k from 1 to |V|
    for i from 1 to |V|
        for j from 1 to |V|
            if dist[i][j] > dist[i][k] + dist[k][j] 
                dist[i][j] ← dist[i][k] + dist[k][j]
            end if


Our professor told us that the loop for k MUST be outside the i and j loops. I am unable to understand why this must be the case. He said that if k is inside we will only compute the best 2 edged or 1 edge path from i to j. I just don't see it. Can someone help?

Solution

The pseudocode came from Wikipedia and the explanation is in Wikipedia as well. The recurrence is
$dist(i, j, k) = min(dist(i,j,k-1),\ dist(i,k,k-1) + dist(k,j,k-1))$ with the base case $dist(i, j, 0) = w(i, j)$. There is only one way we can achieve this iteratively, by calculating all cases of $k-1$ before calculating cases of $k$. The other answer has an example when this is broken.

Context

StackExchange Computer Science Q#133392, answer score: 2

Revisions (0)

No revisions yet.