Shortest paths and the limits of greedy finalization

Prerequisites: Graph traversal, priority queues, and path cost.

Learning objectives

• Trace relaxation and stale heap entries.
• State the nonnegative-weight condition for Dijkstra.
• Detect reachable negative cycles with repeated relaxation.

Distances are claims improved by evidence

For a source s, initialize distance[s]=0 and all other distances to infinity. Relaxing an edge u→v of weight w asks whether distance[u]+w improves distance[v]. If so, replace the value and record u as v’s predecessor. Every finite label represents the cost of a discovered path. The question is when a label can be declared final.

Dijkstra’s algorithm removes the smallest tentative distance from a priority queue. With nonnegative edge weights, any alternative path reaching that vertex through still-unsettled vertices cannot become cheaper by adding further edges. This justifies finalization. An implementation using repeated heap insertions instead of decrease-key must skip stale entries whose queued distance differs from the best known distance.

Trace a weighted example

Use edges S→A:6, S→B:2, B→A:1, B→C:7, A→C:2. Start with S:0. Removing S discovers A:6 and B:2. Removing B improves A to 3 and discovers C:9. Removing A:3 improves C to 5. The old A:6 and C:9 entries remain physically in the heap but carry obsolete work. The shortest path to C is S→B→A→C, cost 5.

Now consider S→A:2, S→B:5, B→A:−4. A Dijkstra implementation that permanently finalizes A at cost 2 is wrong: the path through B costs 1. The failure concerns the proof’s nonnegative-edge assumption, not the priority queue itself.

Relax systematically when finalization is unavailable

Bellman-Ford performs repeated passes over all edges. After k passes, the standard argument guarantees correct shortest costs among paths with at most k edges, assuming appropriate initialization and relaxation. If a shortest path exists and no reachable negative cycle improves it indefinitely, a simple shortest path needs at most V−1 edges. A further improvement after V−1 passes reveals a reachable negative cycle affecting some downstream distances.

Unreachable negative cycles do not invalidate distances from the chosen source. A reachable negative cycle also does not necessarily affect every destination; it must be able to reach the destination in question. A production API should define how it reports unreachable vertices and unbounded-below costs rather than returning a misleading ordinary number.

Choose a representation and output contract

Unweighted shortest paths use BFS. Directed acyclic graphs permit topological-order relaxation even with negative weights. General nonnegative graphs fit Dijkstra; graphs with negative edges need another justified method. Path reconstruction follows predecessors backward, so store them consistently on improvements and guard against cycles when unbounded cases are possible.

MIT’s shortest-path lectures develop these arguments. Reproduce a counterexample whenever an assumption is weakened. That habit is more useful than memorizing one algorithm as the answer to every routing problem.

Practice problem

Run Dijkstra on S→A:4, S→B:1, B→A:2, A→G:3, B→G:9. List the order of nonstale removals and the final path. Then add A→B:−4. Identify a negative cycle, show its total weight, and determine whether the shortest cost from S to G remains finite.

Worked solution

The nonstale removal order is S:0, B:1, A:3, G:6. The path is S→B→A→G. An old queued A:4 and G:10 can later be skipped. Adding A→B:−4 creates B→A→B with cost 2−4=−2. It is reachable from S, and from that cycle A can reach G. Repeating the cycle lowers the path cost by two each time before going to G, so no finite minimum exists. Reporting the earlier cost 6 would be incorrect after this change. A shortest-path interface should report an unbounded-below result for G under this model.

Check your understanding

Edges are S→A=2, S→B=5, and B→A=−4. Why is permanently finalizing A at distance 2 unsafe?

• The shortest path must use the fewest edges.
• A negative edge always makes every distance unbounded.
• The graph contains a negative cycle.
• A later route through B has cost 1.

Explanation

S→B→A costs 5−4=1. The graph is acyclic, so the problem is a failed nonnegative-edge assumption, not an unbounded negative cycle.

A reachable negative cycle can reach T but cannot reach U. Both T and U are reachable from S. What follows?

• Both destinations necessarily have unbounded distance.
• T has no finite shortest distance; U is not affected by this cycle.
• Neither is affected unless the cycle contains S.
• Only vertices physically on the cycle are affected.

Explanation

A path can repeat the cycle to reduce its cost before continuing to T. It cannot carry that reduction to a destination unreachable from the cycle.

Primary reading

• Introduction to Algorithms: lecture notes: MIT OpenCourseWare

Open the study and save your work →