Talk:Floyd–Warshall algorithm/Archive 1

Archive 1

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:

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)

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)

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)

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];
}

--Abdull 10:37, 9 March 2006 (UTC)

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)

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

Analysis Section

I just added: Therefore, the complexity of the algorithm is $\Theta ({n}^{3})$ 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)

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)

C Implementation

I thought I'd get rid of the explanation of how the "C" implementation really doesn't use any C++ paradigms. Does anyone think that is necessary info? I'm actually the guy who wrote the linked-to document (thanks to whoever found my page!) so I'm willing to change the linked-to page as well if anyone has suggestions. Pandemias (talk) 06:17, 19 June 2008 (UTC)

Python code?

The article contains a dead link to Python code. — Preceding unsigned comment added by 151.41.185.206 (talk) 19:07, 1 July 2006 (UTC)

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)

In my opinion an article about "Negative Cycles" is needed, it could then elaborate on algorithms commonly used for such thing such as this one and the Bellman-Ford algorithm and this page could link to that article instead.Vexorian (talk) 13:12, 17 January 2009 (UTC)

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)

Basically, there is no solution to the shortest-path problem in a graph with negative cycles any machine can represent. You can think of it as the following: Assume you have a cycle C in a graph, and the overall sum of edge weights of this cycle is W. Furthermore, assume that this cycle contains a vertex V. If you now consider a path which goes like v_1, v_2, ..., V, ..., v_n, with an overall path weight P, then you can extend this path as follows: v_1, v_2, ..., V, C, V, ..., v_n. This works, since V is contained in the circle C, and thus, you can walk through the circle and end up at V again. Clearly, we can repeat this as much as we want, so v_1, ..., V, C, ..., C, V, ..., v_n, with as many C's as one likes all are still good paths through the graph. Now, consider the overall weight of these expanded paths. Without the circles, the overall weight of the path was P, but now, with one circle added to expand the graph, the new weight will be P + W, or, with K cycles added into the path, the new weight will be P + K*W. Now there are two cases: If W is positive (W > 0), then it clearly holds that P < P + W < P + 2*W < ..., thus, a correct shortest path algorithm will ignore them. However, if W is negative (W < 0), then it clearly holds that P > P + W > P + 2*W, ..., as you subtract more, and more and more from the path length. Thus, there exists no shortest path in this graph, as for whatever path you declare the shortest one, I can construct a shorter path by using P and adding enough repetitions of the circle into P. Now, Floyd-Warshall is one of the nicer algorithms to handle this, as Floyd-Warshall just stops after a certain number of iterations and outputting paths with a certain negative weight, because the number of edges on a path considered by the Floyd-Warshall-algorithm is bounded, thus, the output is wrong (even though, as the article states, negative cycles can be detected by checking the diagonal elements: dist[v][v] describes the weight of circles containing V, which is exactly what I described earlier). I hope this helps, and if it does, it can be added to the article (Probably with a nice image to make it really clear) --Tetha (talk) 14:02, 3 September 2009 (UTC)

FW no longer in the c++ boost library

They currently only list the Johnson algorithm, no FW (presumably because it's slower). I think if I blindly removed the link from the page it would get rv'd quickly. 134.173.201.55 (talk) 09:08, 13 April 2009 (UTC)

Notation style

WP:MOSMATH exists. Really, it does.

Contrast these:

${\mathcal {W}}_{1}$, ${\mathcal {W}}_{2}$, $...$, ${\mathcal {W}}_{\mathit {n}}={\mathcal {M}}_{{\mathcal {R}}^{*}}$

The above is in this article.

${\mathcal {W}}_{1},{\mathcal {W}}_{2},\dots ,{\mathcal {W}}_{\mathit {n}}={\mathcal {M}}_{{\mathcal {R}}^{*}}$

The second one is standard style.

Are there really some people who are not instantly offended by the first form? Why do people do things like that? Michael Hardy (talk) 14:02, 22 July 2009 (UTC)

Haha, seriously? Well, as the person who wrote the first version, I'm very "offended" that you would rather complain than just fix the article. Not all of us are up to date on obscure Wikipedia style rules. :P 132.228.195.207 (talk) 16:12, 7 August 2009 (UTC)

I've done some fixing of the article and I'll be back for more.

It doesn't take any familiarity with Wikipedia style conventions to be offended by what the first version above looks like. Michael Hardy (talk) 17:51, 9 November 2009 (UTC)

Update Pseudocode/change to Java?

The pseudocode is not that readable/self-explanatory. Also, it does not include how to find the path between two vertices (though there's now a description below it).

How would it be to update the psuedocode, including a change to demonstrate finding the path? Alternatively, what about replaceing the psuedo code with Java code like what I posted a few edits ago? I think the Java code is easier for an average reader to read/understand than this psuedocode is (even without knowledge of Java), but I'm not too familiar with Wikipedia's pseudocode conventions. luv2run (talk) 01:56, 30 November 2009 (UTC)

I'm the one who deleted your code. I think that it is too long and that pseudocode is better for this purpose. I don't know about any pseudocode conventions (and I couldn't find any either). What do you think is difficult to understand in that code?

I think that in theory, the task is usually given as “find the length of the shortest path”. In practice, the path itself is usually required as well. I think that because of this, the code should only find the length (as it currently does) with a note how to find the path, but I'm not that sure about this.

Also, as a note, your code isn't correct, because Java's int can't have a value of infinity. But this is of course very easy to fix and isn't an argument against it. Svick (talk) 02:32, 30 November 2009 (UTC)

True, thanks. On the current version, I don't like the syntax much, especially the { }^2, and also just think the inner loop isn't as self-explanatory as it should be. I'd rather make it a little longer to show what it actually does, or comment more. Like in the java I had, naming a variable length_thru_k, then comparing it to the current path length.

The java code was a little long, I agree, but half of it was an example showing how to recover the path. I don't know if the explanation we have now is sufficient to explain how to recover the path or not. Hard to tell ... maybe I'll see if I can come up with something a little more compact in psuedocode, C, or Java, and post it here. I guess the problem is it seems redundant to have a separate section for finding the path, but insufficient to have a brief description. Thoughts on that?luv2run (talk) 02:47, 30 November 2009 (UTC)

I agree that the pseudocode as presented isn't that great, but I greatly prefer pseudocode to java (or any other programming language). The whole point of having pseudocode is so that we can avoid the messiness of a particular programming language and state the algorithm as clearly as possible. --Robin (talk) 02:57, 30 November 2009 (UTC)

How does this look?

 1 int path[][];
 2 /* path is dimension n by n, where n is the number of vertices.
 3    Initially, path[i][j] is the length of an edge from i to j, or infinity if there is no edge.
 4    path[i][i] is zero, the length from any vertex to itself.
 5    After running the algorithm, path[i][j] will have the length of the shortest path from i to j. */
 6 
 7 procedure FloydWarshall ()
 8    for k := 1 to n
 9       /* Pick whichever is shorter: the path we already have from i to j,
10          or the path from i to k, then from k to j (a path from i to j through k). */
11       for each pair of nodes (i,j)
12          int length_thru_k := path[i][k]+path[k][j];
13          if length_thru_k < path[i][j] then
14             path[i][j] := length_thru_k

Additionally, we could easily demonstrate remembering the path by adding the appropriate array and statement under the if. Like so (the second procedure, GetPath, maybe not necessary?)

 1 int path[][];
 2 /* path is dimension n by n, where n is the number of vertices.
 3    Initially, path[i][j] is the length of an edge from i to j, or infinity if there is no edge.
 4    path[i][i] is zero, the length from any vertex to itself.
 5    After running the algorithm, path[i][j] will have the length of the shortest path from i to j. */
 6 
 7 int goes_thru[][];
 8 /* Initally, goes_thru[i][j] is set to (for example) -1, indicating no intermediate vertices.
 9    When we find a path from i to j passing through k, we save it here by setting goes_thru[i][j]
10    equal to k. This will allow us to recover the path from i to j. */
11 
12 procedure FloydWarshall ()
13    for k := 1 to n
14       /* Pick whichever is shorter: the path we already have from i to j,
15          or the path from i to k, then from k to j (a path from i to j through k). */
16       for each pair of nodes (i,j)
17          int length_thru_k := path[i][k] + path[k][j];
18          if length_thru_k < path[i][j] then
19             path[i][j] := length_thru_k;
20             goes_thru[i][j] := k;
21
22 procedure GetPath (i,j)
23    if path[i][j] equals infinity then
24       return "no path";
25    int intermediate := goes_thru[i][j];
26    if intermediate equals -1 then
27       return " ";   /* there is an edge from i to j, with no vertices between */
28    else
29       return GetPath(i,intermediate) + intermediate + GetPath(intermediate,j);

Let me know what you think. Thanks guys. -luv2run (talk) 03:55, 30 November 2009 (UTC)

The presented pseudocode does not solve the problem correctly as given in the recursive formula. The recursive formula definitely says, that by calculating ANY value for a given k, we only use values of k-1. In your code for calculating the new value for position [i][j] you are using values, that already have been overwritten during this iteration (k). This gives wrong results. Do you agree with this? —Preceding unsigned comment added by 77.11.155.186 (talk) 00:19, 23 February 2011 (UTC)

Applications and generalizations

• Transitive closure of directed graphs (Warshall's algorithm). In Warshall's original formulation of the algorithm, the graph is unweighted and represented by a Boolean adjacency matrix. Then the addition operation is replaced by logical conjunction (AND) and the minimum operation by logical disjunction (OR).

I think the AND and OR operations are mixed up here. AND would result in 0 for all pairs except 1,1 which is the only pair with a minimum of 1, and OR is the logical operator for addition. Didn't want to change the main page b/c I don't actually know for sure if this is correct but it struck me as wrong when I saw it. -rockychat3 —Preceding unsigned comment added by 209.94.128.120 (talk) 04:56, 1 December 2009 (UTC)

$1$ in position $(i,j)$ in this variant of the algorithm means that we already know that there is a path between vertices $i$ and $j$. If you want to combine paths $i\rightarrow k$ and $k\rightarrow j$ (where you would use addition of their lengths in the usual variant), you have to use AND (you can go from $i$ to $j$ through $k$ if there is a path between $i$ and $k$ AND there is a path between $k$ and $j$). When you try to decide whether there is path through $k$ OR “direct” (i.e. one we already know) path, you use OR. The difference stems from the fact that “no path” is represented as infinity in the usual algorithm, but as $0$ in this variant. Svick (talk) 11:31, 1 December 2009 (UTC)

Undirected Graphs

Weighted undirected graphs are equally capable of being solved by the Floyd-Warshall algorithm though some small changes are needed to gain further optimization. I've made the changes to have the article reflect that fact. AlexandreZ (talk) 16:13, 23 March 2010 (UTC)

Undirected graphs are essentially a special case for directed graphs, especially sine F-W works only with the incidence matrix. You're right that one can optimize away half of the comparisons if you know beforehand that the graph is undirected. However, I think that this detail is not needed, nor is that optimization commonly used. Jwesley₇₈ 17:03, 23 March 2010 (UTC)

An undirected graph must have no negative cycles to have well-defined shortest paths. It would be exceedingly strange to use Floyd-Warshall instead of running Dijkstra from all vertices on a graph with non-negative weights. Dcoetzee 21:02, 19 December 2012 (UTC)

Java examples

I explored both examples of the FW algorithm implemented in Java. The one in commons.apache.org is a link into the source tree of a long-dormant project that never achieved release status, is very poorly documented, and is nearly impenetrable without a long exploration of the source tree. (In fairness, it is architected as an element of a library.) The one on AlgoWiki is straightforward and simple, with the supporting code readily available.

I propose that we remove the reference to the commons example from the article body. If you don't want to lose the reference, put it in the exterior links section, or as a ref. Dmforcier (talk) 18:36, 8 August 2010 (UTC)

I don't think those links should be in the article body at all. Few of them should be moved to External links, and the rest deleted. Svick (talk) 20:21, 8 August 2010 (UTC)

First sentence

The article begins, "In Computer Science...". Doesn't this seem a bit pretentious and misleading? Floyd-Warshall's Algorithm has many different and unique applications, and it is certainly neither confined to the field of computer science nor dependent on computer science. If such a presumptive lead-in is to be used--I don't see a need for such a one, in my opinion it's unnecessary--then the most generalized, pure categorization should be used, e.g. "In Graph Theory..." or, "In Mathematics...". Cheers. — Preceding unsigned comment added by 71.12.211.253 (talk) 21:45, 12 June 2012 (UTC)

It's standard for Mathematics and Computer Science articles to begin with "In <field of study>...". And this article is about an algorithm! The algorithm computes the length of the shortest path between any two vertices, but I don't think that beginning the article with "in graph theory" would be more accurate. Justin W Smith ^talk/_stalk 03:05, 13 June 2012 (UTC)

Optimization in Pseudocode

I've removed the optimization from the pseudocode. The point of pseudocode is not to show the most efficient method possible, but rather to illustrate how the algorithm works. It is expected that programmers will take simple optimizations into account. Stargazer7121 (talk) 21:39, 8 February 2013 (UTC)

Negative Cycles

In my opinion the section about negative cycles is wrong in the sense that it is stated that there is no shortest path, because traversing the cycles multiple times makes the length arbitrarily small. But in the context of shortest paths one usually talks about (simple) paths and not walks, i.e., multiple traversal is not allowed. And then of course (since there are only finitely many simple paths), a shortest path is well-defined. In this case, the algorithm just fails since the concatenation of the shortest i-(k+1)-path and the shortest (k+1)-j-path (both using only vertices 1 up to k as inner vertices) does not necessarily result in a simple path since it may contain a cycle.

MatthiasWalter (talk) 08:51, 10 December 2013 (UTC)

Path reconstruction Incorrect

The Path reconstruction pseudocode never populates the 'next' variable with anything but null and so it cannot find any paths. 67.172.248.52 (talk) 16:19, 14 October 2013 (UTC)

This section has undergone several iterations since this comment was made. 98.209.119.23 (talk) 22:05, 29 April 2014 (UTC)

Simpler path reconstruction

I have changed the path reconstruction such that the next array is updated in the main loop. This saves us the trouble of using extra procedures and illustrates a common dynamic programming pattern. Thomasda (talk) 20:31, 19 May 2014 (UTC)

Floyd's and Warshall's algorithms are not the same!

The article as it is now completely misses the point of Warshall's contribution!

The point of Warshall's note (see references) is not to introduce Floyd's algorithm or any other variant based on elementwise operations - it is to use bit vector operations to achieve a running time of $O(n^{2})$ rather than $O(n^{3})$. So Warshall's use of a Boolean matrix to represent the graph is not a minor implementation detail, it is essential to his contribution, and without it, the algorithm shouldn't carry his name. Rp (talk) 14:38, 3 September 2014 (UTC)

Litmus Testing

My correction of the Floyd Algorithm are correct. The entire artcle needs a rewrite to be both understandable and correct. As it remains, it is confusing my students and I spend a lot of time correcting their errors gleaned from this article. This is a simple to understand algorithm when explained clearly. Instead we don't only have mathematical snobbery, but truly inaccurate information. I am SICK of wikipeadia inability to just tell wrong from write. Mathematical truth is not a matter of a VOTE. When k = 1, it is not equal to zero. Fixing this page requires a complete rewrite because the graph and the agorthms don't match and the explanation doesn't inform the reader of facts. Not having fixed these problems in the article has been called not passing a litmus test. The only litmus test here is if the article is informative and educational. It is NOT. — Preceding unsigned comment added by 96.57.23.82 (talk) 02:16, 17 May 2015 (UTC) — Preceding unsigned comment added by 96.57.23.82 (talk)

Litmus Test

My correction of the Floyd Allgorthm are correct. The entire artcle needs a rewrite to be both understandalb eand correct. As it remains, it is confusing my students and I spend a lot of time correcting their errors gleened from this article. This is a simple to undertand allgorithm when explained clearly. Instead we don't only have mathmatical snobbery, but truly inacuate information. I am SICK of wikipeadia inability to just tell wrong from write. Mathmatical truth is not a matter of a VOTE. When k = 1, it is not equal to zero. Fixing this page requires a complete rewrite because the graph and the agorthms don't match and the explaination doesn't inform the reader of facts. Not having fixed these problems in the article has been called not passing a litmus test. The only litmus test here is if the article is informatative and educational. It is NOT. — Preceding unsigned comment added by 96.57.23.82 (talk) 02:17, 17 May 2015 (UTC)

It was stated when correcting something that was obviously incorrect in the path allgorithm, one should consider understanding the poorly written article as a "litmus test."

There is no litmus test. The article should be written clearly. It should be understandable and correct. It is not secret code for a select few. If this is not understood, David Esptein, then it is time for you to take some time off of wikipedia editing and do something else, like create the secret society of the Knights templer, or whatever.

Do not reverse the correction without a clear explanation of the ERROR that fixed the original version. If you feel passionate enough to insult people, then feel passionate enough to fix the error and to make the correction in the algorithm clear. Stop vandalizing the page — Preceding unsigned comment added by 96.57.23.82 (talk • contribs)

Please see WP:COMPETENCE and please stop editing this article until you actually understand the algorithm. To be specific, the kth stage of the algorithm finds paths whose interior vertices form a subset of the set of numbers from 1 to k. The first stage finds paths whose interior vertices belong to the singleton set {1}, the second stage finds paths whose interior vertices belong to the set {1,2}, the third stage finds paths whose interior vertices belong to the set {1,2,3}, etc. For some reason this IP editor insists on replacing the set {1,2,3} by the number 3 in this description. It is an incorrect change, the article is correct as-is, and my repeated attempts at explanation (in the edit summaries) have fallen on deaf ears. —David Eppstein (talk) 22:58, 16 May 2015 (UTC)

Your not listening. The problem isn't that the set of vertices is wrong, the problem is that the material is NOT consistant and therefore confuses the STUDENT. The Graph has to match the Allgorithm and mathc the equation. You have to SAY what you mean. In this case it does not SAY what it means, nor does it say what you said.

It is just a pile of nonsense. — Preceding unsigned comment added by 96.57.23.82 (talk) 06:07, 17 May 2015 (UTC)

I actually understand the article very well and there is no excuse for your attitude or for your confusing readers. I was teaching this algorithm probably when you were in High School. If you can't write it clearly, then take time off and stop vandalizing the article. — Preceding unsigned comment added by 96.57.23.82 (talk) 23:04, 16 May 2015 (UTC)

Actually, while we are the topic of High School, there is nothing inherently difficult about this topic. This graph vertex algorithm can be understand by any high school student, and most junior high school students. There problem with this article is that it is written sloppily and like garbage. It is confusing, full of unnecessarily jargon, and an impedance to actually understanding the topic. The entire thing needs a rewrite.

Dear non-account user, a request: before going back and making the same edit again, could we instead try to find common understanding? In particular, what do you think the symbols "{1,2,3}" represent? --JBL (talk) 01:21, 17 May 2015 (UTC)

there is no need to "know" what it means because it says what it is, aand what it says is WRONG. In fact, the __entire__ article is wrong.

1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity) 2 for each vertex v 3 dist[v][v] ← 0 4 for each edge (u,v) 5 dist[u][v] ← w(u,v) // the weight of the edge (u,v) 6 for k from 1 to |V| 7 for i from 1 to |V| 8 for j from 1 to |V| 9 if dist[i][j] > dist[i][k] + dist[k][j] 10 dist[i][j] ← dist[i][k] + dist[k][j] 11 end if

Example

The algorithm above is executed on the graph on the left below:

Floyd-Warshall example.svg

Note - you have an EXMAMPLE pf K=0 K NEVER equals zero ... K starts at 1.

Prior to the first iteration of the outer loop, labeled k=0 above,

Yeah - that si WRONG, k is 1.

the only known paths correspond to the single edges in the graph. At k=1, paths that go through the vertex 1 are found: in particular, the path 2→1→3 is found, replacing the path 2→3 which has fewer edges but is longer. At k=2, paths going through the vertices {1,2} are found. The red and blue boxes show how the path 4→2→1→3 is assembled from the two known paths 4→2 and 2→1→3 encountered in previous iterations, with 2 in the intersection. The path 4→2→3 is not considered, because 2→1→3 is the shortest path encountered so far from 2 to 3. At k=3, paths going through the vertices {1,2,3} are found.

WRONG, the paths do NOT go through that set.

Finally, at k=4, all shortest paths are found.

So the whole thing needs a rewrite. Try starting with Cormen.... — Preceding unsigned comment added by 96.57.23.82 (talk) 01:30, 17 May 2015 (UTC)

Your post is not really comprehensible -- possibly, if you want your comments to be taken seriously, you should take some time and write a few clear sentences laying out exactly what you think the incorrect statement is and why you believe it to be incorrect. As it is I am not able to understand either of these things from your comments. (Also, it really might help if you would answer the question that I asked.) --JBL (talk) 01:37, 17 May 2015 (UTC)

Since it quotes the article, it is not surprising that it is hard to understand. As it is, it is clear. The algorithm in the code doesn't match diagram, and the diagram doesn't match the text. This whole article needs a rewrite. Perhaps the esteemed Professor of Univ Irvine can donate his class notes. — Preceding unsigned comment added by 96.57.23.82 (talk) 01:41, 17 May 2015 (UTC)

Follow Cormen if you need to The structure of a shortest path In the Floyd-Warshall algorithm, we use a different characterization of the structure of a shortest path than we used in the matrix-multiplication-based all-pairs algorithms. The algorithm considers the "intermediate" vertices of a shortest path, where an intermediate vertex of a simple path p = 〈 v , v , . . . , v 〉 is any vertex of p other than 1 2 lv or v , that is, any vertex in the set {v ,v , . . . , v }. 1 l 2 3 l-1The Floyd-Warshall algorithm is based on the following observation. Let the vertices of G be V = {1, 2, . . . , n}, and consider a subset {1, 2, . . . , k} of vertices for some k. For any pair of vertices i, j ∈ V, consider all paths from i to j whose intermediate vertices are all drawn from {1, 2, . . . , k}, and let p be a minimum-weight path from among them. (Path p is simple, since we assume that G contains no negative-weight cycles.) The Floyd- Warshall algorithm exploits a relationship between path p and shortest paths from i to j with all intermediate vertices in the set {1, 2, . . . , k - 1}. The relationship depends on whether or not k is an intermediate vertex of path p. Figure 26.3 Path p is a shortest path from vertex i to vertex j, and k is the highest-numbered intermediate vertex of p. Path p1 , the portion of path p from vertex i to vertex k, has all intermediate vertices in the set {1, 2, . . . , k – 1}. The same holds for path p2 from vertex k to vertex j. • If k is not an intermediate vertex of path p, then all intermediate vertices of path p are in the set {1, 2, . . . , k – 1}. Thus, a shortest path from vertex i to vertex j with all intermediate vertices in the set {1, 2, . . . , k – 1} is also a shortest path from i to j with all intermediate vertices in the set {1, 2, . . . , k}. • If k is an intermediate vertex of path p, then we break p down into

as shown in Figure 26.3

. By Lemma 25.1, p1 is a shortest path from i to k with all intermediate vertices in the set {1, 2, . . . , k}. In fact, vertex k is not an intermediate vertex of path p1 , and so p1 is a shortest path from i to k with all intermediate vertices in the set {1, 2, . . . , k - 1}. Similarly, p2 is a shortest path from vertex k to vertex j with all intermediate vertices in the set {1, 2, . . . , k - 1}.

A recursive solution to the all-pairs shortest-paths problem Based on the above observations, we define a different recursive formulation of shortest-path estimates than we did in Section 26.1. Let

be the weight of a shortest path from vertex i to vertex j with all intermediate vertices in

the set {1, 2, . . . , k}. When k = 0, a path from vertex i to vertex j with no intermediate vertex numbered higher than 0 has no intermediate vertices at all. It thus has at most one edge, and hence

. A recursive definition

is given by (26.5) The matrix

gives the final answer—

are in the set {1, 2, . . . , n}. for all i, j ∈ Vbecause all intermediate vertices Computing the shortest-path weights bottom up Based on recurrence (26.5), the following bottom-up procedure can be used to compute the values

in order of

increasing values of k. Its input is an n × n matrix W defined as in equation (26.1). The procedure returns the matrix D(n) of shortest-path weights. Figure 26.4 shows a directed graph and the matrices D (k) computed by the Floyd-Warshall algorithm. The running time of the Floyd-Warshall algorithm is determined by the triply nested for loops of lines 3-6. Each execution of line 6 takes O(1) time. The algorithm thus runs in time Θ(n3). As in the final algorithm in Section 26.1 , the code is tight, with no elaborate data structures, and so the constant hidden in the Θ -notation is small. Thus, the Floyd-Warshall algorithm is quite practical for even moderate-sized input graphs. Constructing a shortest path There are a variety of different methods for constructing shortest paths in the Floyd-Warshall algorithm. One way is to compute the matrix D of shortest-path weights and then construct the predecessor matrix Π from the D matrix. This method can be implemented to run in O(n3 ) time (Exercise 26.1-5). Given the predecessor matrix Π, the PRINT- ALL- PAIRS- SHORTEST- PATH procedure can be used to print the vertices on a given shortest path. We can compute the predecessor matrix Π "on-line" just as the Floyd-Warshall algorithm computes the matrices D (k) . Specifically, we compute a sequence of matrices Π(0) , Π(1) , . . . , Π(n), where Π = Π(n) and

is

defined to be the predecessor of vertex j on a shortest path from vertex i with all intermediate vertices in the set {1, 2, . . . , k}. We can give a recursive formulation of vertices at all. Thus, . When k = 0, a shortest path from i to j has no intermediate Figure 26.4 The sequence of matrices D (k) and Π(k) computed by the Floyd-Warshall algorithm for the graph in Figure 26.1 . — Preceding unsigned comment added by 96.57.23.82 (talk) 02:07, 17 May 2015 (UTC)

I am new to wikipedia authoring, but whether or not the article is clear the pseudo-code is incorrect. On line 9 there is a > symbol where there should be a < symbol. Being new I thought I would talk about it on this page before diving in and correcting it Philsrice (talk) 08:28, 14 August 2015 (UTC)

Is there a bug in the main loop?

Should the main loop for updating the 'next' matrix instead of looking like:

   next[i][j] ← next[i][k]

be

   next[i][j] ← next[i][k]
   next[j][i] ← next[j][k]

? I have been random fuzz testing the algorithm in Python and occasionally get a wrong path which appears fixed with the additional line. — Preceding unsigned comment added by Shane.magrath (talk • contribs) 08:03, 17 April 2018 (UTC)