Talk:Floyd–Warshall algorithm
 | Mathematics B‑class Mid‑priority | |||||||||
| ||||||||||
 | Computer science B‑class High‑importance | ||||||||||||||||
| |||||||||||||||||
|
|
|
This page has archives. Sections older than 95 days may be auto-archived by Lowercase sigmabot III if there are more than 4. |
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)
Litmus Test =
It was stated when correcting something obviously incorrect in the path allgorithm that since the article was written poorly one should consider this a litmus test.
There is no litmus test. The article should be clearly understandable and correct, and not secret code of a select few. If this is not understtod, 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 was in original version. If you feel pationate enough to insult people, then feel pationate enough to fix the error and to make the correction in the allgorthm clear.
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.
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 rather than . 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)
