Graph data structures are among the most important and exciting topics to learn in computer science because of their usage in several real-world applications like in Google Maps, Circuit Designing, etc.

A graph is a non-linear data structure containing points called nodes and links between them called edges. Now, let's say we have a weighted and directed graph (a graph whose edges have some weights assigned to them), and we select a source node from that graph. Dijkstra's algorithm answers if we want to know the shortest path between this node and all the other nodes.

In this article, we will find out why Dijkstra's algorithm fails on negative edge weights. The prerequisite for understanding this is the knowledge of weighted graphs and Dijkstra's algorithm.

What is Dijkstraâ€™s algorithm?

Dijkstra's algorithm is a greedy graph searching algorithm used to find the shortest path from a source node to all the other nodes. This algorithm only works for the weighted graph as it uses the weights of the edges to calculate the shortest path. For a detailed explanation of how Dijkstra's algorithm works for finding the shortest path, refer to this.

Let's see the requirements for this algorithm to work.

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}.

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

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.

What are directed graphs? A graph in which the edges are directed from one node to the other is called a directed graphs.

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.