15. Shortest Path and MST

The previous lesson covered BFS for shortest path in unweighted graphs. But what about weighted graphs — where edges have different costs? That's where Dijkstra's and Bellman-Ford come in. And when you need to connect all nodes with minimum total cost, you need a Minimum Spanning Tree.

Dijkstra's Algorithm

Finds the shortest path from one source to all other nodes in a weighted graph with non-negative edges. Uses Python's heapq module — a min-heap built on a list.

LeetCode 743 - Network Delay Time

import heapq
from collections import defaultdict

def dijkstra(graph: dict, start: int, n: int) -> list[int]:
    dist = [float('inf')] * n
    dist[start] = 0
    heap = [(0, start)]  # (distance, node)

    while heap:
        d, node = heapq.heappop(heap)
        if d > dist[node]:
            continue  # already found a shorter path
        for neighbor, weight in graph[node]:
            new_dist = dist[node] + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                heapq.heappush(heap, (new_dist, neighbor))

    return dist

How it works: start at source with distance 0. Pop the closest node from the heap. For each neighbor, if going through this node is shorter than the best known path, update and push to heap. Repeat until heap is empty.

Key detail: heapq is a min-heap that orders tuples by first element — so (distance, node) automatically prioritizes the shortest distance. No custom comparator needed.

Time: O((V + E) log V) with a binary heap. The log V comes from heap operations.

Limitation: doesn't work with negative edge weights. If an edge has weight -5, Dijkstra might skip a path that later becomes shorter through the negative edge.

Bellman-Ford Algorithm

Handles negative edge weights. Slower than Dijkstra but more general. Also detects negative cycles. A negative cycle is a loop where the total weight of edges sums to less than zero. If you walk around it, your distance gets shorter every lap — infinitely.

def bellman_ford(edges: list[list[int]], n: int, start: int) -> list[int] | None:
    dist = [float('inf')] * n
    dist[start] = 0

    # Relax all edges V-1 times
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    # Check for negative cycles (one more relaxation)
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return None  # negative cycle exists

    return dist

Time: O(V × E). Slower than Dijkstra, but works with negative weights.

When to use: currency exchange (detect arbitrage = negative cycle), graphs where edges can have negative costs.

When to Use Dijkstra vs BFS vs Bellman-Ford

Decision: unweighted → BFS. Non-negative weights → Dijkstra. Negative weights → Bellman-Ford.

Dijkstra Variants

Shortest path to a specific target

Stop early once you pop the target from the heap:

def shortest_path(graph: dict, start: int, end: int) -> int:
    dist = defaultdict(lambda: float('inf'))
    dist[start] = 0
    heap = [(0, start)]

    while heap:
        d, node = heapq.heappop(heap)
        if node == end:
            return d  # first time we pop target = shortest path
        if d > dist[node]:
            continue
        for neighbor, weight in graph[node]:
            new_dist = d + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                heapq.heappush(heap, (new_dist, neighbor))

    return -1  # unreachable

K stops limit (modified Bellman-Ford)

LeetCode 787 - Cheapest Flights Within K Stops

def find_cheapest_price(n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:
    dist = [float('inf')] * n
    dist[src] = 0

    for _ in range(k + 1):  # at most k+1 edges
        temp = dist[:]
        for u, v, w in flights:
            if dist[u] != float('inf') and dist[u] + w < temp[v]:
                temp[v] = dist[u] + w
        dist = temp

    return dist[dst] if dist[dst] != float('inf') else -1

Minimum Spanning Tree

An MST connects all nodes in an undirected weighted graph with the minimum total edge weight. No cycles. Exactly V-1 edges for V nodes.

Graph:                    MST (total weight = 6):
  A —3— B                  A     B
  |     |                  |     |
  2     5                  2     1
  |     |                  |     |
  C —1— D                  C —1— D

MST is less common in interviews than shortest path, but it does appear. The two algorithms are Kruskal's (sort edges, union-find) and Prim's (grow from a node with a heap).

Union-Find

Union-Find tracks connected components. Two operations: find (which component is this node in?) and union (merge two components). Used by Kruskal's to detect cycles.

LeetCode 547 - Number of Provinces

class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, x: int, y: int) -> bool:
        px, py = self.find(x), self.find(y)
        if px == py:
            return False  # already connected
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

With path compression and union by rank, both operations are nearly O(1) — technically O(α(n)) which is effectively constant.

Prim's Algorithm

Prim's looks almost identical to Dijkstra — same heap pattern, different meaning:

LeetCode 1584 - Min Cost to Connect All Points

def prim(graph: dict, n: int) -> int:
    visited = [False] * n
    heap = [(0, 0)]  # (weight, node) — start from node 0
    total = 0

    while heap:
        weight, node = heapq.heappop(heap)
        if visited[node]:
            continue
        visited[node] = True
        total += weight
        for neighbor, w in graph[node]:
            if not visited[neighbor]:
                heapq.heappush(heap, (w, neighbor))

    return total

Time: O((V + E) log V) — same as Dijkstra.

For most interviews, know that MST exists, what it means, and that Kruskal's/Prim's solve it. Focus your preparation time on Dijkstra — it appears far more often.

Practice Problems

Key Takeaways

• Dijkstra: shortest path with non-negative weights, uses heapq, O((V+E) log V)
• heapq is a min-heap — push (distance, node) tuples, smallest distance pops first
• Bellman-Ford: shortest path with any weights, detects negative cycles, O(V × E)
• Unweighted → BFS. Non-negative → Dijkstra. Negative → Bellman-Ford
• MST connects all nodes with minimum total edge weight — know it exists, focus prep on Dijkstra
• Prim's for MST looks like Dijkstra — same heap pattern, different meaning
• Union-Find gives nearly O(1) component queries with path compression + union by rank