Dijkstra’s Algorithm
About
Dijkstra’s Algorithm is a greedy algorithm used to find the shortest path from a single source vertex to all other vertices in a graph with non-negative weights. It was developed by Edsger W. Dijkstra in 1956. It operates by selecting the minimum distance vertex, updating its neighbors, and repeating until all shortest paths are determined.
Type: Single Source Shortest Path (SSSP)
Graph Type: Weighted graphs (no negative weights)
Approach: Greedy Algorithm
Time Complexity:
O(V²) with an adjacency matrix (Basic version)
O((V + E) log V) with a priority queue (Optimized version using a Min-Heap)
Data Structure Used: Priority Queue (Min-Heap) for efficient selection of the shortest path
Limitation: Cannot handle negative weight edges
Working Principle
Initialize distances: Set the source vertex’s distance to 0 and all other vertices to infinity.
Select the minimum distance vertex: Pick the vertex with the smallest known distance (initially the source).
Update neighboring vertices: For each adjacent vertex, update its shortest known distance if a shorter path is found through the current vertex.
Repeat the process: Continue selecting the next minimum distance vertex and updating neighbors until all vertices are processed.
Terminate: The algorithm stops when all vertices have been visited, and the shortest distances to all nodes are finalized.
Example Execution
Graph Representation
Consider the following weighted graph:
(A)
/ \
4 1
/ \
(B) --- 2 -- (C)
\ /
5 3
\ /
(D)Graph Representation in Adjacency List Form:
A
B(4), C(1)
B
A(4), C(2), D(5)
C
A(1), B(2), D(3)
D
B(5), C(3)
We want to find the shortest path from A to all other nodes using Dijkstra’s Algorithm.
Step 1: Initialization
Set the source vertex (A) distance to 0.
Set all other vertices to ∞ (infinity).
Maintain a "visited" set to track processed nodes.
Use a priority queue (Min-Heap) to always select the node with the smallest known distance.
A
0
-
B
∞
-
C
∞
-
D
∞
-
Step 2: Process Node A (Starting Node)
Mark A as visited.
Update the distances of B and C (its adjacent nodes).
Since C has a smaller weight (1) compared to B (4), it will be prioritized.
A
0
-
B
4
A
C
1
A
D
∞
-
Step 3: Process Node C (Smallest Distance: 1)
Mark C as visited.
Update distances of its neighbors B and D:
B: Current distance = 4, alternative path through C = 1 + 2 = 3 (shorter, update)
D: Current distance = ∞, alternative path through C = 1 + 3 = 4 (update)
A
0
-
B
3
C
C
1
A
D
4
C
Step 4: Process Node B (Smallest Distance: 3)
Mark B as visited.
Update its neighbor D:
Current distance = 4, alternative path through B = 3 + 5 = 8 (not shorter, no update).
No changes in the table.
Step 5: Process Node D (Smallest Distance: 4)
Mark D as visited.
No updates needed since all nodes are processed.
Final shortest distances from A:
A
0
-
B
3
C
C
1
A
D
4
C
Step 6: Extract Shortest Paths
A → C (1)
A → C → B (3)
A → C → D (4)
Final Shortest Paths from A
B
A → C → B
3
C
A → C
1
D
A → C → D
4
Time and Space Complexity
Time Complexity
O(V²) for an adjacency matrix
O((V + E) log V) using a priority queue (Min-Heap)
Space Complexity
O(V + E) (to store the graph)
Implementation
1. Using PriorityQueue
import java.util.*;
public class DijkstraAlgorithm {
// Class to represent a graph edge
static class Edge {
int destination;
int weight;
Edge(int destination, int weight) {
this.destination = destination;
this.weight = weight;
}
}
// Dijkstra’s Algorithm implementation
public static int[] dijkstra(int vertices, List<List<Edge>> adjList, int source) {
int[] dist = new int[vertices]; // Stores shortest distance from source
Arrays.fill(dist, Integer.MAX_VALUE); // Initialize distances to infinity
dist[source] = 0;
// Min-heap based on distance
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
pq.add(new int[]{source, 0}); // {node, distance}
while (!pq.isEmpty()) {
int[] current = pq.poll();
int u = current[0];
int currentDist = current[1];
// Skip if we already have a better distance
if (currentDist > dist[u]) continue;
// Explore all neighbors
for (Edge edge : adjList.get(u)) {
int v = edge.destination;
int weight = edge.weight;
// Relaxation step
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.add(new int[]{v, dist[v]});
}
}
}
return dist;
}
// Sample usage
public static void main(String[] args) {
int vertices = 5;
List<List<Edge>> adjList = new ArrayList<>();
// Initialize adjacency list
for (int i = 0; i < vertices; i++) {
adjList.add(new ArrayList<>());
}
// Add directed edges: from -> (to, weight)
adjList.get(0).add(new Edge(1, 10));
adjList.get(0).add(new Edge(4, 5));
adjList.get(1).add(new Edge(2, 1));
adjList.get(1).add(new Edge(4, 2));
adjList.get(2).add(new Edge(3, 4));
adjList.get(3).add(new Edge(2, 6));
adjList.get(3).add(new Edge(0, 7));
adjList.get(4).add(new Edge(1, 3));
adjList.get(4).add(new Edge(2, 9));
adjList.get(4).add(new Edge(3, 2));
int source = 0;
int[] distances = dijkstra(vertices, adjList, source);
System.out.println("Shortest distances from source " + source + ":");
for (int i = 0; i < vertices; i++) {
System.out.println("To vertex " + i + " = " + distances[i]);
}
/*
Shortest distances from source 0:
To vertex 0 = 0
To vertex 1 = 8
To vertex 2 = 9
To vertex 3 = 7
To vertex 4 = 5
*/
}
}
The graph is represented using an adjacency list.
A priority queue is used to always process the node with the smallest known distance.
The algorithm performs relaxation for each edge.
Time complexity with priority queue and adjacency list: O((V + E) log V)
Limitations
Cannot handle negative weight edges
Not suitable for dynamic graphs where edges change frequently
Less efficient than A for heuristic-based pathfinding*
Optimizations
Use a priority queue (Min-Heap) instead of a simple array to improve efficiency
Fibonacci Heap reduces time complexity to O(E + V log V)
Bi-Directional Dijkstra reduces search space by simultaneously searching from source and destination
Applications of Dijkstra’s Algorithm
Navigation Systems → GPS routing (Google Maps, Waze)
Network Routing → Finding shortest paths in computer networks (OSPF protocol)
Robotics & AI → Path planning in autonomous robots
Telecommunications → Optimizing signal transmission paths
Game Development → Pathfinding for AI characters
Last updated