patternMinor
Why doesn't the Floyd-Warshall algorithm work if I put k in the innermost loop
Viewed 0 times
floydwhythewarshallloopputalgorithminnermostdoesnwork
Problem
The Floyd-Warshall algorithm is defined as follows:
Why doesn't it work if I simply use
In this case, the intermediate node k is iterated in the innermost loop. I expect it will make the same comparisons, but maybe different order. Why is the result different and incorrect?
for k from 1 to |V|
for i from 1 to |V|
for j from 1 to |V|
if dist[i][k] + dist[k][j] < dist[i][j] then
dist[i][j] ← dist[i][k] + dist[k][j]Why doesn't it work if I simply use
for i from 1 to |V|
for j from 1 to |V|
for k from 1 to |V|
if dist[i][k] + dist[k][j] < dist[i][j] then
dist[i][j] ← dist[i][k] + dist[k][j]In this case, the intermediate node k is iterated in the innermost loop. I expect it will make the same comparisons, but maybe different order. Why is the result different and incorrect?
Solution
Take $i - 1$ and $j = 2$. The algorithm is trying to find the shortest path between $1$ and $2$, by considering intermediate vertices. But at this point, most of the array dist is infinity, so we don't even find that $2$ is reachable from $1$ unless the distance is $1$ or $2$.
Context
StackExchange Computer Science Q#9636, answer score: 6
Revisions (0)
No revisions yet.