Graph - Dijkstra's Shortest Path Algorithm
Dijkstra's algorithm finds the shortest path from a single source node to all other nodes in a weighted graph with non-negative edge weights. It uses a Min-Heap (priority queue) to always process the currently known cheapest node first.
How Dijkstra's algorithm works
The core idea is to maintain a distance array where dist[v]v∞0
A Min-Heap (Priority Queue) is used to always pick the unvisited node with the smallest current distance.
Algorithm steps:
- Initialise
dist[source] = 0dist[v] = ∞ - Add the source node to the priority queue with distance 0.
- While the priority queue is not empty:
- Extract the node
u - For each neighbour
vunewDist = dist[u] + weight(u, v) - If
newDist < dist[v]dist[v] = newDistv - When the priority queue is empty,
dist[]
Implementation
Below implementation uses an adjacency list to represent the graph and a PriorityQueue
import java.util.*;
public class Dijkstra {
// Edge: destination node and weight
static class Edge {
int dest, weight;
Edge(int dest, int weight) {
this.dest = dest;
this.weight = weight;
}
}
/**
* Finds shortest distances from source to all nodes.
* @param graph adjacency list: graph[u] = list of Edge(v, w)
* @param V number of vertices
* @param source starting node
* @return dist[] array where dist[i] = shortest distance from source to i
*/
public int[] dijkstra(List<List<Edge>> graph, int V, int source) {
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[source] = 0;
// Min-heap: (distance, node)
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
pq.offer(new int[]{0, source});
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int d = curr[0], u = curr[1];
// Skip if we already found a better path
if (d > dist[u]) continue;
for (Edge edge : graph.get(u)) {
int newDist = dist[u] + edge.weight;
if (newDist < dist[edge.dest]) {
dist[edge.dest] = newDist;
pq.offer(new int[]{newDist, edge.dest});
}
}
}
return dist;
}
}Example usage:
int V = 5; // 5 nodes: 0, 1, 2, 3, 4
List<List<Dijkstra.Edge>> graph = new ArrayList<>();
for (int i = 0; i < V; i++) graph.add(new ArrayList<>());
// Add edges: (from, to, weight)
graph.get(0).add(new Dijkstra.Edge(1, 4));
graph.get(0).add(new Dijkstra.Edge(2, 1));
graph.get(2).add(new Dijkstra.Edge(1, 2));
graph.get(1).add(new Dijkstra.Edge(3, 1));
graph.get(2).add(new Dijkstra.Edge(3, 5));
graph.get(3).add(new Dijkstra.Edge(4, 3));
Dijkstra d = new Dijkstra();
int[] distances = d.dijkstra(graph, V, 0);
System.out.println(Arrays.toString(distances));
// Output: [0, 3, 1, 4, 7]
// Shortest distances from node 0 to all other nodesComplexity Analysis
- Time complexity: O((V + E) log V). Each vertex is extracted from the priority queue once (O(V log V)) and each edge is relaxed once (O(E log V)).
- Space complexity: O(V + E). For the distance array, priority queue, and adjacency list.
Limitations
- No negative edge weights: Dijkstra assumes all weights are non-negative. A negative weight can cause the algorithm to produce incorrect results because a previously finalised node might actually be reachable via a cheaper path through a negative edge.
- Single-source only: Dijkstra computes shortest paths from one source node. For all-pairs shortest paths, use Floyd-Warshall or run Dijkstra from every node.