Talk:Floyd–Warshall algorithm: Difference between revisions

Revision as of 21:43, 8 February 2013

Latest revision as of 00:41, 9 March 2024

(66 intermediate revisions by 24 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 Computer science|class=B|importance=high}}

{{archives}}

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

== Applications and generalizations ==

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

: 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''").

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

# 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 ==

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

I think it makes sense to have it be consistent:

either

no end-fors and no end-ifs

or

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

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

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 Floyd-Warshall algorithm only finds shortest paths if there are no negative cycles.

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.

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

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

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

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 />

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

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

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

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

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

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

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

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

== Undirected Graphs ==

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

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

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

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)

: 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. [[User:Dcoetzee|Dcoetzee]] 21:02, 19 December 2012 (UTC)

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

== Java examples ==

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

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.

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

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. [[User:Dmforcier|Dmforcier]] ([[User talk: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. [[User:Svick|Svick]] ([[User talk:Svick|talk]]) 20:21, 8 August 2010 (UTC)

== First sentenceAttribution ==

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.

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. <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/71.12.211.253|71.12.211.253]] ([[User talk:71.12.211.253|talk]]) 21:45, 12 June 2012 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

: 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. <span class="nowrap"><b>[[User:Justin W Smith|Justin W Smith]]</b> <i>^{[[User talk:Justin W Smith|talk]]}/_{[[Special:Contributions/Justin W Smith|stalk]]}</i></span> 03:05, 13 June 2012 (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)

== Optimization in Pseudocode ==

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

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. [[User:Stargazer7121|Stargazer7121]] ([[User talk:Stargazer7121|talk]]) 21:39, 8 February 2013 (UTC)