Dijkstra’s Algorithm

Dijkstra’s algorithm is a basic and efficient algorithm for finding the shortest path in a graph with non-negative weighted edges. It is the most used algorithm for finding an optimal solution for the shortest pathfinding problems in graph theory. Whether you have to develop GPS navigation systems or work on AI pathfinding systems, you can use Dijkstra’s algorithm for efficient and fast performance. In this article, we will discuss what Dijkstra’s algorithm is, its working, pseudocode, example, and implementation in different programming languages. Additionally, we will discuss the advantages, disadvantages, applications, and comparisons with the Bellman-Ford algorithm.

Table of Contents:

• What is Dijkstra’s Algorithm?
• Working of Dijkstra’s Algorithm
• Dijkstra’s Algorithm – Pseudocode
• Dijkstra’s Algorithm Example
• Time and Space Complexity of Dijkstra’s Algorithm
• Implementation of Dijkstra’s Algorithm
• Advantages of Dijkstra’s Algorithm
• Disadvantages of Dijkstra’s Algorithm
• Applications of Dijkstra’s Algorithm
• Dijkstra’s Algorithm vs Bellman-Ford Algorithm
• Conclusion

What is Dijkstra’s Algorithm?

Dijkstra’s Algorithm is a graph search algorithm that is used to find the shortest path between a starting node and all the other nodes in a weighted graph, where all edge weights are non-negative. It was designed by Dutch computer scientist Edsger W. Dijkstra. It generally works by gradually exploring the nearest unvisited node and updating the shortest path to each neighbouring node. When the shortest path of a node is found, it is marked as visited. Later, the algorithm moves on to find the shortest path to a specific target by visiting all other nodes that have not been visited yet. Dijkstra’s algorithm is a type of greedy algorithm, and it only works on a weighted graph with edges of positive weights. 

Working of Dijkstra’s Algorithm

Dijkstra’s Algorithm needs a graph and a vertex to start finding the shortest path. This algorithm is based on a greedy approach, which means it makes the optimal choice at each step and selects the node with the smallest distance.

Here is a step-by-step description of how Dijkstra’s algorithm works.

Step 1: Initialization

• At first, choose a starting node, which is called the source node.
• Now, set the distance to the source as 0, and the distance to all other nodes as infinity.
• Then, mark all nodes as unvisited.
• Now, create a priority queue or a min-heap to keep track of all nodes with the shortest distances.

Step 2: Visit the Current Node

• Now, start with the source node initially.
• And, for each of its unvisited neighboring nodes, calculate the distance from the source node.
• If the distance is smaller than the previously calculated distance, then update it.

Step 3: Mark as Visited

• When all the neighboring nodes are checked, mark the current node as visited.
• The visited nodes will not be checked again, as the shortest distance between them is already calculated.

Step 4: Repeat

• Now, select the next unvisited nodes with the smallest distance.
• Repeat steps 2 and 3 until all the nodes are visited or you have reached the target node.

Step 5: Final Output

• The algorithm stops when all the shortest paths from the source node are found.
• Now, you have the shortest distance to each node and can also reconstruct the shortest paths if you stored the previous nodes.

Now, let’s understand what a min-heap is that we have used above in Dijkstra’s algorithm:

Min-Heap

A min heap is a complete binary tree where the value of each parent node is less than or equal to the values of its child nodes. This makes sure that the smallest element is always at the root of the heap. Min heaps are typically implemented using arrays for efficient storage and indexing. Insertion and deletion operations maintain the heap property using “heapify” procedures. They are commonly used in algorithms like Dijkstra’s and in priority queues. Also, the time complexity for insertion and deletion in a min-heap is O(log n), while retrieving the minimum is O(1).

Dijkstra’s Algorithm – Pseudocode

function Dijkstra(Graph, source):

    create distance map: set all distances to infinity
    set distance[source] = 0

    create a priority queue and add source with distance 0

    while the priority queue is not empty:
        current_node = node with smallest distance in queue
        mark current_node as visited

        for each unvisited neighbor of current_node:
            tentative_distance = distance[current_node] + weight(current_node, neighbor)

            if tentative_distance < distance[neighbor]:
                distance[neighbor] = tentative_distance
                add neighbor to the queue with updated distance

    return distance

Become a Python Certified Professional!

Enroll now to master Python with expert-led live sessions.

Explore Program

Dijkstra’s Algorithm Example 

In this example, we are finding the shortest distance from City A to all other cities. 

Here’s the map of cities with the distance between them.

Cities (Nodes): A, B, C, D, E, F
Edges and Weights (Distances):

Now, here is a step-by-step execution to solve a problem to find the shortest path.

Step 1: Initialization

• Start from node A, and since node A is the source node, set its distance equal to 0.
• Set the distance of all other nodes to infinity, to represent that those nodes are initially unreachable from the starting node.
• Use the min-heap data structure to select the city with the current shortest distance.

And, the current Min Heap is [(0, A)].

Step 2: Visit the Nodes or Cities, and Update the Path

Now, visit each city one by one and keep updating the shortest distance.

1. Visit City A

At first, City A is visited because after initialization, it is the only city with the smallest value 0. So, we will push the node A into the min-heap.

Node A is the only node in the min heap.

Now, we will explore all the neighbours of city A.

• A -> B: dist[B] = min(0+ 4) = 4
• A -> C: dist[C] = min(0+ 2) = 2
• A -> D: dist[D] = min(0+ 1) = 1

So, update the distance:

• B’s distance to 4
• C’s distance to 2
• D’s distance to 1

These updated nodes (B: 4, C: 2, D: 1) are then pushed into the min heap to be processed in order of their current shortest distances.

So, Min Heap: [(1, D), (2, C), (4, B)]

2. Visit the City D

In Dijkstra’s algorithm, we always choose the node with the smallest current distance from the min heap. So, after pushing cities B (4), C (2), and D (1) into the min heap, D has the smallest distance (1), so it is the next node to be popped (visited).

Now, pop (1, D) from the heap, because D has the smallest distance now.

Then, explore all neighbours of D.

• D -> E: dist[E] = min(1+ 5) = 6
• D -> F: dist[F] = min(1+ 8) = 9

So, update the distance:

• E’s distance to 6.
• F’s distance to 9.

These new distances (E:6, F:9) are then pushed into the heap for future processing.

Current Min Heap: [(2, C), (4, B), (6, E), (9, F)]

3. Visit Node C

After processing D (with distance 1), the heap contains: (4, B), (2, C), (6, E), (9, F). Now, pop (2, C) from the heap because C has the smallest distance now.

Then, explore all neighbours of C.

• C -> F: dist[F] = min(2+ 3) = 5

So, update the distance:

• F’s distance to 5.

Now, (5, F) is then pushed into the heap to show the shorter path through C.

Min Heap: [(4, B), (6, E), (9, F), (5, F)]

4. Visit Node B

After the previous steps, the min heap contains something like: (5, F), (6, E), (4, B). Now, pop (4, B) from the heap because B has the smallest distance now.

Then, explore all neighbours of B.

• B -> E: dist[E] = min(4+ 5) = 9

But E already has a better and smaller path 6, so no need to update E.

Min Heap: [(5, F), (6, E)]

5. Visit Node F

Now, pop (5, F) from the heap, because F has the smallest distance now.

Then, all the neighbours of F have already been visited.

Min Heap: [(6, E)]

6. Visit Node E

Now, pop (6, E) from the heap because E has the smallest distance now.

Then, all the neighbours of E have already been visited and have a shorter path, thus there will be no change.

Now, the Min Heap is empty, and then the algorithm ends. 

Step 3: Final Shortest Paths from City A to all Other Cities

Thus, the above table is the final update table of shortest paths from City A. 

Time and Space Complexity of Dijkstra’s Algorithm

Here is a brief description of the time and space complexity of Dijkstra’s Algorithm.

Time Complexity of Dijkstra’s Algorithm

The time complexity of Dijkstra’s Algorithm is based on two factors:

1. The data structure used for the priority queue (min heap).
2. The representation of the graph using a matrix or an adjacency list.

Now, let’s take 

• V = number of vertices (nodes)
• E = number of edges

1. Using a min-heap (priority queue) + adjacency list

The time complexity while using a min-heap (priority queue) + adjacency list is O((V + E) * log V) in total. Because each vertex can be inserted into the heap at most one time, its complexity is O(V log V), each edge can also cause insertion in the heap. So its complexity is O(E log V), and the complexity of heap operations (insert, pop) is O(log V).

This is the most efficient and commonly used version of Dijkstra’s algorithm.

2. Using an adjacency matrix + no heap (simple array for min search)

The time complexity while using an adjacency matrix + no heap is O(V^2) in total, because finding the minimum distance between each node takes O(V) time. This is repeated for each vertex, so it takes O(V*V) time.

This version is slower and less efficient.

Space Complexity of Dijkstra’s Algorithm

The space complexity is also based on the version of Dijkstra’s Algorithm used:

1. Using a min-heap (priority queue) + adjacency list

The space complexity of Dijkstra’s Algorithm is O(V+E), because the min heap takes O(V) space, and the adjacency list takes O(E) space for storing the graph.

2. Using an adjacency matrix + no heap (simple array for min search)

The space complexity of Dijkstra’s Algorithm is O(V^2), because the array takes O(V) space, and it is repeated for each vertex.

Here is a table for the precise understanding of the time and space complexity of Dijkstra’s Algorithm.

Implementation of Dijkstra’s Algorithm

1. Implementation of Dijkstra’s Algorithm in C++

Output:

Explanation:

• The above C++ program shows how Dijkstra’s Algorithm is used in C++ programming to find the shortest paths from a source node to all other nodes in a weighted graph using a min-heap.
• An adjacency list (vector<pair<int, int>> adj[]) is used in the code to represent the graph, in which each pair represents a neighbour and the edge weight.
• The dijkstra() function is used to maintain a distance array and update it by exploring the shortest distance node from the priority queue at first.
• Finally, after processing all the nodes, the main function prints the shortest paths from the source 0 to every other node.

2. Implementation of Dijkstra’s Algorithm in JAVA

Output:

Explanation:

• The above JAVA program shows how Dijkstra’s Algorithm is used in JAVA programming to find the shortest paths from a source node to all other nodes in a weighted graph using a min-heap.
• An adjacency list (List<List<int[]>>) is used to represent the graph, in which each int[] stores a neighbour and the weight.
• Also, a custom Pair class is used to store the (distance, node) pairs and enable the sorting based on the distance using compareTo.
• Finally, the main function prints the shortest paths from the source to each node.

3. Implementation of Dijkstra’s Algorithm in Python

Output:

Explanation:

• The above Python program shows how Dijkstra’s Algorithm is used in Python programming to find the shortest paths from a source node to all other nodes, in a weighted graph using a min-heap (heapq).
• An adjacency list (adj) is used to represent the graph, in which each node has a list of tuples (neighbour, weight).
• The algorithm updates the shortest path (dist[]) by visiting all the nearest unvisited nodes from the heap.
• Finally, the function prints the shortest paths from the source to each node.

Advantages of Dijkstra’s Algorithm

• Gives Optimal Solution: Dijkstra’s algorithm will always produce the least-cost or shortest path from a source node to all other nodes in a graph, with nonnegative edge weights. 
• Efficient: With a min-heap (i.e., priority queue), Dijkstra’s algorithm is efficient and has a good time complexity.
• Most Used Algorithm: Dijkstra’s algorithm is commonly used in routing protocols and GPS systems, as it produces a least-cost and least-time path. 
• Can be used with Directed and Undirected Graphs: With directed and undirected graphs (must have positive edge weights), Dijkstra’s algorithm can be used.

Disadvantages of Dijkstra’s Algorithm

• Does not work with the Negative Weights: Dijkstra’s algorithm does not work with a graph with negative edge weights; It fails or gives incorrect results.
• Inefficient for Large Dense Graphs: It gives a very low performance when applied to dense graphs with many edges and nodes, even if a min-heap is used.
• Has a Single Source Node Only at a Time: Dijkstra’s algorithm finds the shortest path only from a single source node at a time. It will fail if you need all-pairs shortest paths.
• Does not Track Actual Path: The basic version of this algorithm does not store the actual path; It only stores the distances between the nodes. You have to give additional logic to store the actual path route.

Applications of Dijkstra’s Algorithm

• Dijkstra’s algorithm is used by GPS-based navigation systems, for example, Google Maps, Waze, and other GPS devices to locate and determine the shortest route from the starting point to the destination. In these systems, it takes travel time or distance on the road as edge weights.
• Dijkstra’s algorithm is also used for network routing in routing protocols such as OSPF (Open Shortest Path First), to find the best and shortest path when transferring data packets. This is extremely useful in reducing congestion or traffic across the routers.
• City planners also use the Dijkstra algorithm to plan for traffic flow, find signal timing or actual road construction that can minimize traffic and travel time.
• Dijkstra’s algorithm is also used by AI pathfinding systems, mainly in video games and simulations, to plan and navigate effectively and efficiently through a mapped area.
• Companies like FedEx, Amazon, etc. use Dijkstra’s algorithm to find the shortest routes to save money on time and fuel. They also use Dijkstra’s algorithm in warehouse path planning.

Unlock Your Tech Career with Free Python Certification!

Enroll Now! Learn Python Online – Anytime, Anywhere, for Free!

Explore Program

Dijkstra’s Algorithm vs Bellman-Ford Algorithm

The table below compares the Dijkstra and the Bellman-Ford algorithms based on various parameters such as suitability for the graph, edge weights, time and space complexity, and application. The comparison side-by-side facilitates the understanding of when and why a specific algorithm should be given preference based on the nature of the graph and the need for the problem.

Conclusion

Dijkstra’s algorithm is the most widely used pathfinding algorithm, which uses a graph data structure. It is widely used in our real life to find the shortest path to save time, energy, and solve problems such as efficient path planning, navigation, and routing. This algorithm gives efficient performance with a min heap, but it also has some limitations, such as it does not work with negative weights, and needs additional logic to store the actual path routes. So, by understanding Dijkstra’s algorithm with its working, pseudocode, implementations, advantages, disadvantages, and applications, you can easily use this algorithm to solve any problem related to finding a shortest path in programming.

Dijkstra’s Algorithm – FAQs