Dijkstra Algorithm

Pranjal Bhardwaj
6 min readMar 24, 2021

Design And Analysis of Algorithms

Dijkstra Algorithm is used to find the shortest distance from a given node to all the other nodes present in the graph. It may be a directed or an undirected graph.

Dijkstra Algorithm was created and published by Dr. Edsger W. Dijkstra, a brilliant Dutch computer scientist.

Introduction

Dijkstra Algorithm is used to create a shortest path tree. This is used to find the shortest distance from the given Node (Source) to all the other nodes present in the graph. Each node is connected to other nodes with a given weight which is used to calculate the distance between the nodes. This algorithm can be used in directed as well as undirected graph. This algorithm can also be used to find the shortest distance between two nodes, where one of them is the source node and the other is the destination node by structuring the algorithm in such a way that it breaks when the distance between the two nodes is finalised.

The algorithm works on the logic where we overestimate the distance of each vertex from the source vertex. Then we visit all the nodes and its neighbours and find the shortest subpath to those neighbouring nodes. This algorithm used greedy approach as we keep on finding the next best solution hoping that the result in the end would be the best solution of the problem.

Example

Suppose we are given a graph with the nodes A B C D E F and G. We can see that this is a directed graph. Each edge has a weight associated to it.

Lets suppose that the node A is the source node. Now we have to create the shortest path tree, and find all the shortest distance from the Source Node A to the all the other nodes.

Step 1:
In the first step we initialise the source node to 0 and the other nodes to infinity since we do not know how far the node is from the source node. So we assume the distance to be infinity.

Step 2:
Finding the smallest minimum distance value from the set that contains all the nodes whose edges have not been relaxed yet.
Here since we have only two value 0 and Infinity, the smallest distance value is zero. Therefore we select the node 0 and relax all the outgoing edges.

Relaxing an edge is the updating the path length of the adjacent vertex if the new path is less than the original path length.

Step 3:
Relax the outgoing edges of the selected node and remove the node from the set. In this case we relax the edges from A to B and A to C. And change the path length from infinity to respective path lengths.

Now repeating the same steps 2 and 3, we find the minimum distance value from the available nodes in the set { B, C, D, E, F, G}. In this case the node B has the minimum distance value i.e 1 therefore we relax all the outgoing edges from the node B.

Now we have nodes C, D, E, F, G in the set and we find the minimum distance value i.e 2 (Node C) in this case. Therefore we relax all the outgoing edges from the node C.

Now we have the nodes D, E, F, and G in the set. We again find the minimum distance values from the set i.e Node D (3) in this case. Therefore we relax all the outgoing edges from the Node D.

Now we have nodes E, F and G in the set. Now we find the minimum distance value from the set which is 4 (Node F) in this case. Therefore we relax the edges outgoing from the node F.

Now we can see that all the edges are relaxed and even though there are nodes present in the set, we remove them from the set since they do not any outgoing edges.

Now we have the shortest path tree. This can be used to find the smallest distance from the source to any other node present in the graph.

Pseudocode

function dijkstra(G, S)
for each vertex V in G
distance[V] <- infinite
previous[V] <- NULL
If V != S, add V to Priority Queue Q
distance[S] <- 0

while Q IS NOT EMPTY
U <- Extract MIN from Q
for each unvisited neighbour V of U
tempDistance <- distance[U] + edge_weight(U, V)
if tempDistance < distance[V]
distance[V] <- tempDistance
previous[V] <- U
return distance[], previous[]

In the pseudocode, I have made the first loop for the initialisation of the vertices. The source node is initialised to 0 and all the other nodes are initialised to infinity. Then we have the set in the priority queue which finds the minimum distance value from the queue. Then until all the elements are removed from the queue, we find the node with the smallest distance value and relax its edges.

Time Complexity

The time complexity of the Dijkstra algorithm is O(E Log V ).
Here V is the number of vertices in the graph and E is the total number of edges in the graph.

Space Complexity

The space complexity of Dijkstra algorithm is O(V).

Disadvantage of Dijkstra

Dijkstra algorithm has a disadvantage when it comes to graphs with negative weighted adges. The algorithm may or may not give the correct answer when there are negative edges present in the graph. The algorithm does not always give the wrong answer for the negative edges in the graph. Following is a small example that shows that the algorithm can give a correct answer with negative edges present in the graph.

On applying the Dijkstra algorithm on the given graph we get the following shortest path tree.

Here we can see that even though there is a negative edge present in the graph we have the shortest path tree.

But there are cases when there is a negative weight cycle in the graph due to the presence of the negative weights which leads to a infinite cycle in the algorithm that leads to decrease in the path length in every iteration. Following is the example to show the failure of the algorithm due to the presence of the negative weight cycle.

In the given graph the nodes are A, B, C and D. but we have changes in the edges. the weight from node C to D is now positive and 1. and we have another node from C to B (reverse) of weight -3, which creates the negative weight cycle. Now if use Dijkstra algorithm on the graph we find that if we calculate the path from Source node A to node B via C, we can find a shorter route i.e (1 + 2 + -3 = 0) which is less than previously calculated distance 1. Therefore the algorithm will run in a loop where it would constantly keep on getting a smaller distance than the previously calculated distance.
Therefore we do not use Dijkstra algorithm when there is presence of negative weight cycles and negative weights.

Thank you

Pranjal Bhardwaj
E19CSE432

--

--