← All patternsDijkstra's Shortest Path · template
Pattern · Graphs
Dijkstra's Shortest Path
Always expand the closest unfinished node from a min-heap; with non-negative weights, its distance is final.
Time O((V + E) log V) · Space O(V + E)
Taught in Module 26: Shortest Paths
Think of it like this
Water flooding out from a source through pipes of different lengths: it reaches the nearest junctions first.
Clues that point here
- → Shortest path with weighted edges
- → Weights are non-negative
- → Minimum cost or time to reach nodes
- → Network delay
Not this pattern when
- ✕ Negative edge weights (Bellman-Ford)
- ✕ All weights equal (plain BFS is simpler)
The template
A skeleton to adapt. The parts in comments are what changes from problem to problem.
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]); // {node, dist}
pq.offer(new int[]{src, 0});
while (!pq.isEmpty()) {
int[] cur = pq.poll();
if (cur[1] > dist[cur[0]]) continue; // stale entry
for (int[] e : graph.get(cur[0])) { // e = {next, weight}
int nd = cur[1] + e[1];
if (nd < dist[e[0]]) { dist[e[0]] = nd; pq.offer(new int[]{e[0], nd}); }
}
}
return dist;Common versions
- Network delay time
- Path with minimum effort
- Cheapest flights (with a stop limit: Bellman-Ford style)
- Swim in rising water
Practice problems with this pattern
26.1Network Delay TimeMediummain pattern26.2Path With Minimum EffortMediummain pattern26.3Cheapest Flights Within K StopsMediummain pattern26.4Path with Maximum ProbabilityMediummain pattern26.5Find the City With the Smallest Number of NeighborsMediummain pattern26.6Swim in Rising WaterHardmain pattern26.7Number of Ways to Arrive at DestinationMediummain pattern21.7Minimum Obstacle Removal to Reach CornerHardalso uses it