Talk:Floyd–Warshall algorithm: Difference between revisions

Revision as of 01:52, 30 November 2009

Latest revision as of 00:41, 9 March 2024

(100 intermediate revisions by 38 users not shown)

Line 1:

{{WikiProject Computingbanner shell|class=B|importancevital=yes|1=}}

{{WikiProject Mathematics|priority=Mid}}

== Inconsistent article ==

{{WikiProject Computer science|importance=high}}

}}

{{User:MiszaBot/config

|archiveheader = {{talkarchivenav}}

|maxarchivesize = 70K

|counter = 1

|minthreadsleft = 4

|algo = old(95d)

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

}}

{{archives}}

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

The description of the algorithm is not consistent with the pseudocode. Either change the description to an algorithm that finds if there are paths between vertices (if this is what the Floyd-Warshall is about), or change the pseudocode to something that actually matches the algorithm description.

Where it appears:

:I agree on this, article does not explain Floyd-Warshall algorithm. The description of predecessor matrix has been left out. From a search through older revisions, it seems to me that article is better before an edit which claims to have ''generalized the psuedocode to a more formal notation''. Look at http://en.wikipedia.org/w/index.php?title=Floyd-Warshall_algorithm&diff=106667395&oldid=106657377 --[[User:Tomash|Tomash]] 19:27, 14 May 2007 (UTC)

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

Should it be?:

== Is the code correct? ==

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

In my view, the pseudocode just calculates if there are paths between vertexes. I think I can reconstruct the path length as minimal k where w(k)[i,j]=1, but this is kind of confusing. Is there some reason for this. I would suggest to replace/accompany it with the code below [[User:Jirka6|Jirka6]] 04:04, 25 February 2007 (UTC)

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

== Change pseudocode to Wikicode? ==

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

The pseudocode in this article is very hard to understand. I suggest changing it to something like this:

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

{{wikicode}}

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

'''function''' fw('''int'''[0..n,0..n] graph) {

'''var''' '''int'''[0..n,0..n] dist := graph

'''for''' k '''from''' 0 '''to''' n

'''for''' i '''from''' 0 '''to''' n

'''for''' j '''from''' 0 '''to''' n

'''if''' dist[i,j] > dist[i,k] + dist[k,j]

dist[i,j] = dist[i,k] + dist[k,j]

'''return''' dist

}

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

I will change this soon if nobody protests

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

:Late protest :). The article uses vertices from a set from 1 to n. The above pseudocode/wikicode uses a set from 0 to n. This is confusing. Besides, it is not clear which values the adjacency matrix is supposed to have at [i,j] when there is no edge between two vertices i and j (and how about the value at [i,i]... infinity?). Any idea? Thanks, --[[User:Abdull|Abdull]] 10:41, 9 March 2006 (UTC)

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

::The whole ideea of roy-floyd algorithm is that the whole dist[i,j] matrix contains only infinity at first, then the graph is copyed upon it, changing for known vertices the distance. So there should be a change at the initialization part--[[User:Tudalex|Tudalex]] 17:51, 23 March 2007 (UTC)

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

== Predecessor matrix? ==

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

Wouldn't it be advantageous to also mention the predecessor matrix Pk[i,j] defined as the predecessor of j on the shortest path from i to j, using internal nodes 1...k?

We would add the following to the pseudocode. First initialization:

'''var''' '''int'''[0..n,0..n] pred

'''for''' i '''from''' 0 '''to''' n

'''for''' j '''from''' 0 '''to''' n

'''if''' dist[i,j] > 0

pred[i,j] := i

Next, we add one more line after the "dist[i,j] = dist[i,k] + dist[k,j]" line:

pred[i,j] = pred[k,j]

I'm not entirely sure if this addition would be appreciated. Being a novice Wikipedian, I decided I won't make the addition but rather post it here. If an experienced Wikipedian thinks it's a good addition, please make it.

:I think that's a good idea. IFAIK the "Warshall" part of the algorithm means that it will actually find the paths. If it is used to find just the distances, it should be called just "Floyd's algorithm". I may be wrong. Anyway, I say go ahead and make the changes. --[[User:Ropez|Ropez]] 28 June 2005 22:11 (UTC)

::It's done. BTW, there seems to be a problem regarding the predecessor assignment statement. See [[Talk:Floyd-Warshall algorithm/C plus plus implementation]] for details. --[[User:Netvor|Netvor]] 30 June 2005 19:25 (UTC)

I think it makes sense to have it be consistent:

:This is useless without telling us what, exactly, "pred" is is and how it's used. Furthermore, AFAICT, pred is not returned from the function—it just gets updated and then thrown away. Very confusing unless you read the talk page... --[[User:DomenicDenicola|Domenic Denicola]] 07:43, 24 July 2006 (UTC)

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

:Really good suggestion!Well done![[User:Visame|Visame]] ([[User talk:Visame|talk]]) 17:30, 7 March 2008 (UTC)

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

== Predecessor matrix for negative edge weights? ==

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

I was wondering how the code must look to get a working predecessor matrix with negative edge weights. The following part of the code seems to consider "0" as "no conection" or does it?

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

'''if''' dist[i,j] > 0

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

pred[i,j] := i

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 personally would rewrite this as something like:

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

'''if''' dist[i,j] < Infinity

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

pred[i,j] := i

where "Infinity" is used as "There is no connection between these nodes". The C++-implementation gives me the impression this is the right way. -- [[User:RealLink|RealLink]] 10:39, 2 September 2005 (UTC)

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

:I've changed to exactly what you wrote, but I don't know what the correct formatting should be (Infinity, INFINITY, '''infinity''', or what). [[User:203.213.7.132|203.213.7.132]] 04:30, 19 June 2006 (UTC)

the given example:

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

:I think we should also tell the meaning of "Infinity".

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

Does it mean there is no edgesbetween the two vertices ? ---[[User:Visame|Visame]] ([[User talk:Visame|talk]]) 17:37, 7 March 2008 (UTC)

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

== Plagiarism? ==

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

Just wanted to point out that the paragraph starting "The algorithm is based on the following observation..." is taken almost verbatim from "Introduction to Algorithms Second Edition", Cormen, et al, 2001, p.629. The section is "25.2 The Floyd-Warshall algorithm", third paragraph.

:I'll take care of this (or someone else, earlier). Obvoiously, the one who copied the text had no idea how and why the algorithm works: [[voodoo programming|wikivoodoopedia]]. [[user:mikkalai|mikka]] [[user talk:mikkalai|(t)]] 20:58, 15 November 2005 (UTC)

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

== Redirect ==

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

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

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

I just put up a redirect from [[Floyd's algorithm]] to this article. It was not nearly as advanced as this article, but I saved a C implementation which I have not verified yet:

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

int floyds(int *matrix) {

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

int k, i, j;

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

UPDATE for cost(k2, 4) <= 0; k <br n; k++)/>

for (i = 0; i < n; i++)

for (j = 0; j < n; j++)

if (matrix[i][j] > (matrix[i][k] + matrix[k][j]))

matrix[i][j] = matrix[i][k] + matrix[k][j];

}

--[[User:Abdull|Abdull]] 10:37, 9 March 2006 (UTC)

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

== Python code? ==

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

The article contains a dead link to Python code.

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

== How does this look? ==

== Attribution ==

I found the original article confusing and hard to read. I've changed it to reflect the way I was taught FW, which I think is more comprehensible. Any suggestions? [[User:Hjfreyer|Hjfreyer]] 23:06, 7 April 2007 (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.

== Wouldn't Dijkstra's algorithm be better for transitive closure? ==

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)

It seems like a better way to calculate the transitive closure of a graph would be to apply [[Dijkstra's algorithm]] starting at each vertex. Since you do not need the Extract-Min function at each step, since you don't care about finding the minimum path, you can do each vertex in O(e) time, or a total of O(ve). This is better than O(v^3) especially for sparse graphs. [[User:Alex319|Alex319]] 17:47, 6 June 2007 (UTC)

:Actually, for transitive closure, breadth-first search is quite sufficient. [[User:Dcoetzee|Dcoetzee]] 22:37, 10 June 2008 (UTC)

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

== Analysis Section ==

I just added: '''Therefore, the [[Computational_complexity_theory|complexity]] of the algorithm is [[big theta|<math>\Theta({n}^3)</math>]] and can be solved by a [[Deterministic Turing machine|deterministic machine]] in [[polynomial time]].''' to the analysis section. Does this need any further explanation? It feels like I would be just taking stuff from other articles if I started describing it further. [[User:Fintler|fintler]] 01:06, 11 October 2007 (UTC)

==What's the relationship between FolydWarshall and (Gauss-Jordan algorithm)==

In the "Applications and generalizations" part, it says:

"Inversion of real matrices (Gauss-Jordan algorithm). " is one application of Floyd-Warshall algorithm.

I can't figure it out.Can anyone tell me?

THANKS!E-mail me:Kankaqi [AT] gmail.com[[User:Visame|Visame]] ([[User talk:Visame|talk]]) 17:20, 7 March 2008 (UTC)

==More Explanation on Negative Cycles Needed==

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)

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

==Negative Cycle not defined==

Title says it all really. Is a negative cycle one in which every edge is -vely weighted, or is it one in which the overall path length is -ve? <small>—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/24.153.207.149|24.153.207.149]] ([[User talk:24.153.207.149|talk]]) 00:22, 10 June 2008 (UTC)</small><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

:Okay, we've had enough questions about negative cycles now that I think this could be expanded. The question is where to do it - I think the most appropriate place is in the general article about shortest path algorithms, and then we can link it from here. The brief answers are: a negative cycle is a cycle with total weight negative, and the behavior of a shortest path algorithm on a graph with negative cycles depends on the algorithm. It may fail to terminate; if it does terminate, it will return a valid result for graphs containing negative cycles, which doesn't make sense because such graphs have no shortest path between any two nodes both reachable from the negative cycle (you can achieve arbitrarily short paths by following the cycle). [[User:Dcoetzee|Dcoetzee]] 22:31, 10 June 2008 (UTC)

::In my opinion an article about "Negative Cycles" is needed, it could then elaborate on algorithms commonly used for such thing such as this one and the [[Bellman-Ford algorithm]] and this page could link to that article instead.[[User:Vexorian|Vexorian]] ([[User talk:Vexorian|talk]]) 13:12, 17 January 2009 (UTC)

==C Implementation==

I thought I'd get rid of the explanation of how the "C" implementation really doesn't use any C++ paradigms. Does anyone think that is necessary info? I'm actually the guy who wrote the linked-to document (thanks to whoever found my page!) so I'm willing to change the linked-to page as well if anyone has suggestions. [[User:Pandemias|Pandemias]] ([[User talk:Pandemias|talk]]) 06:17, 19 June 2008 (UTC)

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

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)

== Notation style ==

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

:

Contrast these:

:

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

==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 to read/understand than this psuedocode is, but I'm not too familiar with Wikipedia's pseudocode conventions. -Luv2run, 11/29-09.