COMPSCI320 Chap.10 Shortest Paths with Negative Weights
Shortest Paths with Negative Weights
Negative edge lengths break Dijkstra's greedy rule, and adding a constant to every edge does not repair it.
This chapter indexes a table by the number of edges a path may use, fills it pass by pass on a graph with a negative edge, explains the linear-space Bellman-Ford-Moore algorithm and its stopping rule, and shows how one extra pass detects a negative cycle such as a currency arbitrage loop.
The worked example fills every pass of the edge-budget table on a graph with one negative edge, and the figure tracks each distance falling pass by pass.
The practice cards explain how a further pass reveals a negative cycle and how exchange rates become edge lengths through logarithms.
What this chapter covers
- 01
Why Dijkstra fails on negative edges
- 02
Shortest paths with at most i edges
- 03
The table version and its cost
- 04
Bellman-Ford-Moore with early stopping
- 05
Detecting negative cycles
- 06
Arbitrage and distance-vector routing
Worked example · free
Bellman-Ford passes towards a destination
- 1Pass 1 uses single edges: a 5, b 6, c 1, s still infinite.
- 1Pass 2: a improves to −3 + 1 = −2, b to 3 + 1 = 4, and s reaches 8.
- 1Pass 3: s improves to 4 + (−2) = 2 through a.
- 1Pass 4 changes nothing, so the distances s 2, a −2, b 4, c 1 are final.
Key terms
- Negative Cycle
- A directed cycle whose edge lengths sum to less than zero, so repeated laps lower a path length without limit.
- Bellman-Ford-Moore Algorithm
- A dynamic programming method that relaxes every edge in repeated passes to find shortest paths with negative weights.
- Successor Pointer
- A stored next vertex on the current best path from a vertex towards the destination.
- Distance-Vector Routing
- A routing scheme in which each router updates its distances from its neighbours' vectors, as in Bellman-Ford.
- Edge Budget
- The maximum number of edges a path may use in the shortest-path table of the Bellman-Ford method.
Shortest Paths with Negative Weights FAQ
Why does adding a constant to every edge not fix Dijkstra?
Adding the same amount to each edge penalises a path once per edge, so paths with many edges grow more than paths with few. The shortest path can therefore change after the shift. The lecture shows a small graph where the true shortest route uses three edges but becomes longer than a one-edge route once every length is increased.
Why are n − 1 passes enough when no negative cycle exists?
Without a negative cycle, removing any cycle from a path never makes it longer, so some shortest path is simple. A simple path visits each of the n vertices at most once and so has at most n − 1 edges. After pass n − 1 every such path has been considered, and the distances are final.
How does one extra pass detect a negative cycle?
If no negative cycle exists, a further pass cannot change any distance. If some distance still decreases in pass n, the improving path has n edges, so it repeats a vertex, and the repeated section must be a cycle of negative total length. Following successor pointers from the updated vertex finds that cycle.
Why can successor pointers mislead during the algorithm?
A pointer records the neighbour that last improved a vertex, but that neighbour's own distance may improve later. During the run, following pointers can therefore trace a path whose length differs from the stored distance, and with a negative cycle the pointers may even form a cycle. After the algorithm ends with no negative cycle, the pointers describe shortest paths.
Exam move
Fill one edge-budget table by hand on a graph with a negative edge, writing every row in full, then rerun it with the one-array method and note where the values arrive sooner. Practise the negative cycle argument in three sentences, and convert one set of exchange rates into logarithmic edge lengths.
Before the exam, reconstruct the arbitrage example with rates of your own and confirm that a product above one gives a cycle of negative total length. Rehearse the explanation of why a negative cycle makes shortest paths undefined, using a cycle of total length minus one.
Working through Shortest Paths with Negative Weights in COMPSCI320? Sia is AskSia’s AI Computer Science tutor — ask any COMPSCI320 Shortest Paths with Negative Weights question and get a clear, step-by-step explanation grounded in how COMPSCI320 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
