Talk:Floyd–Warshall algorithm: Difference between revisions

Revision as of 10:37, 9 March 2006

Latest revision as of 00:41, 9 March 2024

(136 intermediate revisions by 59 users not shown)

Line 1:

{{WikiProject banner shell|class=B|vital=yes|1=

== Change pseudocode to Wikicode? ==

{{WikiProject Mathematics|priority=Mid}}

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

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

{{wikicode}}

Where it appears:

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

Should it be?:

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

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

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

}

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

I will change this soon if nobody protests

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

== Predecessor matrix? ==

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

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)

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

== Predecessor matrix for negative edge weights? ==

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

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

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

pred[i,j] := i

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

I personally would rewrite this as something like:

I think it makes sense to have it be consistent:

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

either

pred[i,j] := i

no end-fors and no end-ifs

or

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

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)

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

== Plagiarism? ==

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

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)

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

== Redirect ==

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

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

int floyds(int *matrix) {

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

int k, i, j;

for (k = 0; k < 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)

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

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

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

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)

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