Lesson 15 of 16 Graphs

Dijkstra and Shortest Path Patterns

Shortest path patterns: Dijkstra with a min-heap and lazy deletion, network delay time, and Bellman-Ford for cheapest flights within k stops.

40-50 min advanced 0/16 lessons done
Course contents Lesson 15 of 16 · 0 done
On this page (7 sections)
  1. What you will learn
  2. Signals
  3. Code
  4. Choosing an algorithm
  5. Key takeaways
  6. Exercises
  7. Quiz

What you will learn

  • Dijkstra’s algorithm with Python’s heapq and 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. The if d > dist[u]: continue line 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 cost per 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

GraphAlgorithmTime
UnweightedBFSO(V + E)
Weights 0 or 10-1 BFS with a dequeO(V + E)
Non-negative weightsDijkstraO((V + E) log V)
Negative weights, or a limit on edgesBellman-FordO(V·E) or O(k·E)
All pairs, small VFloyd-WarshallO(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

  1. Path with minimum effort (LeetCode 1631): Dijkstra on a grid where cost is the maximum step.
  2. Return the actual shortest path, not just its length, by storing parents.
  3. Swim in rising water (LeetCode 778) with Dijkstra, then with binary search plus BFS.

Quiz

  1. Why does Dijkstra need non-negative edge weights?
  2. What does if d > dist[u]: continue do?
  3. Why does cheapest_with_k_stops copy the cost array each round?
Show answers
  1. It assumes a popped node’s distance is final; a negative edge found later could make that distance smaller.
  2. It skips outdated heap entries for nodes whose distance has since improved (lazy deletion).
  3. 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.

Finished this lesson?

Mark it complete to track your progress (saved in this browser).