Skip to content
Graph Algorithms
Limitation of Dijkstra's Algorithm
Understanding the Limitation of Dijkstra's Algorithm with Negative Weights
Dijkstra's Algorithm is widely recognized for efficiently finding the shortest paths in a graph. However, it has a significant limitation—it doesn’t handle graphs with negative weight edges well.
To understand why this is a problem, let’s consider an example with five nodes: A, B, C, D, and E. By carefully examining how Dijkstra's Algorithm processes these nodes, we can clearly see where the algorithm falls short when negative weights are involved.
Example: A Graph with Five Nodes
In this graph:
Now, let's walk through what happens when we apply Dijkstra's Algorithm to this graph, starting from node A.
Initialization
The first step in the algorithm is to initialize the distances.
We know that the distance from A to itself is 0, so we start by setting A = 0.
For all the other nodes—B, C, D, and E—we initially set their distances to infinity, as we haven’t calculated any paths to them yet.
So, after initialization, the distances look like this:
Processing Node A
Next, we begin processing the nodes, starting with A.
A has two neighbours: B and C. We update the distances to B and C based on their direct connections to A.
After updating these distances, our current knowledge of the shortest distances looks like this:
Processing Node B
Now, we move on to node B, which has a neighbour, D. We calculate the distance to D through B:
The distance to D through B is 3, which is the sum of the distance to B (2) and the direct distance from B to D (1).
We update the distance to D. Now our distances look like this:
Processing Node C
Next, we process node C, which also has a neighbor, D. We calculate the distance to D through C:
However, since 7 is greater than the already known distance to D (which is 3), we do not update the distance to D. The distances remain:
Processing Node D
Finally, we process node D, which has a neighbor, E. We calculate the distance to E through D:
Here’s where the issue arises. The distance of -2 is shorter than any previously calculated distance to E.
In theory, Dijkstra's Algorithm should update this distance to reflect the shorter path.
However, Dijkstra’s Algorithm assumes that once the shortest path to a node is known, it doesn’t need to be revisited or updated.
This assumption fails in the presence of negative weights, and as a result, the algorithm would incorrectly maintain the distance to E as infinity instead of updating it to -2.
Conclusion
In this example, the correct shortest path to E should be through D, with a distance of -2.
However, because of the negative weight edge from D to E, Dijkstra's Algorithm fails to find the correct shortest path.
This example clearly illustrates why Dijkstra's Algorithm cannot handle graphs with negative weights.
When dealing with such graphs, alternative algorithms like Bellman-Ford are necessary, as they are designed to handle negative weights and can even detect negative cycles in the graph.
This example highlights the limitations of Dijkstra's Algorithm and underscores the importance of choosing the right algorithm for the right problem, especially when negative weights are involved.
Want to print your doc?
This is not the way.
This is not the way.
Try clicking the ⋯ next to your doc name or using a keyboard shortcut (
CtrlP
) instead.