Why Dijkstra's algorithm fails with negative edge weights

Dijkstra’s algorithm repeatedly picks the unsettled vertex with the smallest tentative distance from the source and makes that distance final. The 1959 paper describes it the same way: vertices whose minimum path is known are added to a set in increasing order of distance, and the answer is found once the destination joins that set.

Why the greedy choice is safe without negative weights

The choice is only safe if no later detour can make a distance smaller. When every edge weight is zero or more, a route through a vertex that isn’t settled yet can only add cost. So a cheaper route to the vertex with the smallest tentative distance can’t appear later. That property is what the greedy choice rests on.

A counterexample with three edges

One negative edge is enough to break the argument. Take a directed graph with S→A of weight 2, S→B of weight 5, and B→A of weight -4.

A directed graph with source S and vertices A and B. Edge S to A has weight 2, S to B has weight 5, and B to A has weight -4. An implementation that never revises a settled vertex settles A at distance 2 first, but the true shortest path is S→B→A, costing 5 + (-4) = 1. The graph has no negative cycle.

An implementation that, like the 1959 procedure, never revises a settled vertex settles A first, at 2. Yet the true shortest route, S→B→A, costs 5+(-4)=1. Going through B, which looked more expensive at first, shortens the distance to A after A was already settled. No negative cycle is needed for this.

The implementation decides the outcome

Still, “Dijkstra always gives a wrong answer with negative edges” is too broad. Princeton’s Algorithms text distinguishes two versions by whether a vertex can re-enter the priority queue. The version that allows re-entry finds the correct answer when there are no negative cycles, but can take exponential time in the worst case. The version that never processes a settled vertex again can return a wrong answer with negative edges. Both go by the same name; what matters is which invariant and guarantee an implementation relies on. The heap usually behind that priority queue is covered in A heap is not a sorted list.

What to use when there are negative edges

For single-source shortest paths with negative weights, consider Bellman–Ford. It also detects a negative cycle reachable from the source, and its worst-case running time is proportional to VE, where V is the number of vertices and E the number of edges.

If the graph is a DAG (directed acyclic graph), relaxing edges in topological order works even with negative edges, in time proportional to V+E.

A reachable negative cycle lowers the path cost every time it is traversed, so no finite shortest path exists to destinations reachable through it. That is why the presence of a negative edge isn’t the only thing to check: whether a negative cycle is reachable from the source, and whether the graph is a DAG, matter too.

Check the library’s documentation separately

Library behavior is a separate question from the mathematical guarantee. SciPy’s documentation defines the input to scipy.sparse.csgraph.dijkstra as non-negative distances, says the routine does not work with negative distances, and points to algorithms such as Bellman–Ford or Johnson instead (checked October 4, 2026). Whether another library warns, throws, or returns a wrong result is something to check in the documentation for the version you use.

Documentation used

Links and content were checked on October 4, 2026. The SciPy documentation can change between versions.