Problem
Given a weighted graph represented using an adjacency list and a source node, find the shortest distance from the source node to every other node.Each edge contains a destination node and a weight. Dijkstra's Algorithm works correctly only when all edge weights are non-negative.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
graph = {
0: [[1,4],[2,1]],
1: [[3,1]],
2: [[1,2],[3,5]],
3: []
}
source = 0
Output
[0,3,1,4]0 are:
0 → 0 = 0
0 → 1 = 3
0 → 2 = 1
0 → 3 = 4
Solution
Dijkstra's Algorithm uses a Min Heap to always process the node with the smallest known distance from the source.We maintain a distance array where
distance[i] represents the shortest distance currently known from the source node to node i. Initially, the source has distance 0, while all other nodes are set to infinity.
The source node is added to the Min Heap. We repeatedly remove the node with the smallest distance and examine its neighboring nodes.
For each neighbor, we check whether reaching it through the current node produces a shorter path. If it does, we update its distance and add the new distance to the Min Heap.
This process is called relaxation. Because all edge weights are non-negative, once a node is processed with its shortest distance, no later path can produce a smaller distance.
public int[] dijkstra(int[][][] graph, int source) {
int n = graph.length;
int[] distance = new int[n];
Arrays.fill(distance, Integer.MAX_VALUE);
// Store {distance, node}.
PriorityQueue<int[]> minHeap =
new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
distance[source] = 0;
minHeap.offer(new int[]{0, source});
while (!minHeap.isEmpty()) {
int[] current = minHeap.poll();
int currentDistance = current[0];
int node = current[1];
// Skip outdated entries.
if (currentDistance > distance[node]) {
continue;
}
// Relax all neighboring edges.
for (int[] edge : graph[node]) {
int neighbor = edge[0];
int weight = edge[1];
int newDistance = currentDistance + weight;
if (newDistance < distance[neighbor]) {
distance[neighbor] = newDistance;
minHeap.offer(new int[]{newDistance, neighbor});
}
}
}
return distance;
}
Complexity
Each edge can cause a distance update and a Min Heap operation. Since each heap operation takesO(log V) time, the overall time complexity is O((V + E) log V).
The distance array and Min Heap require
O(V) extra space, while the graph representation itself requires O(V + E) space.