Talk:Floyd–Warshall algorithm

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)

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)

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)

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 Test

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)

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)