What Goes Wrong When an Edge Is Negative?
Dijkstra’s algorithm repeatedly settles the unsettled vertex with the smallest tentative distance label. With nonnegative edge weights, this greedy choice is safe: a route to that vertex cannot later be made cheaper by first travelling through a vertex whose label is larger. A negative edge breaks precisely this reasoning. A route that initially looks expensive can become cheaper after it passes through a negative edge, even if the algorithm has already settled the vertex it improves.
Throughout, graphs are finite directed graphs with real edge weights. Write an edge \(u\to v\) of weight \(w\) as \((u,v;w)\). A directed walk is a sequence of vertices whose consecutive pairs are directed edges; its cost is the sum of those edge weights. For a fixed source \(s\), the distance to \(v\) is the minimum cost of a directed walk from \(s\) to \(v\), when a minimum exists. If no such walk exists, the vertex is unreachable. If walk costs to \(v\) are unbounded below, there is no finite shortest-walk distance to \(v\).
For the examples, use the standard version of Dijkstra’s algorithm: initialize the source label to \(0\) and all other labels to \(\infty\); repeatedly select an unsettled vertex with smallest finite label, settle it, and relax its outgoing edges to unsettled vertices. Relaxing \(u\to v\) means replacing the label of \(v\) by the smaller of its current label and the label of \(u\) plus the edge weight. The settled set is treated as final, so a later improvement to a settled vertex is not used to revise its label or propagate that improvement.
The Greedy Assumption and Its Guarantee
Proof. First note why shortest-walk distances exist in this setting. Any walk that repeats a vertex contains a closed subwalk. Every such closed subwalk has nonnegative cost, because all its edges have nonnegative weight. Removing it gives a walk with the same endpoints and no greater cost. Repeating this removal produces a simple path with no greater cost. There are only finitely many simple paths in a finite graph, so if \(v\) is reachable, one of them has minimum cost. Denote that distance by \(d(s,v)\).
We prove by induction over the order in which reachable vertices are settled that each settled vertex \(u\) has label \(d(s,u)\). When the selected vertex is \(u=s\), its label is \(0\). Every walk from \(s\) back to \(s\) has nonnegative cost, while the length-zero walk has cost \(0\); hence \(d(s,s)=0\). This proves the initial case, including the source, which has no predecessor on a path from itself.
Now consider a later step, and suppose the claim holds for all previously settled vertices. Let \(u\ne s\) be the next vertex selected, and choose a shortest path \(P\) from \(s\) to \(u\). The source has already been settled. Along \(P\), let \(x\) be the first unsettled vertex, and let \(y\) be its predecessor. Such a predecessor exists because \(u\ne s\), and \(y\) is settled. When \(y\) was settled, the algorithm relaxed the edge \(y\to x\), so the current label of \(x\) is at most the cost of the prefix of \(P\) ending at \(x\). Since all edges on the remaining part of \(P\) have nonnegative weights, that prefix cost is at most the total cost of \(P\), which is \(d(s,u)\). Thus the label of \(x\) is at most \(d(s,u)\). The algorithm selected \(u\) with minimum label among unsettled vertices, so the label of \(u\) is no greater than the label of \(x\), and therefore is at most \(d(s,u)\).
Every finite label is the cost of some source-to-vertex walk: the source starts with the length-zero walk, and each relaxation extends a walk by one edge. Consequently the label of \(u\) cannot be less than \(d(s,u)\), the minimum cost of such a walk. Combining the two inequalities gives label\((u)=d(s,u)\), completing the induction. An unreachable vertex can never receive a finite label, since a finite label would have been created by extending a source-to-vertex walk. Therefore unreachable vertices remain at \(\infty\). \(\square\)
The key step is the comparison between the path prefix ending at \(x\) and the full path to \(u\). Nonnegative weights ensure that extending the prefix cannot reduce its cost. A negative edge can reverse that comparison, so the proof no longer guarantees that the smallest current label is safe to settle.
A Negative Edge Can Make the Answer Wrong
Worked Example: A Settled Vertex Is Improved Too Late
Let the directed weighted graph have vertex set \(V=\{s,a,b,t\}\) and edge set \(\{(s,a;2),(s,b;5),(b,a;-10),(a,t;2)\}\). Run Dijkstra’s algorithm from \(s\).
Initially the labels are \(s=0\), \(a=\infty\), \(b=\infty\), and \(t=\infty\). Settling \(s\) gives labels \(a=2\), \(b=5\), and \(t=\infty\). The smallest unsettled label is \(a=2\), so settle \(a\). Relaxing \(a\to t\) gives \(t=2+2=4\). The smallest unsettled label is now \(t=4\), so settle \(t\). Finally, \(b=5\) is settled. Its edge \(b\to a\) would give \(a=5+(-10)=-5\), but \(a\) is already settled and is not revised.
| Action | Labels after the action \((s,a,b,t)\) | Settled vertices |
|---|---|---|
| Initialize | \((0,\infty,\infty,\infty)\) | \(\varnothing\) |
| Settle \(s\); relax its edges | \((0,2,5,\infty)\) | \(\{s\}\) |
| Settle \(a\); relax \(a\to t\) | \((0,2,5,4)\) | \(\{s,a\}\) |
| Settle \(t\) | \((0,2,5,4)\) | \(\{s,a,t\}\) |
| Settle \(b\); its edge to \(a\) is ignored | \((0,2,5,4)\) | \(\{s,a,t,b\}\) |
The algorithm reports \(a=2\) and \(t=4\). But the walk \(s\to b\to a\) has cost \(5+(-10)=-5\), and the walk \(s\to b\to a\to t\) has cost \(5+(-10)+2=-3\). The other source-to-\(t\) route is \(s\to a\to t\), of cost \(2+2=4\). These are the only two source-to-\(t\) routes, so the true distance to \(t\) is \(-3\), not \(4\). Similarly, the two routes to \(a\) have costs \(2\) and \(-5\), so its true distance is \(-5\). The graph has no directed cycles, hence no negative cycle.
Check: The predecessor chain returned for \(t\) is \(s\to a\to t\), whose cost is \(2+2=4\), exactly the algorithm’s label. The cheaper route \(s\to b\to a\to t\) costs \(5-10+2=-3\), confirming the failure.
The failure is not that the algorithm cannot add a negative weight. It computes the candidate \(5+(-10)=-5\) correctly. The problem is that it made \(a\) final before processing \(b\), and its settled-vertex rule prevents the later improvement from being propagated to \(t\). The nonnegative-weight theorem rules out this situation by ensuring that a route through a vertex with a larger label cannot later improve the vertex already selected.
Negative Edges Do Not Always Cause Failure
Worked Example: Dijkstra Succeeds Despite a Negative Edge
Let \(V=\{s,a,b,t\}\), with directed weighted edge set \(\{(s,a;1),(s,b;4),(a,b;-2),(b,t;4),(s,t;5)\}\). Run Dijkstra’s algorithm from \(s\).
Initially the labels are \((0,\infty,\infty,\infty)\), in the order \((s,a,b,t)\). Settling \(s\) gives \(a=1\), \(b=4\), and \(t=5\). Next settle \(a=1\); relaxing \(a\to b\) gives \(b=\min(4,1-2)=-1\). Next settle \(b=-1\); relaxing \(b\to t\) gives \(t=\min(5,-1+4)=3\). Then settle \(t=3\). The labels are now \((0,1,-1,3)\).
To check them, the routes to \(a\) consist only of \(s\to a\), of cost \(1\). The routes to \(b\) are \(s\to b\), of cost \(4\), and \(s\to a\to b\), of cost \(1-2=-1\). The routes to \(t\) are the direct edge, of cost \(5\); \(s\to b\to t\), of cost \(4+4=8\); and \(s\to a\to b\to t\), of cost \(1-2+4=3\). Thus the algorithm’s labels agree with the minimum route costs. The graph has no directed cycles, so this negative edge is not part of a negative cycle.
Check: The recovered route to \(t\) is \(s\to a\to b\to t\). Its cost is \(1+(-2)+4=3\), matching the label \(t=3\).
This example shows why the correct conclusion is that Dijkstra’s guarantee requires nonnegative edge weights, not that every graph containing a negative edge must produce a wrong answer. On some such graphs, the vertex order happens to allow the useful negative edge to be processed before its head is settled. That success does not restore the general guarantee: the preceding example has a negative edge and causes a wrong result.
Negative Edges and Negative Cycles Are Different
A negative edge can occur in an acyclic graph, as in both examples above. A negative cycle has a different consequence for shortest-walk distances: repeating that cycle lowers the cost without bound. The condition that matters for a particular target is whether a negative cycle is reachable from the source and can itself reach that target.
Proof. Choose a walk from \(s\) to a vertex of the negative cycle, and a walk from a vertex of the cycle to \(t\). Join them by traversing the cycle as needed. Let the cycle have cost \(c<0\). For every positive integer \(k\), one obtains a source-to-\(t\) walk by traversing the cycle \(k\) times before continuing to \(t\). Its cost is the fixed cost of the joining walks plus \(kc\). Since \(c<0\), these costs decrease without bound as \(k\) increases. Therefore no finite minimum walk cost to \(t\) exists. \(\square\)
Worked Example: A Reachable Negative Cycle
Let \(V=\{s,a,b,t\}\), with directed weighted edge set \(\{(s,a;1),(a,b;-2),(b,a;1),(b,t;2)\}\). The cycle \(a\to b\to a\) has cost \(-2+1=-1\). It is reachable from \(s\), and from the cycle there is a route to \(t\).
Dijkstra’s run begins by settling \(s\), which gives \(a=1\). It settles \(a\), then relaxes \(a\to b\) to give \(b=1+(-2)=-1\). It settles \(b\); the candidate for already-settled \(a\) is \(-1+1=0\), which would improve \(a\), and the candidate for \(t\) is \(-1+2=1\). Under the stated settled-vertex rule, \(a\) is not revised. The algorithm then settles \(t=1\).
These finite labels cannot be shortest-walk distances. For example, the walk \(s\to a\to b\to a\to b\to t\) has cost \(1-2+1-2+2=0\), and each additional traversal of \(a\to b\to a\) reduces that cost by \(1\). Thus costs to \(t\) are unbounded below. The proposition explains why this is not merely a case where Dijkstra returns the wrong finite minimum: no finite minimum exists.
Check: One traversal of the cycle changes the cost by \(-2+1=-1\). Two traversals change it by \(2(-1)=-2\), so the displayed walk’s cost is \(1-2+1-2+2=0\), as stated.
A negative cycle reachable from \(s\) does not automatically make the distance to every vertex unbounded below. The cycle must also be able to reach the target. If it cannot, walks that visit the cycle cannot continue from it to that target; the target’s shortest-walk question must be considered separately.
Common Pitfalls
Wrong claim: “A negative edge means Dijkstra must fail.” In the second example, the edge \(a\to b\) has weight \(-2\), but Dijkstra settles \(a\) before \(b\), uses that edge to lower \(b\)’s label, and returns the correct distance \(3\) to \(t\). The correction is that negative weights remove the general correctness guarantee; whether a particular run fails depends on the graph and the order in which vertices are settled.
Wrong calculation: “The negative edge creates a negative cycle.” In the first example, the edge \(b\to a\) has weight \(-10\), but there is no directed route from \(a\) back to \(b\). It therefore lies on no directed cycle. A negative cycle requires a directed cycle whose entire edge-weight sum is negative; the sign of one edge alone is not enough.
Wrong assumption: “A finite output must be a shortest distance.” In the third example, Dijkstra outputs finite labels even though repeated traversal of a reachable negative cycle makes the cost to \(t\) arbitrarily small. Before interpreting an output as a shortest-walk distance, distinguish an incorrect finite label from a target for which no finite minimum exists.
Check Your Understanding
For each question, state the relevant assumptions and show the edge-weight sums that support your answer.
- In the first worked example, what is the cost of the route \(s\to b\to a\to t\), and at which step does Dijkstra fail to use it?
- Why does the proof of the nonnegative-weight guarantee need the weights on the remainder of path \(P\) to be nonnegative?
- Give the sequence of labels after settling \(s\) and then \(a\) in the second worked example.
- In the third worked example, how much does each additional traversal of \(a\to b\to a\) change the walk cost?
- Can a graph have a negative edge and no negative cycle? Justify your answer using one of the explicit examples.