What you will learn
- Dijkstra’s algorithm with Python’s
heapqand lazy deletion. - When Dijkstra is wrong and Bellman-Ford is right.
- Limiting the number of edges in a path.
Signals
- Weighted edges and “minimum cost / time / distance”.
- “Time for a signal to reach all nodes”, “cheapest route”.
- A limit on stops or edges → Bellman-Ford rounds (or BFS by levels with costs).
Code
"""Shortest paths: Dijkstra with a min-heap, and Bellman-Ford limited to k edges."""
import heapq
def dijkstra(n, edges, src):
graph = [[] for _ in range(n)]
for u, v, w in edges:
graph[u].append((v, w))
dist = [float("inf")] * n
dist[src] = 0
heap = [(0, src)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue # stale entry: we already found a shorter way to u
for v, w in graph[u]:
if d + w < dist[v]:
dist[v] = d + w
heapq.heappush(heap, (dist[v], v))
return dist
def network_delay(times, n, k):
"""LeetCode 743: nodes are 1..n; time for a signal from k to reach every node."""
dist = dijkstra(n + 1, times, k)[1:]
worst = max(dist)
return -1 if worst == float("inf") else worst
def cheapest_with_k_stops(n, flights, src, dst, k):
"""Bellman-Ford for at most k+1 edges; copy per round so one round adds one edge."""
cost = [float("inf")] * n
cost[src] = 0
for _ in range(k + 1):
nxt = cost[:]
for u, v, w in flights:
if cost[u] + w < nxt[v]:
nxt[v] = cost[u] + w
cost = nxt
return -1 if cost[dst] == float("inf") else cost[dst]
if __name__ == "__main__":
edges = [(0, 1, 4), (0, 2, 1), (2, 1, 2), (1, 3, 1), (2, 3, 5)]
print(dijkstra(4, edges, 0))
print(network_delay([[2, 1, 1], [2, 3, 1], [3, 4, 1]], 4, 2))
flights = [[0, 1, 100], [1, 2, 100], [2, 3, 100], [0, 3, 500], [0, 2, 300]]
print(cheapest_with_k_stops(4, flights, 0, 3, 1), cheapest_with_k_stops(4, flights, 0, 3, 2))
Output:
[0, 3, 1, 4]
2
400 300
- Dijkstra: always expand the closest unfinished node. With non-negative weights, once a node is popped with distance
d, no later path can beat it. Theif d > dist[u]: continueline skips stale heap entries instead of decreasing keys (lazy deletion). O((V + E) log V). - In the first graph the direct edge 0→1 costs 4, but 0→2→1 costs 3, and 0→2→1→3 costs 4.
- Network delay: run Dijkstra from the source; the answer is the largest distance, or -1 if some node is unreachable.
- Cheapest flights within k stops: k stops means at most k+1 edges. Each Bellman-Ford round allows one more edge; copying
costper round stops a round from chaining several edges. With 1 stop the best is 400 (0→2→3); with 2 stops it’s 300 (0→1→2→3).
Choosing an algorithm
| Graph | Algorithm | Time |
|---|---|---|
| Unweighted | BFS | O(V + E) |
| Weights 0 or 1 | 0-1 BFS with a deque | O(V + E) |
| Non-negative weights | Dijkstra | O((V + E) log V) |
| Negative weights, or a limit on edges | Bellman-Ford | O(V·E) or O(k·E) |
| All pairs, small V | Floyd-Warshall | O(V³) |
Dijkstra fails with negative edges because a node finalised early could later be reached more cheaply through a negative edge.
Practise: shortest path problems.
Key takeaways
- Dijkstra = BFS with a min-heap keyed by distance; requires non-negative weights.
- Skip stale heap entries with
if d > dist[u]instead of decrease-key. - Bellman-Ford handles negative weights and “at most k edges” by relaxing in rounds.
- Copy the distance array each round when the edge count is limited.
Exercises
- Path with minimum effort (LeetCode 1631): Dijkstra on a grid where cost is the maximum step.
- Return the actual shortest path, not just its length, by storing parents.
- Swim in rising water (LeetCode 778) with Dijkstra, then with binary search plus BFS.
Quiz
- Why does Dijkstra need non-negative edge weights?
- What does
if d > dist[u]: continuedo? - Why does
cheapest_with_k_stopscopy the cost array each round?
Show answers
- It assumes a popped node’s distance is final; a negative edge found later could make that distance smaller.
- It skips outdated heap entries for nodes whose distance has since improved (lazy deletion).
- So each round extends paths by exactly one edge; updating in place could use several new edges in one round and break the stop limit.