Builds on Shortest-Path BFS and Top-K Heap, which you haven’t finished yet.
Dijkstra's Algorithm
A network has n nodes, labeled 1 through n, connected by directed wires times[i] = (ui, vi, wi): a signal takes wi time units to travel from ui to vi.
A signal is broadcast from a single node k. Return the time it takes for the last node to receive it -- the smallest t such that every one of the n nodes has heard the signal by time t. Return -1 if some node never receives it.
2 the signal reaches nodes 1 and 3 at time 1, then node 4 at time 2.Dijkstra
weighted directed graph ➔ min-heap (dist, node) ➔ greedy relaxation| 1 | import heapq |
| 2 | from typing import List, Dict |
| 3 | |
| 4 | def dijkstra(n: int, edges: List[List[int]], source: int) -> Dict[int, float]: |
| 5 | """Dijkstra (the core of Network Delay Time): cheapest distance from source to nodes |
| 6 | 1..n. |
| 7 | Time: O((V + E) log V) | Space: O(V + E) |
| 8 | """ |
| 9 | adj = [[] for _ in range(n + 1)] |
| 10 | for u, v, w in edges: |
| 11 | adj[u].append((v, w)) |
| 12 | |
| 13 | dist = {i: float('inf') for i in range(1, n + 1)} |
| 14 | dist[source] = 0 |
| 15 | pq = [(0, source)] # (cost, node) |
| 16 | |
| 17 | while pq: |
| 18 | d, u = heapq.heappop(pq) |
| 19 | if d > dist[u]: |
| 20 | continue # Stale entry: u was already settled with a smaller d |
| 21 | |
| 22 | for v, weight in adj[u]: |
| 23 | if dist[u] + weight < dist[v]: # Relax the edge |
| 24 | dist[v] = dist[u] + weight |
| 25 | heapq.heappush(pq, (dist[v], v)) |
| 26 | |
| 27 | return dist |
(d, u) is popped with d == dist[u], dist[u] is final: no path to u is shorter.Keep a min-heap pq of (distance, node) pairs. Popping the smallest d settles u, because with non-negative weights any other path to u leaves the settled area through a node that is at least as far away, so it can't be shorter. For each edge, if going through u is shorter, update dist[v] and push the new pair. The trap is the stale entry: u can sit in pq several times, so skip it when d > dist[u]; without that line the answer stays right, but old entries relax every edge again and the run can slow down badly.
See it run
Dijkstra's algorithm from node 1, step by step
dist {1: 0, 2: inf, 3: inf, 4: inf}
Each arrow is a one-way road with its cost beside it. A node shows its number, a colon, then its dist. The row under the graph is pq: the left box is popped first.
popthe node whose pair was just popped, and whose edges are now readfinalpopped with its final distin pqhas a dist and a pair waiting in pqrelaxan edge that gave a shorter diststalea pair whose d is larger than dist[u], which is skipped
dist[1] = 0 and every other node is inf. pq holds the pair (0, 1).
Gotcha 1 of 4
- The trap
Gotcha 1: Relaxing edges from a stale heap entry
Mistaked, u = heapq.heappop(pq)Fixd, u = heapq.heappop(pq) if d > dist[u]: continueWhat happens:
uis pushed again every timedist[u]improves. Sopqcan hold old pairs foruwith a largerd. Without the check, an old pair relaxes every edge ofuagain. The answer stays right, because an olddnever improvesdist[v]. But the run can do much more work. That is why this mistake has no example.
- Every move costs the same, as in Shortest Path in Binary Matrix (LC 1091), so the path with the fewest steps is already the cheapest. See Shortest-Path BFS
- The path may use at most
kstops, as in Cheapest Flights Within K Stops (LC 787), so the cheapest path overall can be one you are not allowed to take. See Bellman-Ford
Deep Dive
Why a popped distance is final
pq is a min-heap of (d, node) pairs. Each pop returns the pair with the smallest d that is still waiting. When d == dist[u], the card says dist[u] is final. Here is the reason.
Suppose some other path to u were shorter than d. That path starts at the source, which is settled. It must leave the settled nodes at some edge x -> y. Node y is not settled yet, so a pair for y waits in pq, and that pair has a d no larger than the length of the path up to y.
Every edge weight is zero or more. So the rest of the path from y to u adds nothing negative, and the pair for y is no larger than the whole path. The path is shorter than d, so the pair for y is smaller than d. But pq just returned d as the smallest. This is a contradiction, so no shorter path exists.
Example: in Network Delay Time (LC 743), times = [[2, 1, 1], [2, 3, 1], [3, 4, 1]], n = 4 and k = 2 give dist = {1: 1, 2: 0, 3: 1, 4: 2}. The largest value is 2, which is the answer.
One trace: a stale entry is skipped
The board runs dijkstra on a small graph with source = 1. Edge 1 -> 2 costs 4, and edge 1 -> 3 costs 1.
Pop (0, 1). Node 2 gets dist[2] = 4, and node 3 gets dist[3] = 1. Pop (1, 3). Now the path 1 -> 3 -> 2 costs 3, which is less than 4. So dist[2] becomes 3, and a second pair (3, 2) joins pq. The old pair (4, 2) is still inside pq.
Later, the pop returns (4, 2). But dist[2] is 3, and 4 > 3, so the line if d > dist[u]: continue skips it. This is the step marked as stale on the board. The pair (6, 4) is skipped in the same way.
The final dist is {1: 0, 2: 3, 3: 1, 4: 4}. The answer is 4. Without the check, the stale pair (4, 2) would read the edge 2 -> 4 again. For this graph the run makes 6 edge reads instead of 5, and the answer is the same. The check only saves work.
The trap: negative weights
The proof above used one fact: no edge weight is below zero. With a negative edge, the proof fails. A later edge can make a settled node cheaper.
Example: edges = [[1, 2, 2], [1, 3, 3], [3, 2, -2]] with source = 1. The pair (2, 2) is popped first, so node 2 is settled with dist[2] = 2. Then node 3 is settled at 3, and the edge 3 -> 2 gives 3 - 2 = 1. The true cheapest cost to node 2 is 1.
A version that never looks at a settled node again returns 2, which is wrong. The blueprint pushes the node again, so it can fix the value. But then a node can be popped many times, and a cycle with a negative total never ends. For negative weights, use the next card, Bellman-Ford.
A second trap is a zero weight. Network Delay Time (LC 743) allows weight 0. Use < in the relax test, as the blueprint does. With <=, two nodes joined by zero-weight edges push each other forever.
The cost, and the neighbouring cards
Each edge can push at most one pair, so pq never holds more than E + 1 pairs. Each push and pop costs O(log E), which is O(log V) because E is at most V squared. The total is O((V + E) log V) time and O(V + E) space.
Shortest-Path BFS (the fewest-steps card) is the same idea with every weight equal to 1. Then a plain queue already pops in order of distance, and no heap is needed. Use Dijkstra when the weights differ, as in Network Delay Time (LC 743), or when the cost is the largest step on the path, as in Path With Minimum Effort (LC 1631).
Bellman-Ford (the relax-k-times card) is the next step. It handles a cap on the number of edges, and negative weights, with rounds of relaxation and no heap. Floyd-Warshall (the all-pairs card) answers every pair at once, at O(V^3).
Example: on the board graph, the cheapest path from node 1 to node 4 costs 4. If a cap of one edge were added, no path could reach node 4. Dijkstra cannot take that cap into account, because it settles a node by cost alone.
60-Second Pitch
"The weights are not negative and I need the cheapest path from one source, so I use Dijkstra with a min-heap. I keep dist for each node and push (distance, node) pairs. A pop gives the smallest waiting distance. Because no weight is negative, any other path to that node would leave the settled nodes through a pair that is at least as large, so the popped distance is final. A node can sit in the heap more than once, so I skip a pair when d is larger than dist[u]. Then I relax each outgoing edge with a strict < and push the improved pair. The time is O((V + E) log V) and the space is O(V + E). If an edge can be negative, or the path has a cap on edges, I would switch to Bellman-Ford."
Common Questions
- Why does Dijkstra need non-negative weights?
The proof says every other path to a popped node must pass through a waiting pair that is at least as large. A negative edge can lower the cost after that point, so a settled node can still get cheaper. Then the popped distance is not final.
- What is the time complexity, and where does the log come from?
O((V + E) log V). Each edge pushes at most one pair, so there are at most E pushes and pops. Each costs O(log E) in the heap, which is O(log V). The space is
O(V + E)for the graph and the heap.- Why check
d > dist[u]after the pop? Why not remove the old pair? Python's
heapqcannot remove a pair from the middle. So the old pair stays, and we skip it when it comes out. The skip costsO(1)and keeps the work near O((V + E) log V). Without it, the answer is the same but old pairs read the edges again.- How do you handle a graph where all weights are 1?
Use plain BFS. A queue pops nodes in order of distance when every move costs the same, so no heap is needed. The time drops to
O(V + E). This is the Shortest-Path BFS card.- What do you use for negative weights?
Bellman-Ford. It relaxes every edge in rounds, and it does not need to settle a node early. With a cap on the number of edges, as in Cheapest Flights Within K Stops (LC 787), the number of rounds is the cap plus one.
SWE Reasoning
Spot it
- The graph has edge weights, and the question asks for the cheapest path, the shortest time or the smallest total cost.
- All weights are zero or more. Say this out loud, because the whole method depends on it.
- The cost can also be the largest step on the path, such as effort or water level. The same heap works with
maxin place of+. - The answer is a distance from one source to the other nodes, not the distance between every pair.
- A plain BFS would be wrong, because a path with fewer edges can cost more.
The invariant, step by step
dist[source] = 0, every otherdistis infinity, andpqholds(0, source).- Each pop returns the waiting pair with the smallest
d. - If
d > dist[u], a better pair foruwas already handled. Skip this stale pair. - Otherwise
d == dist[u]. Every other path toumust leave the settled nodes through a pair that is at leastd, sodist[u]is final. - For each edge
u -> v, ifdist[u] + weight < dist[v], set the newdist[v]and push the new pair. - When
pqis empty, every reachable node is settled. The unreachable nodes still have infinity.
Traps
- No stale check.
pqcan hold several pairs for one node. Withoutif d > dist[u]: continue, the old pairs read every edge again. The answer is right, but the run is slower. - A negative weight. A settled node can become cheaper later. Dijkstra does not promise a correct answer, and a negative cycle never ends. Use Bellman-Ford.
<=in the relax test. Zero-weight edges push each other forever. Use<.- Pushing without an improvement. Push only inside the
if, whendist[v]became smaller. - Unreached nodes. A node that is never reached keeps infinity. For Network Delay Time (LC 743), return -1 when the largest distance is infinity.
Practice
Builds on Shortest-Path BFS and Top-K Heap, which you haven’t finished yet.
Dijkstra's Algorithm
A network has n nodes, labeled 1 through n, connected by directed wires times[i] = (ui, vi, wi): a signal takes wi time units to travel from ui to vi.
A signal is broadcast from a single node k. Return the time it takes for the last node to receive it -- the smallest t such that every one of the n nodes has heard the signal by time t. Return -1 if some node never receives it.
2 the signal reaches nodes 1 and 3 at time 1, then node 4 at time 2.Dijkstra
weighted directed graph ➔ min-heap (dist, node) ➔ greedy relaxation| 1 | import heapq |
| 2 | from typing import List, Dict |
| 3 | |
| 4 | def dijkstra(n: int, edges: List[List[int]], source: int) -> Dict[int, float]: |
| 5 | """Dijkstra (the core of Network Delay Time): cheapest distance from source to nodes |
| 6 | 1..n. |
| 7 | Time: O((V + E) log V) | Space: O(V + E) |
| 8 | """ |
| 9 | adj = [[] for _ in range(n + 1)] |
| 10 | for u, v, w in edges: |
| 11 | adj[u].append((v, w)) |
| 12 | |
| 13 | dist = {i: float('inf') for i in range(1, n + 1)} |
| 14 | dist[source] = 0 |
| 15 | pq = [(0, source)] # (cost, node) |
| 16 | |
| 17 | while pq: |
| 18 | d, u = heapq.heappop(pq) |
| 19 | if d > dist[u]: |
| 20 | continue # Stale entry: u was already settled with a smaller d |
| 21 | |
| 22 | for v, weight in adj[u]: |
| 23 | if dist[u] + weight < dist[v]: # Relax the edge |
| 24 | dist[v] = dist[u] + weight |
| 25 | heapq.heappush(pq, (dist[v], v)) |
| 26 | |
| 27 | return dist |
(d, u) is popped with d == dist[u], dist[u] is final: no path to u is shorter.Keep a min-heap pq of (distance, node) pairs. Popping the smallest d settles u, because with non-negative weights any other path to u leaves the settled area through a node that is at least as far away, so it can't be shorter. For each edge, if going through u is shorter, update dist[v] and push the new pair. The trap is the stale entry: u can sit in pq several times, so skip it when d > dist[u]; without that line the answer stays right, but old entries relax every edge again and the run can slow down badly.
See it run
Dijkstra's algorithm from node 1, step by step
dist {1: 0, 2: inf, 3: inf, 4: inf}
Each arrow is a one-way road with its cost beside it. A node shows its number, a colon, then its dist. The row under the graph is pq: the left box is popped first.
popthe node whose pair was just popped, and whose edges are now readfinalpopped with its final distin pqhas a dist and a pair waiting in pqrelaxan edge that gave a shorter diststalea pair whose d is larger than dist[u], which is skipped
dist[1] = 0 and every other node is inf. pq holds the pair (0, 1).
Gotcha 1 of 4
- The trap
Gotcha 1: Relaxing edges from a stale heap entry
Mistaked, u = heapq.heappop(pq)Fixd, u = heapq.heappop(pq) if d > dist[u]: continueWhat happens:
uis pushed again every timedist[u]improves. Sopqcan hold old pairs foruwith a largerd. Without the check, an old pair relaxes every edge ofuagain. The answer stays right, because an olddnever improvesdist[v]. But the run can do much more work. That is why this mistake has no example.
- Every move costs the same, as in Shortest Path in Binary Matrix (LC 1091), so the path with the fewest steps is already the cheapest. See Shortest-Path BFS
- The path may use at most
kstops, as in Cheapest Flights Within K Stops (LC 787), so the cheapest path overall can be one you are not allowed to take. See Bellman-Ford
Deep Dive
Why a popped distance is final
pq is a min-heap of (d, node) pairs. Each pop returns the pair with the smallest d that is still waiting. When d == dist[u], the card says dist[u] is final. Here is the reason.
Suppose some other path to u were shorter than d. That path starts at the source, which is settled. It must leave the settled nodes at some edge x -> y. Node y is not settled yet, so a pair for y waits in pq, and that pair has a d no larger than the length of the path up to y.
Every edge weight is zero or more. So the rest of the path from y to u adds nothing negative, and the pair for y is no larger than the whole path. The path is shorter than d, so the pair for y is smaller than d. But pq just returned d as the smallest. This is a contradiction, so no shorter path exists.
Example: in Network Delay Time (LC 743), times = [[2, 1, 1], [2, 3, 1], [3, 4, 1]], n = 4 and k = 2 give dist = {1: 1, 2: 0, 3: 1, 4: 2}. The largest value is 2, which is the answer.
One trace: a stale entry is skipped
The board runs dijkstra on a small graph with source = 1. Edge 1 -> 2 costs 4, and edge 1 -> 3 costs 1.
Pop (0, 1). Node 2 gets dist[2] = 4, and node 3 gets dist[3] = 1. Pop (1, 3). Now the path 1 -> 3 -> 2 costs 3, which is less than 4. So dist[2] becomes 3, and a second pair (3, 2) joins pq. The old pair (4, 2) is still inside pq.
Later, the pop returns (4, 2). But dist[2] is 3, and 4 > 3, so the line if d > dist[u]: continue skips it. This is the step marked as stale on the board. The pair (6, 4) is skipped in the same way.
The final dist is {1: 0, 2: 3, 3: 1, 4: 4}. The answer is 4. Without the check, the stale pair (4, 2) would read the edge 2 -> 4 again. For this graph the run makes 6 edge reads instead of 5, and the answer is the same. The check only saves work.
The trap: negative weights
The proof above used one fact: no edge weight is below zero. With a negative edge, the proof fails. A later edge can make a settled node cheaper.
Example: edges = [[1, 2, 2], [1, 3, 3], [3, 2, -2]] with source = 1. The pair (2, 2) is popped first, so node 2 is settled with dist[2] = 2. Then node 3 is settled at 3, and the edge 3 -> 2 gives 3 - 2 = 1. The true cheapest cost to node 2 is 1.
A version that never looks at a settled node again returns 2, which is wrong. The blueprint pushes the node again, so it can fix the value. But then a node can be popped many times, and a cycle with a negative total never ends. For negative weights, use the next card, Bellman-Ford.
A second trap is a zero weight. Network Delay Time (LC 743) allows weight 0. Use < in the relax test, as the blueprint does. With <=, two nodes joined by zero-weight edges push each other forever.
The cost, and the neighbouring cards
Each edge can push at most one pair, so pq never holds more than E + 1 pairs. Each push and pop costs O(log E), which is O(log V) because E is at most V squared. The total is O((V + E) log V) time and O(V + E) space.
Shortest-Path BFS (the fewest-steps card) is the same idea with every weight equal to 1. Then a plain queue already pops in order of distance, and no heap is needed. Use Dijkstra when the weights differ, as in Network Delay Time (LC 743), or when the cost is the largest step on the path, as in Path With Minimum Effort (LC 1631).
Bellman-Ford (the relax-k-times card) is the next step. It handles a cap on the number of edges, and negative weights, with rounds of relaxation and no heap. Floyd-Warshall (the all-pairs card) answers every pair at once, at O(V^3).
Example: on the board graph, the cheapest path from node 1 to node 4 costs 4. If a cap of one edge were added, no path could reach node 4. Dijkstra cannot take that cap into account, because it settles a node by cost alone.
60-Second Pitch
"The weights are not negative and I need the cheapest path from one source, so I use Dijkstra with a min-heap. I keep dist for each node and push (distance, node) pairs. A pop gives the smallest waiting distance. Because no weight is negative, any other path to that node would leave the settled nodes through a pair that is at least as large, so the popped distance is final. A node can sit in the heap more than once, so I skip a pair when d is larger than dist[u]. Then I relax each outgoing edge with a strict < and push the improved pair. The time is O((V + E) log V) and the space is O(V + E). If an edge can be negative, or the path has a cap on edges, I would switch to Bellman-Ford."
Common Questions
- Why does Dijkstra need non-negative weights?
The proof says every other path to a popped node must pass through a waiting pair that is at least as large. A negative edge can lower the cost after that point, so a settled node can still get cheaper. Then the popped distance is not final.
- What is the time complexity, and where does the log come from?
O((V + E) log V). Each edge pushes at most one pair, so there are at most E pushes and pops. Each costs O(log E) in the heap, which is O(log V). The space is
O(V + E)for the graph and the heap.- Why check
d > dist[u]after the pop? Why not remove the old pair? Python's
heapqcannot remove a pair from the middle. So the old pair stays, and we skip it when it comes out. The skip costsO(1)and keeps the work near O((V + E) log V). Without it, the answer is the same but old pairs read the edges again.- How do you handle a graph where all weights are 1?
Use plain BFS. A queue pops nodes in order of distance when every move costs the same, so no heap is needed. The time drops to
O(V + E). This is the Shortest-Path BFS card.- What do you use for negative weights?
Bellman-Ford. It relaxes every edge in rounds, and it does not need to settle a node early. With a cap on the number of edges, as in Cheapest Flights Within K Stops (LC 787), the number of rounds is the cap plus one.
SWE Reasoning
Spot it
- The graph has edge weights, and the question asks for the cheapest path, the shortest time or the smallest total cost.
- All weights are zero or more. Say this out loud, because the whole method depends on it.
- The cost can also be the largest step on the path, such as effort or water level. The same heap works with
maxin place of+. - The answer is a distance from one source to the other nodes, not the distance between every pair.
- A plain BFS would be wrong, because a path with fewer edges can cost more.
The invariant, step by step
dist[source] = 0, every otherdistis infinity, andpqholds(0, source).- Each pop returns the waiting pair with the smallest
d. - If
d > dist[u], a better pair foruwas already handled. Skip this stale pair. - Otherwise
d == dist[u]. Every other path toumust leave the settled nodes through a pair that is at leastd, sodist[u]is final. - For each edge
u -> v, ifdist[u] + weight < dist[v], set the newdist[v]and push the new pair. - When
pqis empty, every reachable node is settled. The unreachable nodes still have infinity.
Traps
- No stale check.
pqcan hold several pairs for one node. Withoutif d > dist[u]: continue, the old pairs read every edge again. The answer is right, but the run is slower. - A negative weight. A settled node can become cheaper later. Dijkstra does not promise a correct answer, and a negative cycle never ends. Use Bellman-Ford.
<=in the relax test. Zero-weight edges push each other forever. Use<.- Pushing without an improvement. Push only inside the
if, whendist[v]became smaller. - Unreached nodes. A node that is never reached keeps infinity. For Network Delay Time (LC 743), return -1 when the largest distance is infinity.