Dijkstra’s Algorithm — Weighted Shortest Paths
Move beyond unweighted graphs by mastering Dijkstra’s priority-queue based approach to shortest paths with non-negative weights.
Problem Statement
Learn how to compute the shortest distance from a single source to all other nodes in a weighted graph with non-negative edges using Dijkstra’s algorithm.
Why This Problem Matters
- Interviewers love asking for “shortest travel time” or “cheapest flight” variations where BFS no longer works.
- Dijkstra’s algorithm shows comfort with priority queues and greedy correctness proofs.
- Understanding relaxation steps prepares you for Bellman-Ford and A* upgrades.
Thought Process
Initialise distances and frontier
Start with distance[source] = 0 and infinity elsewhere. A min-heap delivers the next best candidate.
Relax edges greedily
When you pop a node, the current distance is final. Relaxing neighbors may shorten their known distances.
Guard against stale heap entries
Skip processing when the extracted distance is greater than the recorded best to keep runtime tight.
Step-by-Step Reasoning
- Seed a min-heap with [0, source] and a distance map defaulting to Infinity.
- Pop the closest node. If this distance is stale, continue.
- For each neighbor, compute candidate distance = current + weight.
- If candidate improves the recorded distance, update and push into the heap.
Dry Run
Graph edges: A→B(4), A→C(2), C→B(1), B→D(5), C→D(8)
Distances settle as A:0, C:2, B:3, D:8. Dijkstra explores in the order A, C, B, D.
Weighted grid where movement costs vary
Convert grid cells to nodes. Dijkstra ensures the first time you reach the finish you have the minimal accumulated cost.
Complexity Analysis
Time
O(E log V)
Space
O(V)
Why
Each edge relaxation costs a heap push (log V) and each vertex may be inserted multiple times, but at most once per improved distance.
Annotated Solution
import java.util.*;
public class ShortestPath {
private static class NodeState {
final int node;
final int dist;
NodeState(int node, int dist) {
this.node = node;
this.dist = dist;
}
}
public static Map<Integer, Integer> dijkstra(Map<Integer, List<int[]>> adjList, int source) {
Map<Integer, Integer> distances = new HashMap<>();
for (Integer node : adjList.keySet()) {
distances.put(node, Integer.MAX_VALUE);
}
distances.put(source, 0);
PriorityQueue<NodeState> minHeap =
new PriorityQueue<>(Comparator.comparingInt(state -> state.dist));
minHeap.offer(new NodeState(source, 0));
while (!minHeap.isEmpty()) {
NodeState current = minHeap.poll();
if (current.dist > distances.getOrDefault(current.node, Integer.MAX_VALUE)) {
continue;
}
for (int[] edge : adjList.getOrDefault(current.node, Collections.emptyList())) {
int neighbor = edge[0];
int weight = edge[1];
int candidate = current.dist + weight;
if (candidate < distances.getOrDefault(neighbor, Integer.MAX_VALUE)) {
distances.put(neighbor, candidate);
minHeap.offer(new NodeState(neighbor, candidate));
}
}
}
return distances;
}
}Most runtimes provide a priority queue; on LeetCode you can import one or write a simple binary heap. The skip-on-stale check keeps complexity optimal.
Common Pitfalls
- Forgetting to skip stale heap entries can balloon runtime.
- Using Dijkstra on graphs with negative edges yields incorrect answers; you need Bellman-Ford instead.
- Neglecting to initialise distances for every node leads to undefined results for disconnected components.
Follow-Up Questions
- Optimise using a Fibonacci heap (rare in interviews, but worth noting for theoretical completeness).
- Describe how to handle multiple sources by seeding the heap with each source at distance 0.
- Upgrade to A* by adding a heuristic to the priority and justify admissibility.