Talk:Floyd–Warshall algorithm
Inconsistent article
The description of the algorithm is not consistent with the pseudocode. Either change the description to an algorithm that finds if there are paths between vertices (if this is what the Floyd-Warshall is about), or change the pseudocode to something that actually matches the algorithm description.
- I agree on this, article does not explain Floyd-Warshall algorithm. The description of predecessor matrix has been left out. From a search through older revisions, it seems to me that article is better before an edit which claims to have generalized the psuedocode to a more formal notation. Look at http://en.wikipedia.org/w/index.php?title=Floyd-Warshall_algorithm&diff=106667395&oldid=106657377 --Tomash 19:27, 14 May 2007 (UTC)
Is the code correct?
In my view, the pseudocode just calculates if there are paths between vertexes. I think I can reconstruct the path length as minimal k where w(k)[i,j]=1, but this is kind of confusing. Is there some reason for this. I would suggest to replace/accompany it with the code below Jirka6 04:04, 25 February 2007 (UTC)
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
- 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)
- The whole ideea of roy-floyd algorithm is that the whole dist[i,j] matrix contains only infinity at first, then the graph is copyed upon it, changing for known vertices the distance. So there should be a change at the initialization part--Tudalex 17:51, 23 March 2007 (UTC)
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)
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)
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)
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];
}
Python code?
The article contains a dead link to Python code.
How does this look?
I found the original article confusing and hard to read. I've changed it to reflect the way I was taught FW, which I think is more comprehensible. Any suggestions? Hjfreyer 23:06, 7 April 2007 (UTC)
Wouldn't Dijkstra's algorithm be better for transitive closure?
It seems like a better way to calculate the transitive closure of a graph would be to apply Dijkstra's algorithm starting at each vertex. Since you do not need the Extract-Min function at each step, since you don't care about finding the minimum path, you can do each vertex in O(e) time, or a total of O(ve). This is better than O(v^3) especially for sparse graphs. Alex319 17:47, 6 June 2007 (UTC)
Analysis Section
I just added: Therefore, the complexity of the algorithm is and can be solved by a deterministic machine in polynomial time. to the analysis section. Does this need any further explanation? It feels like I would be just taking stuff from other articles if I started describing it further. fintler 01:06, 11 October 2007 (UTC)
