# Optimise Floyd-Warshall for symmetric adjacency matrix

Is there an optimisation that lowers the constant factor of the runtime of Floyd-Warshall, if you are guaranteed to have a symmetric adjacency matrix?

-
Isn't it always symmetric? O_o –  Pavel Shved Jan 10 '10 at 20:26
You can sometimes have directed edges then it isn't symmetric. –  JPvdMerwe Jan 10 '10 at 20:43

After some thought I came up with:

``````for (int k = 0; k < N; ++k)
for (int i = 0; i < N; ++i)
for (int j = 0; j <= i; ++j)
dist[j][i] = dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
``````

Now of course we both need to show it's correct and faster.

Correctness is harder to prove, since it relies on the proof of Floyd-Warshall's which is non-trivial. A pretty good proof is given here: Floyd-Warshall proof

The input matrix is symmetric. Now the rest of the proof uses a modified Floyd-Warshall's proof to show that the order of the calculations in the 2 inner loops doesn't matter and that the graph stays, validly, symmetrical after each step. If we show both of these conditions are true both algorithms do the same thing.

Let's define dist[i][j][k] as the distance from i to j using using only vertices from the set {0, ..., k} as intermediate vertices on the path from i to j. dist[i][j][-1] is defined as the weight of the edge from i to j, if there is no edge this weight is taken to be infinity.

Now using the same logic as used in the proof linked above: dist[i][j][k] = min(dist[i][j][k-1], dist[i][k][k-1] + dist[k][j][k-1])

Now in the calculation of dist[i][k][k] (and similarly for dist[k][i][k]):

dist[i][k][k] = min(dist[i][k][k-1], dist[i][k][k-1] + dist[k][k][k-1])

Now since dist[k][k][k-1] cannot be negative (or we'd have a negative loop in the graph), this means that dist[i][k][k] = dist[i][k][k-1]. Since if dist[k][k][k-1] = 0 then both parameters are the same, otherwise the first parameter of the min() is chosen.

So now, because of the above fact, when calculating dist[i][j][k] it doesn't matter if dist[i][k] or dist[k][j] are already allowing k in their paths or not. Since dist[i][j][k-1] is only used for the calculation of dist[i][j][k], dist[i][j] will stay dist[i][j][k-1] in the matrix till dist[i][j][k] is calculated. If i or j equals k then the above case applies.

Therefore, the order of the calculations doesn't matter.

Now we need to show that dist[i][j] = dist[j][i] after all steps of the algorithm. We start out with a symmetric grid thus dist[a][b] = dist[b][a], for all a and b. dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) = min(dist[j][i], dist[k][i]+dist[j][k]) = min(dist[j][i], dist[j][k]+dist[k][i]) = dist[j][i] Therefore our assignment is both true and it will maintain the invariant that dist[a][b] = dist[b][a]. Therefore dist[i][j] = dist[j][i] after all steps of the algorithm

Therefore both algorithms yield the same, correct, result.

Speed is easier to prove. The inner loop is called just over half the number of times it is normally called, so the function is about twice as fast. Just made slightly slower because you still assign the same number of times, but this doesn't matter as min() is what takes up most of your time.

If you see anything wrong with my proof, however technical, feel free to point it out and I will attempt to fix it.

EDIT:

You can both speed up and save half the memory by changing the loop as such:

``````for (int k = 0; k < N; ++k) {
for (int i = 0; i < k; ++i)
for (int j = 0; j <= i; ++j)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[j][k]);
for (int i = k; i < N; ++i) {
for (int j = 0; j < k; ++j)
dist[i][j] = min(dist[i][j], dist[k][i] + dist[j][k]);
for (int j = k; j <= i; ++j)
dist[i][j] = min(dist[i][j], dist[k][i] + dist[k][j]);
}
}
``````

This just splits up the above for loops of the optimised algorithm, so it's still correct and it'll likely get the same speed, but uses half the memory.

Thanks to Chris Elion for the idea.

-
Feel free to vote me up if you liked the answer :) –  celion Jan 11 '10 at 22:07
just a note that the two codes above do not produce the same result experimentally. –  WhitAngl Jun 11 at 15:30
the first update in the second code should be: dist[i][j] = min(dist[i][j], dist[k][i] + dist[k][j]); the second update should be: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); the third update is correct. –  WhitAngl Jun 11 at 15:41
Are there any other improvements that can be made with the 2nd code assuming undirected and unweighted? –  Ryan Jun 30 at 20:22

(Using the notation in the pseudo-code in the Wikipedia article) I believe (but haven't tested) that if the edgeCost matrix is symmetric, then the path matrix will also be symmetric after each iteration. Thus you only need to update half of the entries at each iteration.

At a lower level, you only need to store half of the matrix (since d(i,j) = d(j,i)), so you can reduce the amount of memory used, and hopefully reduce the number of cache misses since you'll access the same data multiple times.

-
The content of the passage is a discussion about optimizing the Floyd-Warshall algorithm for a symmetric adjacency matrix, including a proposed optimized algorithm and a proof of its correctness and efficiency.
no_question

the passage does not contain a direct mathematical question that requires a numerical or symbolic answer. instead, it is a discussion and explanation of an optimization technique for an algorithm.
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# Optimise Floyd-Warshall for symmetric adjacency matrix

Is there an optimisation that lowers the constant factor of the runtime of Floyd-Warshall, if you are guaranteed to have a symmetric adjacency matrix?

-
Isn't it always symmetric? O_o –  Pavel Shved Jan 10 '10 at 20:26
You can sometimes have directed edges then it isn't symmetric. –  JPvdMerwe Jan 10 '10 at 20:43

After some thought I came up with:

``````for (int k = 0; k < N; ++k)
for (int i = 0; i < N; ++i)
for (int j = 0; j <= i; ++j)
dist[j][i] = dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
``````

Now of course we both need to show it's correct and faster.

Correctness is harder to prove, since it relies on the proof of Floyd-Warshall's which is non-trivial. A pretty good proof is given here: Floyd-Warshall proof

The input matrix is symmetric. Now the rest of the proof uses a modified Floyd-Warshall's proof to show that the order of the calculations in the 2 inner loops doesn't matter and that the graph stays, validly, symmetrical after each step. If we show both of these conditions are true both algorithms do the same thing.

Let's define dist[i][j][k] as the distance from i to j using using only vertices from the set {0, ..., k} as intermediate vertices on the path from i to j. dist[i][j][-1] is defined as the weight of the edge from i to j, if there is no edge this weight is taken to be infinity.

Now using the same logic as used in the proof linked above: dist[i][j][k] = min(dist[i][j][k-1], dist[i][k][k-1] + dist[k][j][k-1])

Now in the calculation of dist[i][k][k] (and similarly for dist[k][i][k]):

dist[i][k][k] = min(dist[i][k][k-1], dist[i][k][k-1] + dist[k][k][k-1])

Now since dist[k][k][k-1] cannot be negative (or we'd have a negative loop in the graph), this means that dist[i][k][k] = dist[i][k][k-1]. Since if dist[k][k][k-1] = 0 then both parameters are the same, otherwise the first parameter of the min() is chosen.

So now, because of the above fact, when calculating dist[i][j][k] it doesn't matter if dist[i][k] or dist[k][j] are already allowing k in their paths or not. Since dist[i][j][k-1] is only used for the calculation of dist[i][j][k], dist[i][j] will stay dist[i][j][k-1] in the matrix till dist[i][j][k] is calculated. If i or j equals k then the above case applies.

Therefore, the order of the calculations doesn't matter.

Now we need to show that dist[i][j] = dist[j][i] after all steps of the algorithm. We start out with a symmetric grid thus dist[a][b] = dist[b][a], for all a and b. dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) = min(dist[j][i], dist[k][i]+dist[j][k]) = min(dist[j][i], dist[j][k]+dist[k][i]) = dist[j][i] Therefore our assignment is both true and it will maintain the invariant that dist[a][b] = dist[b][a]. Therefore dist[i][j] = dist[j][i] after all steps of the algorithm

Therefore both algorithms yield the same, correct, result.

Speed is easier to prove. The inner loop is called just over half the number of times it is normally called, so the function is about twice as fast. Just made slightly slower because you still assign the same number of times, but this doesn't matter as min() is what takes up most of your time.

If you see anything wrong with my proof, however technical, feel free to point it out and I will attempt to fix it.

EDIT:

You can both speed up and save half the memory by changing the loop as such:

``````for (int k = 0; k < N; ++k) {
for (int i = 0; i < k; ++i)
for (int j = 0; j <= i; ++j)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[j][k]);
for (int i = k; i < N; ++i) {
for (int j = 0; j < k; ++j)
dist[i][j] = min(dist[i][j], dist[k][i] + dist[j][k]);
for (int j = k; j <= i; ++j)
dist[i][j] = min(dist[i][j], dist[k][i] + dist[k][j]);
}
}
``````

This just splits up the above for loops of the optimised algorithm, so it's still correct and it'll likely get the same speed, but uses half the memory.

Thanks to Chris Elion for the idea.

-
Feel free to vote me up if you liked the answer :) –  celion Jan 11 '10 at 22:07
just a note that the two codes above do not produce the same result experimentally. –  WhitAngl Jun 11 at 15:30
the first update in the second code should be: dist[i][j] = min(dist[i][j], dist[k][i] + dist[k][j]); the second update should be: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); the third update is correct. –  WhitAngl Jun 11 at 15:41
Are there any other improvements that can be made with the 2nd code assuming undirected and unweighted? –  Ryan Jun 30 at 20:22

(Using the notation in the pseudo-code in the Wikipedia article) I believe (but haven't tested) that if the edgeCost matrix is symmetric, then the path matrix will also be symmetric after each iteration. Thus you only need to update half of the entries at each iteration.

At a lower level, you only need to store half of the matrix (since d(i,j) = d(j,i)), so you can reduce the amount of memory used, and hopefully reduce the number of cache misses since you'll access the same data multiple times.

-
user
The content of the passage is a discussion about optimizing the Floyd-Warshall algorithm for a symmetric adjacency matrix, including a proposed optimized algorithm and a proof of its correctness and efficiency.

TYPE: NO_QUESTION

The passage does not contain a direct mathematical question that requires a numerical or symbolic answer. Instead, it is a discussion and explanation of an optimization technique for an algorithm.