A latency graph has 400 nodes and exactly one edge of weight -2, all others positive, with no negative cycle. Give an algorithm faster than Bellman-Ford for single source shortest paths on this instance and state its complexity.

A latency graph has 400 nodes and exactly one edge of weight -2, all others positive, with no negative cycle. Give an algorithm faster than Bellman-Ford for single source shortest paths on this instance and state its complexity.

Approach: A single negative edge can be used at most once on any shortest path. Run the non-negative algorithm twice and combine the two results.

O(E log V), by running Dijkstra twice. Let the single negative edge be (u,v) with weight -2. Any shortest path from the source s either avoids it or crosses it exactly once, since crossing it twice needs a cycle containing it and no negative cycle exists while every other weight is positive. Run Dijkstra on the graph with (u,v) deleted to get d1, which is valid because the remaining weights are non-negative, then run Dijkstra again from v on that same reduced graph to get d2. The true distance to any vertex x is min(d1(x), d1(u) - 2 + d2(x)). Each run is O(E log V) with a binary heap, so the total stays O(E log V) against Bellman-Ford at O(VE), which at 400 nodes is a factor of about 20 once both Dijkstra runs are counted, since V/(2 log2 V) is 400/17.3. Johnson's reweighting reaches the same distances in one pass at similar cost. The path decomposition is what makes two runs sufficient, and it generalises to k negative edges at a cost of one extra run per subset, which stops paying beyond a handful of them.

Follow-up: How would you detect quickly that a graph with several negative edges has no negative cycle before paying for the full algorithm?

Key concepts: dijkstra, single negative edge, path decomposition, reweighting.