Talk:Floyd–Warshall algorithm

From Wikipedia, the free encyclopedia

Contents

[edit] 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)

[edit] 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)

[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)
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)

[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)
Really good suggestion!Well done!Visame (talk) 17:30, 7 March 2008 (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)
I think we should also tell the meaning of "Infinity".

Does it mean there is no edgesbetween the two vertices ? ---Visame (talk) 17:37, 7 March 2008 (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.

[edit] 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)

[edit] 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)

Actually, for transitive closure, breadth-first search is quite sufficient. Dcoetzee 22:37, 10 June 2008 (UTC)

[edit] Analysis Section

I just added: Therefore, the complexity of the algorithm is Θ(n3) 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)

[edit] What's the relationship between FolydWarshall and (Gauss-Jordan algorithm)

In the "Applications and generalizations" part, it says: "Inversion of real matrices (Gauss-Jordan algorithm). " is one application of Floyd-Warshall algorithm. I can't figure it out.Can anyone tell me? THANKS!E-mail me:Kankaqi [AT] gmail.comVisame (talk) 17:20, 7 March 2008 (UTC)

[edit] More Explanation on Negative Cycles Needed

I think the "Behaviour with negative cycles" is not clear enough. When there is a negative cycle in the graph,does the output has any meaning? Can anyone explain it?Visame (talk) 17:28, 7 March 2008 (UTC)

[edit] Negative Cycle not defined

Title says it all really. Is a negative cycle one in which every edge is -vely weighted, or is it one in which the overall path length is -ve? —Preceding unsigned comment added by 24.153.207.149 (talk) 00:22, 10 June 2008 (UTC)

Okay, we've had enough questions about negative cycles now that I think this could be expanded. The question is where to do it - I think the most appropriate place is in the general article about shortest path algorithms, and then we can link it from here. The brief answers are: a negative cycle is a cycle with total weight negative, and the behavior of a shortest path algorithm on a graph with negative cycles depends on the algorithm. It may fail to terminate; if it does terminate, it will return a valid result for graphs containing negative cycles, which doesn't make sense because such graphs have no shortest path between any two nodes both reachable from the negative cycle (you can achieve arbitrarily short paths by following the cycle). Dcoetzee 22:31, 10 June 2008 (UTC)