Talk:Floyd–Warshall algorithm: Difference between revisions

Revision as of 17:03, 23 March 2010

Latest revision as of 00:41, 9 March 2024

(82 intermediate revisions by 33 users not shown)

Line 1:

{{mathsWikiProject ratingbanner shell|class=B|priorityvital=Midyes|field1=discrete}}

{{WikiProject Mathematics|priority=Mid}}

{{WikiProject Computer science|importance=high}}

}}

{{User:MiszaBot/config

|archiveheader = {{talkarchivenav}}

Line 8 ⟶ 11:

|archive = Talk:Floyd–Warshall algorithm/Archive %(counter)d

}}

{{WikiProject Computing|class=|importance=}}

{{archives}}

== [[File:Pictogram voting question.svg|20px|link=|alt=]] '''Question:'''<!-- Template:ESp --> Is the main function correct? ==

== More Explanation on Negative Cycles Needed ==

Where it appears:

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

Should it be?:

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

: Clearly, it seems to be a problem for many people. In fact, as in the web reference that goes with the pseudocode, the modification of the array next is ''path[i][j] := path[k][j]''. I did the modification yesterday without looking the talk page (my mistake) thinking it was a minor error, but my modification was reverted by {{reply to|MfR}} with this explanation : {{Quote frame|Pseudocode in this page computes the second node of the path from i to j, not the penultimate (as in reference).}}

: which I don't really understand... In ''Introduction to Algorithms, Cormen et al., MIT Press, Third Edition'' at page 697, again, we see '''[k][j]'''... [[User:Raphaelbwiki|Raphaelbwiki]] ([[User talk:Raphaelbwiki|talk]]) 13:49, 4 June 2019 (UTC)

::Can confirm that this doesn't work if implemented as written in the article right now. I am busy doing something and won't be fixing the article; whoever's reverting it when other people fix it needs to stop. <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/174.34.23.247|174.34.23.247]] ([[User talk:174.34.23.247#top|talk]]) 23:11, 29 November 2019 (UTC)</small> <!--Autosigned by SineBot-->

: To answer the question: Yes, the main function is correct. The web reference that goes with the pseudocode uses a <code>path</code> array, but this article uses a <code>next</code> array. This is not just a difference in naming; the variables are used for different things. Specifically, <code>path[u][v]</code> answers the question "on the shortest path from ''u'' to ''v'', which vertex will be visited '''last''' (before arriving at ''v'')?" Whereas <code>next[u][v]</code> answers the question "on the shortest path from ''u'' to ''v'', which vertex will be visited '''first''' (after leaving ''u'')?"

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?[[User:Visame|Visame]] ([[User talk:Visame|talk]]) 17:28, 7 March 2008 (UTC)

: This is why <code>path</code> from the web reference is initialized as <code>path[u][v] = '''u'''</code> for all edges ("on a direct connection from ''u'' to ''v'', we must have come from ''u''"), but <code>next</code> in the article is initialized as <code>next[u][v] = '''v'''</code> ("on a direct connection from ''u'' to ''v'', we first go to ''v''").

: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) --[[User:Tetha|Tetha]] ([[User talk:Tetha|talk]]) 14:02, 3 September 2009 (UTC)

: This difference in data representation has two consequences when it comes to reconstructing the full path:

== FW no longer in the c++ boost library ==

# The main loop in the <code>PrintPath</code> procedure from the web reference keeps checking <code>Path[source][destination]</code>. The value of <code>source</code> is constant, but <code>destination</code> is updated continuously. This is because <code>Path</code> essentially encodes the path information backwards: At each step we have to ask, "on the shortest path from <code>source</code> to <code>destination</code>, what was the '''last''' vertex we visited (before reaching <code>destination</code>)? And before that? And before that? And before that?" ... until we have retraced our steps all the way back to <code>source</code>, at which point the loop stops. <br> On the other hand, the main loop in the <code>Path</code> procedure from the article keeps checking <code>next[u][v]</code>. Here the value of <code>v</code> (the destination) is constant, but <code>u</code> (the source) is updated continuously. This is because <code>next</code> encodes the path information forwards: At each step we ask, "on the shortest path from <code>u</code> to <code>v</code>, what is the '''first''' vertex we have to visit (after leaving <code>u</code>)? And after that? And after that?" ... until we reach our destination <code>v</code>, at which point the loop stops.

# Since <code>PrintPath</code> from the web reference reconstructs the path backwards, it has to use a stack to reverse the order of visited vertices (LIFO). That's why there is a second loop in that code. But the <code>Path</code> procedure in the article works forwards, so it can just append each segment to the <code>path</code> variable as it goes.

: [[Special:Contributions/84.149.142.109|84.149.142.109]] ([[User talk:84.149.142.109|talk]]) 11:30, 28 December 2022 (UTC)

== Pseudocode contains end-ifs but no end-fors ==

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. [[Special:Contributions/134.173.201.55|134.173.201.55]] ([[User talk:134.173.201.55|talk]]) 09:08, 13 April 2009 (UTC)

The pseudocode contains end-ifs but no end-fors:

== Notation style ==

I think it makes sense to have it be consistent:

[[WP:MOSMATH]] exists. Really, it does.

either

:

no end-fors and no end-ifs

Contrast these:

or

:

every for-loop terminated with an end-for and every if-statement terminated with end-if

: <math>\mathcal{W}_1</math>, <math>\mathcal{W}_2</math>, <math>...</math>, <math>\mathcal{W}_\mathit{n} = \mathcal{M}_{\mathcal{R}^*}</math>

:

The above is in this article.

: <math>\mathcal{W}_1, \mathcal{W}_2,\dots, \mathcal{W}_\mathit{n} = \mathcal{M}_{\mathcal{R}^*}</math>

:

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? [[User:Michael Hardy|Michael Hardy]] ([[User talk: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 [[Special:Contributions/132.228.195.207|132.228.195.207]] ([[User talk: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. [[User:Michael Hardy|Michael Hardy]] ([[User talk:Michael Hardy|talk]]) 17:51, 9 November 2009 (UTC)

1 '''let''' dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)

== Update Pseudocode/change to Java? ==

2 '''for each''' edge (''u'',''v'')

3 dist[''u''][''v''] &larr; w(''u'',''v'') ''// the weight of the edge (''u'',''v'')

4 '''for each''' vertex ''v''

5 dist[''v''][''v''] &larr; 0

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''] &larr; dist[''i''][''k''] + dist[''k''][''j'']

11 '''end if''' <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/2601:282:8001:2E4A:845:D12F:594F:7A77|2601:282:8001:2E4A:845:D12F:594F:7A77]] ([[User talk:2601:282:8001:2E4A:845:D12F:594F:7A77#top|talk]]) 22:43, 4 October 2018 (UTC)</small> <!--Autosigned by SineBot-->

== Could Use an Example Graph Not Containing a Negative Cycle ==

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

The Floyd-Warshall algorithm only finds shortest paths if there are no negative cycles.

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. [[User:Luv2run|luv2run]] ([[User talk:Luv2run|talk]]) 01:56, 30 November 2009 (UTC)

It is illustrative to see what happens if there is a negative cycle,

so the existing example provided in the article is useful.

However, it would also be nice to have a graph not containing any negative-cycles.

: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 <code>int</code> can't have a value of infinity. But this is of course very easy to fix and isn't an argument against it. [[User:Svick|Svick]] ([[User talk:Svick|talk]]) 02:32, 30 November 2009 (UTC)

[[File:Weighted directed graph.png|200px]]

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.

[[File:Digraph thing.png|200px]]

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?[[User:Luv2run|luv2run]] ([[User talk:Luv2run|talk]]) 02:47, 30 November 2009 (UTC)

Below are some notes on a step-through of the algorithm for

: 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. --[[User:RobinK|Robin]] ([[User talk:RobinK|talk]]) 02:57, 30 November 2009 (UTC)

the given example:

upper-bound on cost from node 2 to node 1 is +4.<br />

upper-bound on cost from node 1 to node 3 is -2.<br />

cost on the path from 2 to 3 (going through 1 has) new upper bound of -2.<br />

old upper-bound on cost from node 2 to 3 was +3<br />

Next path: (4 --> 2 --> 3)<br />

OBSERVE cost(4, 2) <= -1<br />

OBSERVE cost(2, 3) <= -2<br />

UPDATE cost(4, 3) <= -3<br />

old cost(4, 3) was +inf<br />

Next path: (1 --> 3 --> 4)<br />

How does this look?

OBSERVE cost(1, 3) <= -2<br />

OBSERVE cost(3, 4) <= +2<br />

UPDATE cost(1, 4) <= 0<br />

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

Next path: (2 --> 3 --> 4)<br />

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

OBSERVE cost(2, 3) <= -2<br />

OBSERVE cost(3, 4) <= +2<br />

UPDATE cost(2, 4) <= 0<br />

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

Next path: (4 --> 3 --> 4)<br />

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

OBSERVE cost(4, 3) <= -3<br />

OBSERVE cost(3, 4) <= +2<br />

UPDATE cost(4, 4) <= -1<br />

Negative cycle found. can leave 4 and return to 4 with net negative cost

== Applications and generalizations ==

:This comment needs a signature and date. [[Special:Contributions/128.226.2.54|128.226.2.54]] ([[User talk:128.226.2.54|talk]]) 19:58, 23 January 2024 (UTC)

* 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).

== Attribution ==

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 <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/209.94.128.120|209.94.128.120]] ([[User talk:209.94.128.120|talk]]) 04:56, 1 December 2009 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

The names are justified by the assertion that "it is essentially the same as". No justification is given for this assertion. I suspect it conceals some nontriviality.

:<math>1</math> in position <math>(i, j)</math> in this variant of the algorithm means that we already know that there is a path between vertices <math>i</math> and <math>j</math>. If you want to combine paths <math>i \rightarrow k</math> and <math>k \rightarrow j</math> (where you would use addition of their lengths in the usual variant), you have to use AND (you can go from <math>i</math> to <math>j</math> through <math>k</math> if there is a path between <math>i</math> and <math>k</math> AND there is a path between <math>k</math> and <math>j</math>). When you try to decide whether there is path through <math>k</math> 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 <math>0</math> in this variant. [[User:Svick|Svick]] ([[User talk:Svick|talk]]) 11:31, 1 December 2009 (UTC)

Also, the citation to MathWorld is unwise. MathWorld is notably unreliable. A citation to a real publication is needed. [[Special:Contributions/128.226.2.54|128.226.2.54]] ([[User talk:128.226.2.54|talk]]) 20:01, 23 January 2024 (UTC)

== Undirected Graphs ==

:The transitive closure and shortest path algorithms are all using a dynamic program to compute aggregate information about the same subsets of paths of a graph, in the same order. They differ only in what aggregate information they compute: whether it is the existence of a path or whether it is the minimum weight of the path. That is, where one has an OR, the other has a MIN. That is the only difference. The regular expression conversion algorithm has the same structure but replaces the OR of Boolean values or the MIN of numbers with the OR of regular expressions. The fact that these algorithms are really doing the same thing with different operations was formalized in the late 1960s and early 1970s using the theory of [[semiring]]s; the semiring article has two relevant footnotes and I think this can also be sourced to the textbook of Aho, Hopcroft, and Ullman. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 21:02, 23 January 2024 (UTC)

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. [[User:AlexandreZ|AlexandreZ]] ([[User talk: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. <b><font color="green">Jwesley</font>[[User_talk:Jwesley78|₇₈]]</b> 17:03, 23 March 2010 (UTC)