Content deleted Content added
DaisyFluff (talk | contribs) |
DaisyFluff (talk | contribs) |
||
Line 212:
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
| |||