Dijkstra Fails on a Graph with a Negative Edge
A delivery company models its road network as a directed graph. Nodes are depots and customers; edge weights are travel times in minutes. Most edges are positive, but one promotional route between depot X and customer Y has a weight of −8 minutes because the company credits drivers for using it (a toll rebate). A dispatcher runs Dijkstra's algorithm from the main depot to find the shortest travel time to every customer. The result claims customer Z is reachable in 22 minutes via a path that the dispatcher knows is actually 19 minutes through the negative edge. The dispatcher asks whether to simply add 8 to every edge weight to remove the negative value, then subtract 8 times the number of edges at the end.
1. Explain precisely why Dijkstra's algorithm produced an incorrect shortest path in the presence of the negative edge.
Read the worked answer
Dijkstra's correctness rests on a key invariant: once a node is removed from the priority queue (finalised), its distance is the true shortest distance. This holds only when all edge weights are non-negative. The proof uses the fact that any path extending a finalised node's distance can only increase it, because adding a non-negative edge cannot reduce the total.
With a −8 edge, that argument collapses. A node finalised early with distance d might later be reachable by a cheaper path that goes through the negative edge. Dijkstra never revisits a finalised node, so it reports the stale, larger distance. Concretely, if depot X is finalised at distance 30 and Y is finalised at 40 via a positive route, but X→Y has weight −8, then Y's true distance is 30 + (−8) = 22, which is smaller than 40. Dijkstra already locked in 40 and will not correct it. The reported 22-minute path to Z similarly reflects a route that Dijkstra believed was optimal because it never explored the negative edge's shortcut. The algorithm is not buggy; its precondition (non-negative weights) is violated.
2. Evaluate the dispatcher's proposal to add 8 to every edge and subtract 8 times the edge count at the end.
Read the worked answer
The proposal is incorrect. Adding a constant c to every edge changes the relative cost of paths with different numbers of edges. A path with 3 edges gains 3c; a path with 5 edges gains 5c. Subtracting c times the edge count at the end does not restore the original ordering because the number of edges differs between candidate paths.
Example: path P has 2 edges of weights 10 and 10 (total 20). Path Q has 4 edges of weights 6, 6, 6, 6 (total 24). Originally P (20) beats Q (24). Add 8 to each edge: P becomes 18 + 18 = 36; Q becomes 14 × 4 = 56. P still wins here, but construct a case where the edge counts differ enough: P has 1 edge of weight 30 (total 30); Q has 5 edges of weight 7 (total 35). Add 8: P = 38; Q = 15 × 5 = 75 - P still wins. The distortion is real but the subtraction step is the fatal flaw: subtracting 8 × (edge count) requires knowing the edge count of the optimal path, which is exactly what you are trying to find. You cannot correct after the fact because the correction depends on the unknown answer.
The correct fix is to use an algorithm that handles negative weights, such as Bellman–Ford (O(VE)), which relaxes all edges V−1 times and correctly propagates the negative edge. If negative cycles exist, Bellman–Ford detects them. For a single source with negative edges but no negative cycles, Bellman–Ford is the right tool.
3. The company later adds a second rebate edge, creating a cycle X→Y→X with total weight −3. Explain the consequence and how to detect it.
Read the worked answer
A cycle with total negative weight means shortest paths are undefined: you can loop around the cycle arbitrarily many times, decreasing total cost without bound. There is no finite shortest path to any node reachable from the cycle. Any algorithm that reports a finite distance is wrong.
Detection: run Bellman–Ford. After V−1 relaxation rounds, perform one more pass over all edges. If any edge can still be relaxed (distance decreases), a negative cycle exists and is reachable. To identify which nodes are affected, run a traversal (BFS/DFS) from the nodes incident to the relaxable edge; every node reachable from them has distance −∞.
The dispatcher's problem is now ill-posed as stated. The company must either remove one of the rebate edges, cap the number of times the rebate can be applied, or reformulate the model so the rebate is a one-time credit rather than a per-traversal edge weight. This is the judgement the exam tests: recognising that a modelling choice (representing a rebate as a negative edge weight) can create a mathematically undefined problem, and that the fix may be in the model, not the algorithm.