Dijkstra
Grow a settled set, always expanding the unsettled node with the smallest tentative distance, using a priority queue.
GraphsO(E log V)New6 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
shortest path with weights
cheapest route
network delay time
The template
Get this into muscle memory, then adapt the condition per problem.
const pq = new MinHeap([[0, src]]);
while (pq.size) {
const [d, u] = pq.pop();
if (d > dist[u]) continue;
for (const [v, w] of adj[u]) if (d + w < dist[v]) {
dist[v] = d + w;
pq.push([dist[v], v]);
}
} Watch Dijkstra Shortest PathIf you are stuck
The generic hint ladder for this pattern, in order.
- 1Edges have different costs, so BFS layers no longer mean distance.
- 2Always finalise the closest unfinished node.
- 3Negative weights break the greedy argument, use Bellman-Ford there.
Drill it
Every problem in the bank that uses this pattern.
0 / 6 solved