This Â
level-5 vital article is rated B-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||||||||||||
|
|
|
This page has archives. Sections older than 95 days may be automatically archived by Lowercase sigmabot III when more than 4 sections are present. |
Where it appears:
next[i][j] â next[i][k]
Should it be?:
next[i][j] â next[k][j]
Pseudocode in this page computes the second node of the path from i to j, not the penultimate (as in reference).
path
array, but this article uses a next
array. This is not just a difference in naming; the variables are used for different things. Specifically, path[u][v]
answers the question "on the shortest path from u to v, which vertex will be visited last (before arriving at v)?" Whereas next[u][v]
answers the question "on the shortest path from u to v, which vertex will be visited first (after leaving u)?"path
from the web reference is initialized as path[u][v] = u
for all edges ("on a direct connection from u to v, we must have come from u"), but next
in the article is initialized as next[u][v] = v
("on a direct connection from u to v, we first go to v").PrintPath
procedure from the web reference keeps checking Path[source][destination]
. The value of source
is constant, but destination
is updated continuously. This is because Path
essentially encodes the path information backwards: At each step we have to ask, "on the shortest path from source
to destination
, what was the last vertex we visited (before reaching destination
)? And before that? And before that? And before that?" ... until we have retraced our steps all the way back to source
, at which point the loop stops. Path
procedure from the article keeps checking next[u][v]
. Here the value of v
(the destination) is constant, but u
(the source) is updated continuously. This is because next
encodes the path information forwards: At each step we ask, "on the shortest path from u
to v
, what is the first vertex we have to visit (after leaving u
)? And after that? And after that?" ... until we reach our destination v
, at which point the loop stops.PrintPath
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 Path
procedure in the article works forwards, so it can just append each segment to the path
variable as it goes.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] â w(u,v) // the weight of the edge (u,v) 4 for each vertex v 5 dist[v][v] â 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] â dist[i][k] + dist[k][j] 11 end if â Preceding unsigned comment added by 2601:282:8001:2E4A:845:D12F:594F:7A77 ( talk) 22:43, 4 October 2018 (UTC)
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.
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.
upper-bound on cost from node 1 to node 3 is -2.
cost on the path from 2 to 3 (going through 1 has) new upper bound of -2.
old upper-bound on cost from node 2 to 3 was +3
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: (1 --> 3 --> 4)
OBSERVE cost(1, 3) <= -2
OBSERVE cost(3, 4) <= +2
UPDATE cost(1, 4) <= 0
Next path: (2 --> 3 --> 4)
OBSERVE cost(2, 3) <= -2
OBSERVE cost(3, 4) <= +2
UPDATE cost(2, 4) <= 0
Next path: (4 --> 3 --> 4)
OBSERVE cost(4, 3) <= -3
OBSERVE cost(3, 4) <= +2
UPDATE cost(4, 4) <= -1
Negative cycle found. can leave 4 and return to 4 with net negative cost
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. 128.226.2.54 ( talk) 20:01, 23 January 2024 (UTC)
This Â
level-5 vital article is rated B-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||||||||||||
|
|
|
This page has archives. Sections older than 95 days may be automatically archived by Lowercase sigmabot III when more than 4 sections are present. |
Where it appears:
next[i][j] â next[i][k]
Should it be?:
next[i][j] â next[k][j]
Pseudocode in this page computes the second node of the path from i to j, not the penultimate (as in reference).
path
array, but this article uses a next
array. This is not just a difference in naming; the variables are used for different things. Specifically, path[u][v]
answers the question "on the shortest path from u to v, which vertex will be visited last (before arriving at v)?" Whereas next[u][v]
answers the question "on the shortest path from u to v, which vertex will be visited first (after leaving u)?"path
from the web reference is initialized as path[u][v] = u
for all edges ("on a direct connection from u to v, we must have come from u"), but next
in the article is initialized as next[u][v] = v
("on a direct connection from u to v, we first go to v").PrintPath
procedure from the web reference keeps checking Path[source][destination]
. The value of source
is constant, but destination
is updated continuously. This is because Path
essentially encodes the path information backwards: At each step we have to ask, "on the shortest path from source
to destination
, what was the last vertex we visited (before reaching destination
)? And before that? And before that? And before that?" ... until we have retraced our steps all the way back to source
, at which point the loop stops. Path
procedure from the article keeps checking next[u][v]
. Here the value of v
(the destination) is constant, but u
(the source) is updated continuously. This is because next
encodes the path information forwards: At each step we ask, "on the shortest path from u
to v
, what is the first vertex we have to visit (after leaving u
)? And after that? And after that?" ... until we reach our destination v
, at which point the loop stops.PrintPath
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 Path
procedure in the article works forwards, so it can just append each segment to the path
variable as it goes.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] â w(u,v) // the weight of the edge (u,v) 4 for each vertex v 5 dist[v][v] â 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] â dist[i][k] + dist[k][j] 11 end if â Preceding unsigned comment added by 2601:282:8001:2E4A:845:D12F:594F:7A77 ( talk) 22:43, 4 October 2018 (UTC)
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.
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.
upper-bound on cost from node 1 to node 3 is -2.
cost on the path from 2 to 3 (going through 1 has) new upper bound of -2.
old upper-bound on cost from node 2 to 3 was +3
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: (1 --> 3 --> 4)
OBSERVE cost(1, 3) <= -2
OBSERVE cost(3, 4) <= +2
UPDATE cost(1, 4) <= 0
Next path: (2 --> 3 --> 4)
OBSERVE cost(2, 3) <= -2
OBSERVE cost(3, 4) <= +2
UPDATE cost(2, 4) <= 0
Next path: (4 --> 3 --> 4)
OBSERVE cost(4, 3) <= -3
OBSERVE cost(3, 4) <= +2
UPDATE cost(4, 4) <= -1
Negative cycle found. can leave 4 and return to 4 with net negative cost
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. 128.226.2.54 ( talk) 20:01, 23 January 2024 (UTC)