Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is Dijkstra’s algorithm?
3.
Requirements for Djikstra’s algorithm to work
4.
Why does it fail on negative weights?
5.
Frequently asked questions
6.
Key Takeaways
Last Updated: Mar 27, 2024

Why does Dijkstra’s algorithm fail on negative weights?

Author Shreya Deep
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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!

Live masterclass