Content deleted Content added
m Signing comment by 2601:282:8001:2E4A:845:D12F:594F:7A77 - "→Pseudocode contains end-ifs but no end-fors: new section" |
|||
Line 196:
10 dist[''i''][''j''] ← dist[''i''][''k''] + dist[''k''][''j'']
11 '''end if''' <!-- Template:Unsigned IP --><small class="autosigned">— 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.
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.
[[File:Floyd-Warshall example.svg|600px]]
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.
| |||