Recipe

Audit a Dijkstra run for negative-edge corruption

Use when: a graph has at least one negative edge weight and you need to know whether Dijkstra's reported distances can actually be trusted

Goal: either a corrected distance where Dijkstra was wrong, or confirmation that every negative edge in the graph was harmless

Taught in Why Dijkstra's algorithm fails on negative weights

1. 1

   Proceed through the ordinary algorithm, settling one vertex at a time, and write down each vertex's settled distance along with the order it settled in. This step doesn't need to know a negative edge exists yet.

   Example

   On P,U,V with P\to V (2), P\to U (5), U\to V (-4): settle P (0); relax V \leftarrow 2, U \leftarrow 5; settle V (2) next, since it's the smaller unsettled distance; settle U (5) last.

   Why: the corruption, if any exists, can only be found by comparing against the distances this ordinary run actually produced.

2. 2

   For each edge w \to u with negative weight, compare the two settling times from Step 1. The edge is only worth checking further if w settled after u already had.

   Example

   The one negative edge here is U \to V. From Step 1's order, V settled before U, so this edge is a genuine candidate worth checking.

   • the negative edge's tail settled before its head — that edge could never offer a cheaper route into an already-final vertex, so no corruption is possible from it.
   • the negative edge's tail settled after its head — continue to Step 3 and test the edge directly.

   Why: a negative edge can only threaten a settled distance if its own tail wasn't finalized yet at the moment the head was locked in.

3. 3

   Add the tail's final settled distance to the edge's weight. If that sum is smaller than the head's settled distance, the settled value was wrong.

   Example

   U's final distance is 5, and 5+(-4)=1, which is less than V's settled distance of 2. Dijkstra's reported d(V)=2 is therefore wrong; the true value is 1.

   • the computed sum is smaller than the settled distance — the algorithm's reported answer for that vertex is wrong.
   • the computed sum is not smaller — this particular negative edge never actually endangered the answer, even though its tail settled late.

   ⚡ Shortcut

   On a tiny graph, it's often faster to just list every path from source to the vertex in question and add up each one's weight directly, skipping the audit above entirely. Comparing P\to V (weight 2) against P\to U\to V (weight 1) settles the true distance immediately, the same two numbers Step 3 already found.

   Why: this is exactly the comparison Dijkstra itself skipped by refusing to reconsider a settled vertex, so redoing it by hand is the only way to catch the mistake.