Talk:Floyd-Warshall algorithm
From Wikipedia, the free encyclopedia
Contents |
[edit] Change pseudocode to Wikicode?
The pseudocode in this article is very hard to understand. I suggest changing it to something like this:
The following is wikicode, a former proposed standard pseudocode.
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
- Late protest :). The article uses vertices from a set from 1 to n. The above pseudocode/wikicode uses a set from 0 to n. This is confusing. Besides, it is not clear which values the adjacency matrix is supposed to have at [i,j] when there is no edge between two vertices i and j (and how about the value at [i,i]... infinity?). Any idea? Thanks, --Abdull 10:41, 9 March 2006 (UTC)
[edit] 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)
- This is useless without telling us what, exactly, "pred" is is and how it's used. Furthermore, AFAICT, pred is not returned from the function—it just gets updated and then thrown away. Very confusing unless you read the talk page... --Domenic Denicola 07:43, 24 July 2006 (UTC)
[edit] 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)
- I've changed to exactly what you wrote, but I don't know what the correct formatting should be (Infinity, INFINITY, infinity, or what). 203.213.7.132 04:30, 19 June 2006 (UTC)
[edit] Plagiarism?
Just wanted to point out that the paragraph starting "The algorithm is based on the following observation..." is taken almost verbatim from "Introduction to Algorithms Second Edition", Cormen, et al, 2001, p.629. The section is "25.2 The Floyd-Warshall algorithm", third paragraph.
- I'll take care of this (or someone else, earlier). Obvoiously, the one who copied the text had no idea how and why the algorithm works: wikivoodoopedia. mikka (t) 20:58, 15 November 2005 (UTC)
[edit] Redirect
I just put up a redirect from Floyd's algorithm to this article. It was not nearly as advanced as this article, but I saved a C implementation which I have not verified yet:
int floyds(int *matrix) {
int k, i, j;
for (k = 0; k < n; k++)
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (matrix[i][j] > (matrix[i][k] + matrix[k][j]))
matrix[i][j] = matrix[i][k] + matrix[k][j];
}
--Abdull 10:37, 9 March 2006 (UTC)
[edit] Python code?
The article contains a dead link to Python code.
