No, Dijkstra’s algorithm cannot correctly handle negative edge weights. It may produce incorrect shortest-path distances, and it has no built-in mechanism to detect that its results are wrong. The algorithm’s core logic depends on the assumption that adding more edges to a path can only increase its total cost, an assumption that breaks the moment a negative weight enters the picture.
Why Negative Weights Break the Algorithm
Dijkstra’s algorithm works by visiting nodes in order of their current shortest known distance from the source. Once a node is visited (or “closed”), the algorithm considers its distance final and never revisits it. This greedy approach is what makes Dijkstra fast, running in O(E log V) time with a standard priority queue. But it only works because of one critical guarantee: if all edge weights are zero or positive, no future path through an unvisited node can possibly produce a shorter route to an already-visited node.
Negative weights destroy that guarantee. Suppose the algorithm has already finalized node C with a distance of 3. Later, it processes node D and discovers an edge from D to C with weight -5. The true shortest path to C through D might be 1, but the algorithm will never find it because C has already been locked in at 3. The result is silently wrong, with no error or warning.
To put it more precisely: when Dijkstra picks a node C from the queue, it reasons that every other unvisited node has an equal or greater distance, so no path through those nodes could improve C’s distance. That reasoning holds only when every edge along such a path adds non-negative cost. A single negative edge can create a shortcut that the algorithm has already ruled out.
What Happens With Negative Cycles
A negative cycle is a loop in the graph whose edges sum to a negative total. Each time you traverse the loop, the path cost decreases, meaning there’s no true “shortest path” since you could loop forever. Dijkstra’s algorithm has no ability to detect negative cycles. Research on modified versions of Dijkstra has shown that when a negative cycle exists, the algorithm simply does not terminate. It keeps trying to relax edges around the cycle indefinitely, never converging on an answer. This is a dangerous failure mode because you get neither a correct result nor a clear error.
Algorithms That Do Handle Negative Weights
When your graph contains negative edge weights, you need a different algorithm. The most common choice is Bellman-Ford, which systematically relaxes every edge up to V-1 times (where V is the number of vertices). This approach doesn’t rely on the greedy assumption that finalized nodes stay finalized. Instead, it repeatedly checks whether any edge offers a shorter path, allowing corrections that Dijkstra can’t make. The tradeoff is speed: Bellman-Ford runs in O(V × E) time, which is significantly slower than Dijkstra’s O(E log V) on large graphs. It does, however, detect negative cycles. If any distance is still decreasing after V-1 rounds of relaxation, the algorithm reports that a negative cycle exists.
For directed acyclic graphs (DAGs), there’s a faster option. Because a DAG has no cycles at all, you can process nodes in topological order and relax each edge exactly once. This runs in O(V + E) time and handles negative weights perfectly, since the absence of cycles means you’ll never need to revisit a node. If your graph happens to be a DAG, this is the best approach regardless of whether weights are negative.
Johnson’s Algorithm for All-Pairs Shortest Paths
If you need shortest paths between every pair of nodes in a graph with negative weights, Johnson’s algorithm offers a clever workaround that actually uses Dijkstra as a subroutine. The trick is called “reweighting.” The algorithm first adds a temporary vertex connected to every node with zero-weight edges, then runs Bellman-Ford once from that temporary vertex to compute a potential value for each node.
These potential values are used to transform every edge weight using a simple formula: the new weight of an edge from u to v equals the original weight plus u’s potential minus v’s potential. This transformation has two important properties. First, it makes all edge weights non-negative, so Dijkstra can safely run on the modified graph. Second, it preserves shortest paths. Any path that was shortest in the original graph is still shortest in the reweighted graph, because every path between the same two endpoints shifts by exactly the same amount. After running Dijkstra from each vertex on the reweighted graph, you reverse the transformation to recover the true distances.
Johnson’s algorithm runs Bellman-Ford once in O(V × E) time, then Dijkstra V times for a total of O(V × E log V). For sparse graphs, this is faster than running Bellman-Ford V times, which would cost O(V² × E).
Can Dijkstra Ever Work With Negative Weights?
In rare, specific cases, Dijkstra might happen to return the correct answer on a graph with negative weights. This occurs when the negative edges don’t actually create any shorter path to an already-finalized node. But there’s no way to know this in advance without essentially solving the problem a different way first. You can’t look at a graph with negative weights and predict whether Dijkstra will get lucky.
Some modified versions of Dijkstra allow nodes to be re-added to the priority queue when a shorter path is found. This can produce correct results on graphs with negative weights but no negative cycles. The cost is that a node might be processed multiple times, and in the worst case the algorithm’s runtime degrades to exponential. If a negative cycle exists, this modified version will loop forever.
The practical rule is straightforward: if any edge weight in your graph is negative, don’t use standard Dijkstra. Use Bellman-Ford for single-source shortest paths, topological relaxation if your graph is a DAG, or Johnson’s algorithm if you need all pairs.