Talk:Floyd–Warshall algorithm
Change pseudocode to Wikicode?
The pseudocode in this article is very hard to understand. I suggest changing it to something like this:
function fw(int[0..n,0..n] graph) {
var int[0..n,0..n] dist := graph
for k from 0 to n
for i from 0 to n
for j from 0 to n
if dist[i,j] > dist[i,k] + dist[k,j]
dist[i,j] = dist[i,k] + dist[k,j]
return dist
}
I will change this soon if nobody protests
Predecessor matrix?
Wouldn't it be advantageous to also mention the predecessor matrix Pk[i,j] defined as the predecessor of j on the shortest path from i to j, using internal nodes 1...k? We would add the following to the pseudocode. First initialization:
var int[0..n,0..n] pred
for i from 0 to n
for j from 0 to n
if dist[i,j] > 0
pred[i,j] := i
Next, we add one more line after the "dist[i,j] = dist[i,k] + dist[k,j]" line:
pred[i,j] = pred[k,j]
I'm not entirely sure if this addition would be appreciated. Being a novice Wikipedian, I decided I won't make the addition but rather post it here. If an experienced Wikipedian thinks it's a good addition, please make it.
- I think that's a good idea. IFAIK the "Warshall" part of the algorithm means that it will actually find the paths. If it is used to find just the distances, it should be called just "Floyd's algorithm". I may be wrong. Anyway, I say go ahead and make the changes. --Ropez 28 June 2005 22:11 (UTC)
- It's done. BTW, there seems to be a problem regarding the predecessor assignment statement. See Talk:Floyd-Warshall algorithm/C plus plus implementation for details. --Netvor 30 June 2005 19:25 (UTC)
Predecessor matrix for negative edge weights?
I was wondering how the code must look to get a working predecessor matrix with negative edge weights. The following part of the code seems to consider "0" as "no conection" or does it?
if dist[i,j] > 0
pred[i,j] := i
I personally would rewrite this as something like:
if dist[i,j] < Infinity
pred[i,j] := i
where "Infinity" is used as "There is no connection between these nodes". The C++-implementation gives me the impression this is the right way. -- RealLink 10:39, 2 September 2005 (UTC)