Min-heap greedy — always process the closest unvisited node first. Non-negative weights only.
Weighted GraphMin-HeapGreedyNon-Negative Weights
Time: O((V+E) log V)Space: O(V + E)
When to Use
Shortest path in weighted graph with non-negative weights
Single-source shortest path to all other nodes
Network routing, GPS navigation problems
Word ladder / transformation with costs
⚠️ NOT for negative weight edges — use Bellman-Ford
Complexity
With binary heap
O((V+E) log V)
With Fibonacci heap
O(E + V log V)
Simple array
O(V²) — dense graphs
Space
O(V + E)
Live Animation · Dijkstra's Shortest Path · LC #743
Problem
Given a network of n = 5 nodes and directed weighted edges, find the time it takes for a signal from node 0 to reach all nodes (maximum of all shortest-path distances). Use Dijkstra's min-heap — always expand the cheapest unvisited node, relax its outgoing edges, discard stale PQ entries.
Input: edges = [[0,1,4],[0,2,1],[2,1,2],[1,3,1],[2,3,5],[3,4,3]], source = 0 · Answer: dist = [0,3,1,4,7] → max = 7
dist[ ] from node 0
⛏ Priority Queue (dist, node)
Step 0 / 8
InitPop MinRelax EdgeSkip StaleDone
Initialize: dist[0]=0, all others=∞. Push (0, node0) into min-heap.
dist[src]=0; pq.offer(new int[]{src,0});
Java Pattern Templateskeleton only
// Dijkstra's — single-source shortest path (pattern skeleton)int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
// min-heap: [node, distance]
PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[1]-b[1]);
pq.offer(new int[]{src, 0});
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int u = cur[0], d = cur[1];
if (d > dist[u]) continue; // stale entry — skipfor (int[] e : adj.get(u)) { // e = [neighbor, weight]int v = e[0], w = e[1];
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.offer(new int[]{v, dist[v]});
}
}
}
// dist[i] = shortest distance from src to node i