Understanding Dijkstra’s Algorithm
Introduction
Dijkstra’s algorithm is a fundamental concept in the field of computer science, specifically in the realm of algorithm design and analysis.
It is named after the Dutch computer scientist Edsger W. Dijkstra, who introduced it in 1956 and three years later published.
This algorithm is widely used for finding the shortest path between nodes in a graph, especially in scenarios where the graph contains non-negative weights on its edges.
.
How It Works
Dijkstra’s algorithm works by iteratively exploring nodes in a graph, gradually building up the shortest paths from a designated source node to all other nodes.
.
History of Dijkstra’s Algorithm
When working as a programmer at the Mathematical Centre in Amsterdam in 1956, Dijkstra considered the shortest path issue in order to illustrate the capabilities of a new computer known as ARMAC.
His goal was to select both a problem and a solution (generated by a computer) that non-computer users could understand.
He created the shortest path algorithm and later implemented it for ARMAC, which used it to create a somewhat simplified transport map of 64 Dutch cities (6 bits would be sufficient to encode the city number).
Edsger W. Dijkstra independently developed an algorithm similar to Prim’s minimum spanning tree algorithm, which was initially discovered by Zernike and later rediscovered by Prim. Dijkstra’s publication of the algorithm occurred in 1959, coming two years after Prim’s and 29 years subsequent to Zernike’s discovery.
.
Algorithm of Dijkstra’s Sort
- Initialization
- Assign a source node from which the shortest paths will be calculated.
- Create a set to keep track of visited nodes.
- Initialize an array or data structure to store the shortest distances from the source to each node.
- Set the distance of the source node to 0 and all other nodes to infinity.
- Iteration
- While there are unvisited nodes
- Select the unvisited node with the smallest known distance as the current node.
- Mark the current node as visited.
- Update Distances
- For each neighbouring node of the current node that is still unvisited,
- Calculate the tentative distance from the source to the neighbouring node through the current node.
- If the tentative distance is shorter than the current known distance to that neighbouring node, update the distance.
- Repeat
- Repeat steps 2 and 3 until all nodes are visited or the destination node is reached.
Â
- Result
- Once the algorithm completes, the array or data structure containing the shortest distances will provide the shortest path from the source node to all other nodes in the graph.
.
Example
Let’s consider a road network represented as a graph where cities are the nodes and roads between cities are the edges. We’ll use Dijkstra’s algorithm to find the shortest path from a source city to a destination city.
The following graph displays the houses P, Q, R, S, T, U, V, and W as vertices, and the roads connecting them as edges. The time, expressed in hours, that the car takes to drive between each house is indicated by the numbers on the sides.
.
Step 1 – Start at the source node (let’s say A) with distance 0 and all other nodes to infinity.
.
Step 2 – We mark the node A as visited.
A —> B, Cost of AB is 3, (Shortest Distance)
A —> E, Cost of AE is 4
A —> H, Cost of AH is 5
We have to find the minimum cost. So, we update the shortest distance (AB, 3).
Â
.
Step 3 – We mark the node B as visited.
A —> B —> C, Cost of ABC is 8
A —> B —> E, Cost of ABE is 5
A —> E, Cost of AE is 4, (Shortest Distance)
A —> H, Cost of AH is 5
We have to find the minimum cost. So, we update the shortest distance (AE, 4).
.
Step 4 – We mark the node E as visited.
A —> B —> C, Cost of AC is 8
A —> E —> F, Cost of AEF is 6
A —> E —> G, Cost of AEG is 7
A —> H, Cost of AH is 5, (Shortest Distance)
We have to find the minimum cost. So, we update the shortest distance (AH, 5).
.
Step 5 – We mark the node H as visited.
A —> B —> C, Cost of AC is 8
A —> E —> F, Cost of AEF is 6, (Shortest Distance)
A —> E —> G, Cost of AEG is 7
A —> H —> G, Cost of AHG is 7
We have to find the minimum cost. So, we update the shortest distance (AEF, 6).
.
Step 6 – We mark the node F as visited.
A —> B —> C, Cost of AC is 8
A —> E —> F —> D, Cost of AEFD is 7, (Shortest Distance)
A —> E —> G, Cost of AEG is 7
A —> H —> G, Cost of AHG is 7
We have to find the minimum cost. So, we update the shortest distance (AEFD, 7).
.
Step 7 – We mark the node D as visited.
A —> B —> C, Cost of AC is 8
A —> E —> G, Cost of AEG is 7, (Shortest Distance)
A —> H —> G, Cost of AHG is 7
We have to find the minimum cost. So, we update the shortest distance (AEG, 7).
.
Step 8 – We mark the node G as visited.
A —> B —> C, Cost of AC is 8, (Shortest Distance)
We have to find the minimum cost. So, we update the shortest distance (ABC, 8).
Also, mark the node C as visited.
Dijkstra’s Algorithm is complete.
.
Note – I have just solved an array which has the shortest distance from source node A to the remaining vertices. This is the single source shortest path which we have come across now.
If I declare all the vertices as source nodes and find the shortest path of all the vertices then I use All pair shortest path.
.
Source Code of Dijkstra’s Algorithm
// COMPUTER GEEK – compgeek.co.in
// Write a program for Dijkstra’s Algorithm
Â
#include <stdio.h>
#include <limits.h>
Â
#define V 9 // Number of vertices in the graph
Â
// Function to find the vertex with the minimum distance value
int minDistance(int dist[], int visited[])
{
   int min = INT_MAX, min_index;
Â
   for (int v = 0; v < V; v++)
  {
       if (visited[v] == 0 && dist[v] <= min)
    {
           min = dist[v];
           min_index = v;
       }
   }
Â
   return min_index;
}
Â
// Function to print the constructed distance array
void printSolution(int dist[])
{
   printf(“Vertex \t Distance from Source\n”);
   for (int i = 0; i < V; i++)
  {
       printf(“%d \t %d\n”, i, dist[i]);
   }
}
Â
// Function that implements Dijkstra’s single source shortest path algorithm
void dijkstra(int graph[V][V], int src)
{
   int dist[V]; // The output array. dist[i] will hold the shortest distance from src to i
   int visited[V]; // visited[i] will be true if vertex i is included in the shortest path tree
Â
   // Initialize all distances as INFINITE and visited[] as 0
   for (int i = 0; i < V; i++)
  {
       dist[i] = INT_MAX;
       visited[i] = 0;
   }
Â
   // Distance of source vertex from itself is always 0
   dist[src] = 0;
Â
   // Find shortest path for all vertices
   for (int count = 0; count < V – 1; count++)Â
  {
       int u = minDistance(dist, visited);
Â
       // Mark the picked vertex as visited
       visited[u] = 1;
Â
       // Update dist value of the adjacent vertices of the picked vertex
       for (int v = 0; v < V; v++)
    {
           // Update dist[v] only if it’s not in visited, there is an edge from u to v, and
           // total weight of path from src to v through u is smaller than current value of dist[v]
           if (!visited[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v])
      {
               dist[v] = dist[u] + graph[u][v];
           }
       }
   }
Â
   // Print the constructed distance array
   printSolution(dist);
}
Â
int main()
{
   // Example graph represented as an adjacency matrix
   int graph[V][V] =
  {
       {0, 4, 0, 0, 0, 0, 0, 8, 0},
       {4, 0, 8, 0, 0, 0, 0, 11, 0},
       {0, 8, 0, 7, 0, 4, 0, 0, 2},
       {0, 0, 7, 0, 9, 14, 0, 0, 0},
       {0, 0, 0, 9, 0, 10, 0, 0, 0},
       {0, 0, 4, 14, 10, 0, 2, 0, 0},
       {0, 0, 0, 0, 0, 2, 0, 1, 6},
       {8, 11, 0, 0, 0, 0, 1, 0, 7},
       {0, 0, 2, 0, 0, 0, 6, 7, 0}
   };
Â
   dijkstra(graph, 0); // Find shortest paths from vertex 0
Â
   return 0;
}
// COMPUTER GEEK – compgeek.co.in
// Write a program for Dijkstra’s Algorithm
Â
#include <iostream>
#include <limits.h>
Â
#define V 9 // Number of vertices in the graph
Â
// Function to find the vertex with the minimum distance value
int minDistance(int dist[], bool visited[])
{
   int min = INT_MAX, min_index;
Â
   for (int v = 0; v < V; v++)
  {
       if (!visited[v] && dist[v] <= min)
    {
           min = dist[v];
           min_index = v;
       }
   }
Â
   return min_index;
}
Â
// Function to print the constructed distance array
void printSolution(int dist[])
{
   std::cout << “Vertex \t Distance from Source\n”;
   for (int i = 0; i < V; i++)
  {
       std::cout << i << ” \t ” << dist[i] << std::endl;
   }
}
Â
// Function that implements Dijkstra’s single source shortest path algorithm
void dijkstra(int graph[V][V], int src)
{
   int dist[V]; // The output array. dist[i] will hold the shortest distance from src to i
   bool visited[V]; // visited[i] will be true if vertex i is included in the shortest path tree
Â
   // Initialize all distances as INFINITE and visited[] as false
   for (int i = 0; i < V; i++)
  {
       dist[i] = INT_MAX;
       visited[i] = false;
   }
Â
   // Distance of source vertex from itself is always 0
   dist[src] = 0;
Â
   // Find shortest path for all vertices
   for (int count = 0; count < V – 1; count++)
  {
       int u = minDistance(dist, visited);
Â
       // Mark the picked vertex as visited
       visited[u] = true;
Â
       // Update dist value of the adjacent vertices of the picked vertex
       for (int v = 0; v < V; v++)
    {
           // Update dist[v] only if it’s not in visited, there is an edge from u to v, and
           // total weight of path from src to v through u is smaller than current value of dist[v]
           if (!visited[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v])
      {
               dist[v] = dist[u] + graph[u][v];
           }
       }
   }
Â
   // Print the constructed distance array
   printSolution(dist);
}
Â
int main()
{
   // Example graph represented as an adjacency matrix
   int graph[V][V] =
  {
       {0, 4, 0, 0, 0, 0, 0, 8, 0},
       {4, 0, 8, 0, 0, 0, 0, 11, 0},
       {0, 8, 0, 7, 0, 4, 0, 0, 2},
       {0, 0, 7, 0, 9, 14, 0, 0, 0},
       {0, 0, 0, 9, 0, 10, 0, 0, 0},
       {0, 0, 4, 14, 10, 0, 2, 0, 0},
       {0, 0, 0, 0, 0, 2, 0, 1, 6},
       {8, 11, 0, 0, 0, 0, 1, 0, 7},
       {0, 0, 2, 0, 0, 0, 6, 7, 0}
   };
Â
   dijkstra(graph, 0); // Find shortest paths from vertex 0
Â
   return 0;
}
// COMPUTER GEEK – compgeek.co.in
// Write a program for Dijkstra’s Algorithm
Â
import java.util.Arrays;
Â
class ShortestPath
{
   static final int V = 9; // Number of vertices in the graph
Â
   // Function to find the vertex with the minimum distance value
   int minDistance(int dist[], boolean visited[])
  {
       int min = Integer.MAX_VALUE, min_index = -1;
Â
       for (int v = 0; v < V; v++)
           if (!visited[v] && dist[v] <= min)
      {
               min = dist[v];
               min_index = v;
           }
Â
       return min_index;
   }
Â
   // Function to print the constructed distance array
   void printSolution(int dist[])
  {
       System.out.println(“Vertex \t Distance from Source”);
       for (int i = 0; i < V; i++)
           System.out.println(i + ” \t ” + dist[i]);
   }
Â
   // Function that implements Dijkstra’s single source shortest path algorithm
   void dijkstra(int graph[][], int src)
  {
       int dist[] = new int[V]; // The output array. dist[i] will hold the shortest distance from src to i
       boolean visited[] = new boolean[V]; // visited[i] will be true if vertex i is included in the shortest path tree
Â
       // Initialize all distances as INFINITE and visited[] as false
       Arrays.fill(dist, Integer.MAX_VALUE);
       Arrays.fill(visited, false);
Â
       // Distance of source vertex from itself is always 0
       dist[src] = 0;
Â
       // Find shortest path for all vertices
       for (int count = 0; count < V – 1; count++)
    {
           int u = minDistance(dist, visited);
Â
           // Mark the picked vertex as visited
           visited[u] = true;
Â
           // Update dist value of the adjacent vertices of the picked vertex
           for (int v = 0; v < V; v++)
               if (!visited[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE && dist[u] + graph[u][v] < dist[v])
                   dist[v] = dist[u] + graph[u][v];
       }
Â
       // Print the constructed distance array
       printSolution(dist);
   }
Â
   public static void main(String[] args)
  {
       // Example graph represented as an adjacency matrix
       int graph[][] =
    {
           {0, 4, 0, 0, 0, 0, 0, 8, 0},
           {4, 0, 8, 0, 0, 0, 0, 11, 0},
           {0, 8, 0, 7, 0, 4, 0, 0, 2},
           {0, 0, 7, 0, 9, 14, 0, 0, 0},
           {0, 0, 0, 9, 0, 10, 0, 0, 0},
           {0, 0, 4, 14, 10, 0, 2, 0, 0},
           {0, 0, 0, 0, 0, 2, 0, 1, 6},
           {8, 11, 0, 0, 0, 0, 1, 0, 7},
           {0, 0, 2, 0, 0, 0, 6, 7, 0}
       };
Â
       ShortestPath sp = new ShortestPath();
       sp.dijkstra(graph, 0); // Find shortest paths from vertex 0
   }
}
# COMPUTER GEEK – compgeek.co.in
# Write a program for Dijkstra’s Algorithm
Â
# Function to find the vertex with the minimum distance value
def minDistance(dist, visited):
   min_dist = float(‘inf’)
   min_index = -1
Â
   for v in range(len(dist)):
       if not visited[v] and dist[v] <= min_dist:
           min_dist = dist[v]
           min_index = v
Â
   return min_index
Â
# Function to print the constructed distance array
def printSolution(dist):
   print(“Vertex \t Distance from Source”)
   for i in range(len(dist)):
       print(f”{i} \t {dist[i]}”)
Â
# Function that implements Dijkstra’s single source shortest path algorithm
def dijkstra(graph, src):
   dist = [float(‘inf’)] * len(graph) # The output array. dist[i] will hold the shortest distance from src to i
   visited = [False] * len(graph) # visited[i] will be true if vertex i is included in the shortest path tree
Â
   # Distance of source vertex from itself is always 0
   dist[src] = 0
Â
   # Find shortest path for all vertices
   for _ in range(len(graph) – 1):
       u = minDistance(dist, visited)
Â
       # Mark the picked vertex as visited
       visited[u] = True
Â
       # Update dist value of the adjacent vertices of the picked vertex
       for v in range(len(graph)):
           if not visited[v] and graph[u][v] and dist[u] != float(‘inf’) and dist[u] + graph[u][v] < dist[v]:
               dist[v] = dist[u] + graph[u][v]
Â
   # Print the constructed distance array
   printSolution(dist)
Â
# Example graph represented as an adjacency matrix
graph = [
   [0, 4, 0, 0, 0, 0, 0, 8, 0],
   [4, 0, 8, 0, 0, 0, 0, 11, 0],
   [0, 8, 0, 7, 0, 4, 0, 0, 2],
   [0, 0, 7, 0, 9, 14, 0, 0, 0],
   [0, 0, 0, 9, 0, 10, 0, 0, 0],
   [0, 0, 4, 14, 10, 0, 2, 0, 0],
   [0, 0, 0, 0, 0, 2, 0, 1, 6],
   [8, 11, 0, 0, 0, 0, 1, 0, 7],
   [0, 0, 2, 0, 0, 0, 6, 7, 0]
]
Â
dijkstra(graph, 0) # Find shortest paths from vertex 0
Time Complexity of Dijkstra’s Algorithm
The time complexity of Dijkstra’s algorithm depends on the data structures used to implement it. Here’s a breakdown of the time complexity:
- Using an adjacency matrix
  – If the graph has V vertices and E edges, selecting the vertex with the minimum distance takes O(V) time.
  – Updating the distances of adjacent vertices takes O(V) time for each vertex.
  – Overall, the time complexity of the algorithm using an adjacency matrix is O(V2).
Â
Using a priority queue (min-heap)
  – With a binary heap or Fibonacci heap as the priority queue, selecting the vertex with the minimum distance takes O(log V) time.
  – Updating the distances of adjacent vertices takes O(log V) time for each vertex.
  – Considering that each edge is processed once, the total time complexity becomes O((V + E)log V).
.
Space Complexity of Dijkstra’s Algorithm
The space complexity of Dijkstra’s algorithm is O(V), where V is the number of vertices in the graph.
This space is primarily used for maintaining data structures like priority queues and distance arrays.
.
Advantages of Dijkstra’s Algorithm
– Finds the shortest path from a single source to all other vertices in a non-negative weighted graph.
– Efficient and widely applicable in various scenarios, such as network routing algorithms and GPS navigation systems.
.
Disadvantages of Dijkstra’s Algorithm
– Limited to graphs with non-negative edge weights.
– Inefficient for graphs with negative edge weights or cycles.
– Requires additional data structures like priority queues, which can increase space complexity.
.
Applications of Dijkstra’s Algorithm
– Network routing protocols in computer networks.
– GPS navigation systems for finding the shortest routes.
– Traffic management systems for optimizing travel paths.
– Shortest path algorithms in transportation and logistics.
Test Yourself
Q1- Explain Dijkstra’s algorithm and its significance in graph theory.
Dijkstra’s algorithm is a method for finding the shortest paths between nodes in a graph, especially in scenarios where all edge weights are non-negative. It explores nodes in a graph iteratively, gradually building up the shortest paths from a designated source node to all other nodes. This algorithm is significant because it has various practical applications in network routing, GPS navigation, and traffic management systems, among others.
Q2- Discuss the difference between Dijkstra’s algorithm and Prim’s algorithm.
Dijkstra’s algorithm is used to find the shortest paths between nodes in a graph, while Prim’s algorithm is used to find the minimum spanning tree of a graph.Â
Dijkstra’s algorithm considers the shortest path from a single source node to all other nodes, whereas Prim’s algorithm builds a tree that spans all the vertices with the minimum total edge weight.
Q3- Explain the limitations of Dijkstra’s algorithm.
Dijkstra’s algorithm is limited to graphs with non-negative edge weights.Â
It cannot handle graphs with negative edge weights or cycles, as this could lead to incorrect results.Â
Additionally, the algorithm requires additional data structures like priority queues, which can increase space complexity and memory usage.
Q4- Discuss a real-world application where Dijkstra’s algorithm is used extensively.
One real-world application of Dijkstra’s algorithm is in GPS navigation systems.Â
These systems use Dijkstra’s algorithm to find the shortest route between a starting location and a destination, considering factors such as distance, traffic conditions, and road closures.
Q5- Describe the historical context in which Dijkstra’s algorithm was developed.
Dijkstra developed the algorithm in 1956 while working at the Mathematical Centre in Amsterdam.Â
He created it to illustrate the capabilities of a new computer known as ARMAC and used it to generate a simplified transport map of 64 Dutch cities. The algorithm was later published in 1959.
Q6- What is the main objective of Dijkstra’s algorithm?
  1. Finding the maximum path in a graph
  2. Finding the minimum spanning tree
  3. Finding the shortest path between nodes
  4. Finding the longest path in a graph
Ans – (3)
Explanation – Dijkstra’s algorithm is used to find the shortest path between nodes in a graph.
Q7- Which data structure is commonly used in Dijkstra’s algorithm to efficiently select the node with the smallest known distance?
  1. Stack
  2. Queue
  3. Priority Queue (Correct)
  4. Linked List
Ans – (3)
Explanation – Priority queues are commonly used in Dijkstra’s algorithm to efficiently select the node with the smallest known distance.
Q8- What is the significance of the relaxation step in Dijkstra’s algorithm?
  1. Selecting the source node
 2. Updating the shortest distance to neighboring nodesÂ
  3. Marking nodes as visited
  4. Finding the minimum distance node
Ans – (2)
Explanation – The relaxation step involves updating the shortest distance to neighboring nodes if a shorter path is found through the current node.
Q9- Which algorithm is used to find the minimum spanning tree of a graph?
  1. Dijkstra’s algorithm
  2. Kruskal’s algorithm
  3. Bellman-Ford algorithm
  4. Floyd-Warshall algorithm
Ans – (2)
Explanation – Kruskal’s algorithm is used to find the minimum spanning tree of a graph.
Q10-Â In which year did Dijkstra publish his algorithm?
  1. 1959
  2. 1956
  3. 1961
  4. 1964
Ans – (1)
Explanation – Dijkstra published his algorithm in 1959.
Q11- What is the primary role of priority queues in Dijkstra’s algorithm?
  1. Sorting nodes in descending order
 2. Efficiently selecting the node with the smallest known distance
  3. Storing visited nodes
  4. Updating edge weights
Ans – (2)
Explanation – Priority queues are used to efficiently select the node with the smallest known distance during each iteration of Dijkstra’s algorithm.
