Why does Dijkstra’s algorithm fail on negative weights?

Requirements for Djikstra’s algorithm to work

The requirements for making this algorithm work limit the applications of this algorithm. It only works in particular cases. 

The requirements are:

• The graph should be weighted and directed.
• The weights of the edges must be non-negative.

Let's see why this algorithm works only for graphs with non-negative edge weights.

Why does it fail on negative weights?

Let's understand this using an example. Suppose we have this graph having negative weights.

• The weight of edge from A->B = 5.
• The weight of edge from A->C = 2.
• The weight of edge from B->C = -10.

If we apply Dijkstra's algorithm to this graph with source as A,

The distance of node A from A will be 0; therefore, dis[A] = 0. 

Also, in Dijkstra's algorithm, we set the initial distances of all the nodes other than the source to infinity, therefore dist[B]= infinity and dist[C] = infinity. 

The priority_queue(PQ) will be containing the pairs consisting of {distance of a node from A, node}. 

• Initially, pq = [(0,A), (infinity,B), (infinity, C)]
• We pop out the pair (0,A) from the priority queue because it’s on the top and it has the smallest distance, after which, pq = [(infinity,B), (infinity,C)]. A has a directed edge to B and C, therefore, we update the distance of B and C. dist[B] = 0+5 = 5 and dist[C] = 0+2 = 2. Now, pq = [(2,C),(5,B)]. 
• We pop out the pair (2,C), now PQ = [(5,B)]. C doesn't have any edge to any node. Thus, we move ahead.
• Now, we pop out the last pair (5, B). Note that B has an edge to C with weight -10, but since C is not in PQ, it means the distance of C is already calculated. Thus we will not update the distance of C. 
• Now, the queue is empty and we have calculated the shortest distance of each node. dist[A]=0, dist[B] = 5 and dist[C] = 2.

Are these distances the shortest distance?

If you notice, rather than visiting C as A->C, we could have visited C as A->B->C. In this way, the distance would have been 5+(-10) = -5. Therefore, it is clear that Dijkstra's algorithm has failed to calculate the correct answer. 

But why does this happen?

It happens because, in each iteration, the algorithm only updates the answer for the nodes in the queue. So, Dijkstra’s algorithm does not reconsider a node once it marks it as visited even if a shorter path exists than the previous one.

Hence, Dijkstra's algorithm fails in graphs with negative edge weights.

Frequently asked questions

1. What is a graph?
   A graph is a non-linear data structure that contains elements called nodes or vertices, which are connected with the help of edges.
    
2. What are directed graphs?
   A graph in which the edges are directed from one node to the other is called a directed graphs.
    
3. What are weighted graphs?
   A graph in which each edge has some on it is called a weighted graph.

Key Takeaways

This article discussed why Dijkstra's algorithm doesn't work with graphs having negative edges. You can try submitting the solution to the shortest path problem with Dijkstra's algorithm here.

Here, you can read about another shortest path algorithm, called the Floyd Warshall algorithm. You can also try solving the shortest path problem on an unweighted graph.

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? 

Attempt our Online Mock Test Series on Coding Ninjas Studio now!

Happy Coding!