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. |
Notation style
WP:MOSMATH exists. Really, it does.
Contrast these:
- , , ,
The above is in this article.
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
intcan'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)
- in position in this variant of the algorithm means that we already know that there is a path between vertices and . If you want to combine paths and (where you would use addition of their lengths in the usual variant), you have to use AND (you can go from to through if there is a path between and AND there is a path between and ). When you try to decide whether there is path through 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 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. Jwesley78 17:03, 23 March 2010 (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)