Advanced Graphs

How it works

Once edges have different costs, BFS no longer gives shortest paths, because a path with more edges can be cheaper. Dijkstra's algorithm fixes this by always expanding the closest unfinished node, using a min-heap keyed by distance.

Dijkstra works because with non-negative weights, the closest node in the heap can never be improved later: any other route goes through a node that is already at least as far. That is also why negative edges break it, and why Bellman-Ford (relax every edge V - 1 times) exists.

Minimum spanning trees connect every node at the lowest total cost. Prim's grows one tree from a start node with a heap of crossing edges; Kruskal's sorts all edges and adds each one that joins two different components, using union-find.

Disguises include network delay times, cheapest flights within k stops (Bellman-Ford with a stop limit), paths that minimize the maximum effort (Dijkstra on a different cost function), connecting points at minimum cost, and reconstructing an itinerary that uses every ticket (an Eulerian path).

How to attack it

1. 1Check edge weights: all equal means BFS, non-negative means Dijkstra, negative means Bellman-Ford.
2. 2Define what 'distance' means; it may be a maximum along the path, not a sum.
3. 3Store (distance, node) in the heap and skip stale entries when popped.
4. 4For 'connect everything cheaply', use Kruskal or Prim instead of shortest paths.
5. 5Add any extra constraint (stops, fuel) to the state, not to the graph.

Template

A skeleton to adapt, not a solution to paste. Write it from memory a few times.

import heapq


def dijkstra(n, edges, source):
    graph = [[] for _ in range(n)]
    for u, v, w in edges:          # directed edge u -> v with weight w >= 0
        graph[u].append((v, w))
    dist = [float("inf")] * n
    dist[source] = 0
    heap = [(0, source)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue               # stale entry: a shorter path was found
        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return dist


def kruskal(n, edges):
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]   # path halving
            x = parent[x]
        return x
    total = 0
    for w, u, v in sorted(edges):           # edges as (weight, u, v)
        ru, rv = find(u), find(v)
        if ru != rv:
            parent[ru], total = rv, total + w
    return total

What it costs