Shortest Paths and Spanning Trees: Dijkstra, Bellman-Ford, Kruskal

Start from the question. All steps cost the same: BFS already gives the fewest steps. Costs differ and none is negative: Dijkstra. Some costs are negative: Bellman-Ford. You need the distance between every pair of nodes: Floyd-Warshall. You need the cheapest way to connect all nodes: a minimum spanning tree.

Dijkstra. Keep a heap of (distance so far, node). Pop the closest unfinished node; its distance is now final, because every other route to it would have to go through something at least as far away. Relax each edge: if going through this node is cheaper, record it and push the neighbor. Cost: O(E log V).

import heapq

graph = {
    'A': [('B', 4), ('C', 1)],
    'B': [('D', 1)],
    'C': [('B', 2), ('D', 5)],
    'D': [],
}

def dijkstra(graph, start):
    dist = {start: 0}
    heap = [(0, start)]
    while heap:
        d, node = heapq.heappop(heap)
        if d > dist.get(node, float('inf')):
            continue                  # stale entry: a cheaper one was used
        for nxt, w in graph[node]:
            nd = d + w
            if nd < dist.get(nxt, float('inf')):
                dist[nxt] = nd
                heapq.heappush(heap, (nd, nxt))
    return dist

dijkstra(graph, 'A')   # {'A': 0, 'B': 3, 'C': 1, 'D': 4}

Why negative costs break it. Dijkstra freezes a node's distance when it is popped. A negative edge discovered later could still make that route cheaper, so the frozen answer would be wrong. Here the best way to B is A to C to B, costing 1 + 2 = 3, not the direct 4.

Bellman-Ford. Relax every edge, V - 1 times. After round k, every shortest path that uses at most k edges is correct. One more round that still improves something proves a negative cycle, a loop you could ride forever to lower the cost. Cost: O(V x E). It is slower, but it handles negative edges and detects those cycles.

def bellman_ford(n, edges, src):
    dist = [float('inf')] * n
    dist[src] = 0
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            return None               # a negative cycle
    return dist

bellman_ford(4, [(0, 1, 4), (0, 2, 1), (2, 1, -2), (1, 3, 1)], 0)   # [0, -1, 1, 0]
bellman_ford(3, [(0, 1, 1), (1, 2, -3), (2, 1, 1)], 0)              # None

Floyd-Warshall answers 'every pair' with three nested loops over a distance table: for each possible middle node k, try dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). It is O(V^3), so it suits graphs of a few hundred nodes.

Spanning trees. A spanning tree connects all V nodes with V - 1 edges and no loop. The minimum one has the smallest total weight. Kruskal: sort the edges by weight and add each one unless it would close a loop, which a union-find answers in near-constant time. Prim: grow one tree outward, always adding the cheapest edge that leaves it, with a heap. Both are correct because the cheapest edge crossing any cut belongs to some minimum tree.

def kruskal(n, edges):                  # edges are (weight, a, b)
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    total, used = 0, []
    for w, a, b in sorted(edges):
        ra, rb = find(a), find(b)
        if ra != rb:                    # different groups: no loop
            parent[ra] = rb
            total += w
            used.append((a, b, w))
    return total, used

kruskal(4, [(1, 0, 1), (4, 0, 2), (3, 1, 2), (2, 1, 3), (5, 2, 3)])
# (6, [(0, 1, 1), (1, 3, 2), (1, 2, 3)])

Where it runs in production. Routing and latency-aware path choice, map directions, currency-arbitrage checks (a negative cycle is a free-money loop), cheapest cabling or network layout, and clustering.