Talk:Floyd–Warshall algorithm: Difference between revisions

Revision as of 23:18, 16 May 2015

Latest revision as of 00:41, 9 March 2024

(47 intermediate revisions by 18 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? ==

== Optimization in Pseudocode ==

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.

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)

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.

== Path reconstruction Incorrect ==

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

The Path reconstruction pseudocode never populates the 'next' variable with anything but null and so it cannot find any paths. [[Special:Contributions/67.172.248.52|67.172.248.52]] ([[User talk:67.172.248.52|talk]]) 16:19, 14 October 2013 (UTC)

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

:This section has undergone several iterations since this comment was made. [[Special:Contributions/98.209.119.23|98.209.119.23]] ([[User talk:98.209.119.23|talk]]) 22:05, 29 April 2014 (UTC)

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

== Negative Cycles ==

the given example:

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

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.

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

[[User:MatthiasWalter|MatthiasWalter]] ([[User talk:MatthiasWalter|talk]]) 08:51, 10 December 2013 (UTC)

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

== Simpler path reconstruction ==

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

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. [[User:Thomasda|Thomasda]] ([[User talk:Thomasda|talk]]) 20:31, 19 May 2014 (UTC)

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

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

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

== Floyd's and Warshall's algorithms are not the same! ==

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

The article as it is now completely misses the point of Warshall's contribution!

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

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

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

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 <math>O(n^2)</math> rather than <math>O(n^3)</math>. 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. [[User:Rp|Rp]] ([[User talk:Rp|talk]]) 14:38, 3 September 2014 (UTC)

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

== Litmus Test ==

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

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

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

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.

== Attribution ==

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 <small><span class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:96.57.23.82 |96.57.23.82 ]] ([[User talk:96.57.23.82 |talk]] • [[Special:Contributions/96.57.23.82 |contribs]]) </span></small><!-- Template:Unsigned -->

:Please see [[WP:COMPETENCE]] and please stop editing this article until you actually understand the algorithm. To be specific, the ''k''th 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. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 22:58, 16 May 2015 (UTC)

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.

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)

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. <small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/96.57.23.82|96.57.23.82]] ([[User talk:96.57.23.82|talk]]) 23:04, 16 May 2015 (UTC)</small><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

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

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.