Talk:Floyd–Warshall algorithm: Difference between revisions

Revision as of 03:46, 5 October 2018

Latest revision as of 00:41, 9 March 2024

(20 intermediate revisions by 12 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? ==

==Litmus Testing==

Where it appears:

My correction of the Floyd Algorithm are correct. The entire artcle needs a rewrite to be both understandable and correct. As it remains, it is confusing my students and I spend a lot of time correcting their errors gleaned from this article. This is a simple to understand algorithm when explained clearly. Instead we don't only have mathematical snobbery, but truly inaccurate information. I am SICK of wikipeadia inability to just tell wrong from write. Mathematical truth is not a matter of a VOTE. When k = 1, it is not equal to zero. Fixing this page requires a complete rewrite because the graph and the agorthms don't match and the explanation doesn't inform the reader of facts. Not having fixed these problems in the article has been called not passing a litmus test. The only litmus test here is if the article is informative and educational. It is NOT. — Preceding unsigned comment added by 96.57.23.82 (talk) 02:16, 17 May 2015 (UTC) <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]]) </small><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

==Is there a bug in the main loop? ==

Should the main loop for updating the 'next' matrix instead of looking like:

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

Should it be?:

be

next[i][j] ← next[ik][kj]

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

?

I have been random fuzz testing the algorithm in Python and occasionally get a wrong path which appears fixed with the additional line. <!-- Template:Unsigned --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Shane.magrath|Shane.magrath]] ([[User talk:Shane.magrath#top|talk]] • [[Special:Contributions/Shane.magrath|contribs]]) 08:03, 17 April 2018 (UTC)</small> <!--Autosigned by SineBot-->

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

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

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

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

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

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)

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

== Litmus Test ==

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

My correction of the Floyd Allgorthm are correct. The entire artcle needs a rewrite to be both understandalb eand correct. As it remains, it is confusing my students and I spend a lot of time correcting their errors gleened from this article. This is a simple to undertand allgorithm when explained clearly. Instead we don't only have mathmatical snobbery, but truly inacuate information. I am SICK of wikipeadia inability to just tell wrong from write. Mathmatical truth is not a matter of a VOTE. When k = 1, it is not equal to zero. Fixing this page requires a complete rewrite because the graph and the agorthms don't match and the explaination doesn't inform the reader of facts. Not having fixed these problems in the article has been called not passing a litmus test. The only litmus test here is if the article is informatative and educational. It is NOT. <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]]) 02:17, 17 May 2015 (UTC)</small><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

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

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

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.

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)

Your not listening. The problem isn't that the set of vertices is wrong, the problem is that the material is NOT consistant and therefore confuses the STUDENT.

The Graph has to match the Allgorithm and mathc the equation. You have to SAY what you mean. In this case it does not SAY what it means, nor does it say what you said.

It is just a pile of nonsense. <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]]) 06:07, 17 May 2015 (UTC)</small><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

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

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.

: Dear non-account user, a request: before going back and making the same edit again, could we instead try to find common understanding? In particular, what do you think the symbols "{1,2,3}" represent? --[[User:Joel B. Lewis|JBL]] ([[User_talk:Joel_B._Lewis|talk]]) 01:21, 17 May 2015 (UTC)

there is no need to "know" what it means because it says what it is, aand what it says is WRONG. In fact, the __entire__ article is wrong.

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

2 for each vertex v

3 dist[v][v] ← 0

4 for each edge (u,v)

5 dist[u][v] ← w(u,v) // the weight of the edge (u,v)

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] ← dist[i][k] + dist[k][j]

11 end if

Example

The algorithm above is executed on the graph on the left below:

Floyd-Warshall example.svg

Note - you have an EXMAMPLE pf K=0

K NEVER equals zero ... K starts at 1.

Prior to the first iteration of the outer loop, labeled k=0 above,

Yeah - that si WRONG, k is 1.

the only known paths correspond to the single edges in the graph. At k=1, paths that go through the vertex 1 are found: in particular, the path 2→1→3 is found, replacing the path 2→3 which has fewer edges but is longer. At k=2, paths going through the vertices {1,2} are found. The red and blue boxes show how the path 4→2→1→3 is assembled from the two known paths 4→2 and 2→1→3 encountered in previous iterations, with 2 in the intersection. The path 4→2→3 is not considered, because 2→1→3 is the shortest path encountered so far from 2 to 3. At k=3, paths going through the vertices {1,2,3} are found.

WRONG, the paths do NOT go through that set.

Finally, at k=4, all shortest paths are found.

So the whole thing needs a rewrite. Try starting with Cormen.... <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]]) 01:30, 17 May 2015 (UTC)</small><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

: Your post is not really comprehensible -- possibly, if you want your comments to be taken seriously, you should take some time and write a few clear sentences laying out exactly what you think the incorrect statement is and why you believe it to be incorrect. As it is I am not able to understand either of these things from your comments. (Also, it really might help if you would answer the question that I asked.) --[[User:Joel B. Lewis|JBL]] ([[User_talk:Joel_B._Lewis|talk]]) 01:37, 17 May 2015 (UTC)

Since it quotes the article, it is not surprising that it is hard to understand. As it is, it is clear. The algorithm in the code doesn't match diagram, and the diagram doesn't match the text. This whole article needs a rewrite. Perhaps the esteemed Professor of Univ Irvine can donate his class notes. <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]]) 01:41, 17 May 2015 (UTC)</small><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

Follow Cormen if you need to

The structure of a shortest path

In the Floyd-Warshall algorithm, we use a different characterization of the structure of a shortest path than we

used in the matrix-multiplication-based all-pairs algorithms. The algorithm considers the "intermediate" vertices of

a shortest path, where an intermediate vertex of a simple path p = 〈 v , v , . . . , v 〉 is any vertex of p other than

1 2 lv or v , that is, any vertex in the set {v ,v , . . . , v }.

1 l 2 3 l-1The Floyd-Warshall algorithm is based on the following observation. Let the vertices of G be V = {1, 2, . . . ,

n}, and consider a subset {1, 2, . . . , k} of vertices for some k. For any pair of vertices i, j ∈ V, consider all

paths from i to j whose intermediate vertices are all drawn from {1, 2, . . . , k}, and let p be a minimum-weight

path from among them. (Path p is simple, since we assume that G contains no negative-weight cycles.) The

Floyd- Warshall algorithm exploits a relationship between path p and shortest paths from i to j with all

intermediate vertices in the set {1, 2, . . . , k - 1}. The relationship depends on whether or not k is an

intermediate vertex of path p.

Figure 26.3 Path p is a shortest path from vertex i to vertex j, and k is the highest-numbered intermediate vertex of p.

Path p1 , the portion of path p from vertex i to vertex k, has all intermediate vertices in the set {1, 2, . . . , k – 1}. The

same holds for path p2 from vertex k to vertex j.

•

If k is not an intermediate vertex of path p, then all intermediate vertices of path p are in the set {1, 2, . . . ,

k – 1}. Thus, a shortest path from vertex i to vertex j with all intermediate vertices in the set {1, 2, . . . ,

k – 1} is also a shortest path from i to j with all intermediate vertices in the set {1, 2, . . . , k}.

•

If k is an intermediate vertex of path p, then we break p down into

as shown in Figure 26.3

. By Lemma 25.1, p1 is a shortest path from i to k with all intermediate vertices in the set {1, 2, . . . ,

k}. In fact, vertex k is not an intermediate vertex of path p1 , and so p1 is a shortest path from i to

k with all intermediate vertices in the set {1, 2, . . . , k - 1}. Similarly, p2 is a shortest path from vertex

k to vertex j with all intermediate vertices in the set {1, 2, . . . , k - 1}.

A recursive solution to the all-pairs shortest-paths problem

Based on the above observations, we define a different recursive formulation of shortest-path estimates than we did

in Section 26.1. Let

be the weight of a shortest path from vertex i to vertex j with all intermediate vertices in

the set {1, 2, . . . , k}. When k = 0, a path from vertex i to vertex j with no intermediate vertex numbered higher

than 0 has no intermediate vertices at all. It thus has at most one edge, and hence

. A recursive definition

is given by

(26.5)

The matrix

gives the final answer—

are in the set {1, 2, . . . , n}.

for all i, j ∈ Vbecause all intermediate vertices

Computing the shortest-path weights bottom up

Based on recurrence (26.5), the following bottom-up procedure can be used to compute the values

in order of

increasing values of k. Its input is an n × n matrix W defined as in equation (26.1). The procedure returns the matrix

D(n) of shortest-path weights.

Figure 26.4 shows a directed graph and the matrices D (k) computed by the Floyd-Warshall algorithm.

The running time of the Floyd-Warshall algorithm is determined by the triply nested for loops of lines 3-6. Each

execution of line 6 takes O(1) time. The algorithm thus runs in time Θ(n3). As in the final algorithm in Section 26.1

, the code is tight, with no elaborate data structures, and so the constant hidden in the Θ -notation is small. Thus, the

Floyd-Warshall algorithm is quite practical for even moderate-sized input graphs.

Constructing a shortest path

There are a variety of different methods for constructing shortest paths in the Floyd-Warshall algorithm. One way

is to compute the matrix D of shortest-path weights and then construct the predecessor matrix Π from the

D matrix. This method can be implemented to run in O(n3 ) time (Exercise 26.1-5). Given the predecessor matrix

Π, the PRINT- ALL- PAIRS- SHORTEST- PATH procedure can be used to print the vertices on a given shortest path.

We can compute the predecessor matrix Π "on-line" just as the Floyd-Warshall algorithm computes the

matrices D (k) . Specifically, we compute a sequence of matrices Π(0) , Π(1) , . . . , Π(n), where Π = Π(n) and

is

defined to be the predecessor of vertex j on a shortest path from vertex i with all intermediate vertices in the set

{1, 2, . . . , k}.

We can give a recursive formulation of

vertices at all. Thus,

. When k = 0, a shortest path from i to j has no intermediate

Figure 26.4 The sequence of matrices D (k) and Π(k) computed by the Floyd-Warshall algorithm for the graph in Figure 26.1

. <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]]) 02:07, 17 May 2015 (UTC)</small><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

I am new to wikipedia authoring, but whether or not the article is clear the pseudo-code is incorrect. On line 9 there is a > symbol where there should be a < symbol. Being new I thought I would talk about it on this page before diving in and correcting it

[[User:Philsrice|Philsrice]] ([[User talk:Philsrice|talk]]) 08:28, 14 August 2015 (UTC)

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

Line 212 ⟶ 72:

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

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

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

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

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

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

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

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

Next path: (4 --> 2 --> 3)

OBSERVE cost(4, 2) <= -1

OBSERVE cost(2, 3) <= -2

UPDATE cost(4, 3) <= -3

old cost(4, 3) was +inf

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

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

Next path: (1 --> 3 --> 4)

OBSERVE cost(1, 3) <= -2

OBSERVE cost(3, 4) <= +2

UPDATE cost(1, 4) <= 0

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

== Attribution ==

Next path: (2 --> 3 --> 4)

OBSERVE cost(2, 3) <= -2

OBSERVE cost(3, 4) <= +2

UPDATE cost(2, 4) <= 0

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)

Next path: (4 --> 3 --> 4)

OBSERVE cost(4, 3) <= -3

OBSERVE cost(3, 4) <= +2

UPDATE cost(4, 4) <= -1

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

Negative cycle found. can leave 4 and return to 4 with net negative cost. <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/2601:282:8001:2E4A:F4B4:1347:91EA:A00D|2601:282:8001:2E4A:F4B4:1347:91EA:A00D]] ([[User talk:2601:282:8001:2E4A:F4B4:1347:91EA:A00D#top|talk]]) 02:58, 5 October 2018 (UTC)</small> <!--Autosigned by SineBot-->