Advanced Graph Algorithms

1Dijkstra: non-negative shortest paths

Dijkstra finds single-source shortest paths when every edge weight is non-negative. A min-priority queue repeatedly extracts the unsettled vertex with the smallest tentative distance; its distance is then final, and each outgoing edge is relaxed. With a binary heap the cost is O((V + E) \log V). A single negative edge can make a finalized distance wrong — that is why the algorithm refuses negatives.

Figure. Same digraph as the worked example. Node labels show final Dijkstra distances from A; edge labels are weights.

Relax from the nearest unsettled vertex

1. SeedSet dist[s] = 0 and all other distances to \infty; push s into a min-heap keyed by distance.
2. Extract-minPop the unsettled vertex u with smallest dist[u]. That value is now final for non-negative weights.
3. RelaxFor each edge u → v of weight w, if dist[u] + w < dist[v], update dist[v] and push the new key.

Dijkstra with a binary heap

import heapq

def dijkstra(graph, s):
    dist = {s: 0}
    heap = [(0, s)]
    done = set()
    while heap:
        d, u = heapq.heappop(heap)
        if u in done:
            continue
        done.add(u)
        for v, w in graph[u]:
            nd = d + w
            if v not in dist or nd < dist[v]:
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return dist

Coding lab. Dijkstra on the four-city digraph runs in the app, with checks on your output.

2Bellman-Ford: negatives and cycles

Bellman-Ford also computes single-source shortest paths, but it allows negative edge weights. It relaxes every edge in the graph for V - 1 rounds — enough for a shortest path of at most V - 1 edges to propagate. One extra round that still improves a distance proves a negative cycle is reachable from the source. Time is O(VE).

Figure. Same digraph as the ledger. The negative B→C edge is what forces Bellman-Ford over Dijkstra; node labels are final distances from A.

Relax all edges, then check

1. Initializedist[s] = 0; every other distance \infty.
2. V−1 roundsFor each of V - 1 passes, try every edge u → v: if dist[u] + w < dist[v], update dist[v].
3. Cycle checkOne more pass over all edges; any further improvement means a negative cycle is reachable.

Bellman-Ford with cycle flag

def bellman_ford(n, edges, s):
    dist = [float('inf')] * n
    dist[s] = 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  # negative cycle reachable
    return dist

3Which shortest-path algorithm?

Pick the algorithm from the weight regime and the query shape. Non-negative single-source work is Dijkstra. Negatives or an explicit negative-cycle test need Bellman-Ford. Dense all-pairs queries favour Floyd-Warshall's O(V^3) DP over launching Dijkstra from every vertex when that constant-factor and coding cost lose.

Figure. Pick by weight regime: BFS for unit edges, Dijkstra for non-negative, Bellman-Ford when negatives appear.

4Kruskal: sort edges, skip cycles

A minimum spanning tree of a connected undirected weighted graph is a subset of edges that links every vertex, forms no cycle, and has minimum total weight. Kruskal sorts all edges by increasing weight and adds an edge when its endpoints lie in different components — union-find answers that test. Sorting dominates: O(E \log E).

Figure. Same undirected graph as the Kruskal ledger. Solid edges AB, BC, CD form the MST; dashed AC and BD were skipped as cycles.

Grow a forest by lightest safe edge

1. SortOrder every edge by non-decreasing weight.
2. TestFor the next edge u–v, find the components of u and v (union-find).
3. Add or skipIf the components differ, union them and keep the edge; if they match, the edge would close a cycle — skip it.

Kruskal with union-find

def kruskal(n, edges):
    parent = list(range(n))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    mst, total = [], 0
    for u, v, w in sorted(edges, key=lambda e: e[2]):
        ru, rv = find(u), find(v)
        if ru == rv:
            continue
        parent[rv] = ru
        mst.append((u, v, w))
        total += w
    return mst, total

5Prim: grow one tree from a root

Prim builds the same MST by growing a single tree from a start vertex. A heap stores the lightest edge from the tree to each outsider; extract-min pulls the next vertex into the tree and relaxes its edges to remaining outsiders. With a binary heap the cost is O(E \log V). On a dense graph Prim's adjacency-driven growth is the natural fit; Kruskal's global edge sort is the sparse-graph habit.

Same undirected four-vertex graph as Kruskal: sort edges, skip cycles — Prim grows one tree from a root by always adding the lightest edge out of the current set, ending at the same weight-6 MST.

Expand the cut by the lightest crossing edge

1. StartPut an arbitrary root in the tree S; key[root] = 0 and other keys \infty.
2. ExtractPop the outsider u with smallest key[u] — the lightest edge into S — and add u to S.
3. Relax cutFor each edge u–v with v outside S, if w(u,v) < key[v], set key[v] = w(u,v) and remember parent v ← u.

Prim with a binary heap

import heapq

def prim(graph, root=0):
    n = len(graph)
    key = [float('inf')] * n
    parent = [-1] * n
    key[root] = 0
    heap = [(0, root)]
    in_mst = [False] * n
    total = 0
    while heap:
        k, u = heapq.heappop(heap)
        if in_mst[u]:
            continue
        in_mst[u] = True
        total += k
        for v, w in graph[u]:
            if not in_mst[v] and w < key[v]:
                key[v] = w
                parent[v] = u
                heapq.heappush(heap, (w, v))
    return parent, total

6Topological sort on a DAG

A topological order of a directed acyclic graph lists every vertex so that every edge u → v has u before v. Kahn's algorithm repeatedly peels vertices of in-degree 0; DFS records finish times and reverses them. Both run in O(V + E). Topological sort only exists for a DAG — if Kahn cannot place every vertex, a cycle remains.

Figure. Same DAG as the course-schedule ledger. Edges point from prerequisite to dependent course; one valid order is 0, 1, 2, 3.

Kahn's in-degree peel

1. In-degreesCount incoming edges for every vertex; enqueue all with in-degree 0.
2. PeelDequeue u, append u to the order, and decrement each neighbor's in-degree; enqueue any that hit 0.
3. DetectIf the order length equals V, it is a valid topo order; leftovers with positive in-degree prove a cycle.

Kahn topological order

from collections import deque

def topo_kahn(n, edges):
    g = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:
        g[u].append(v)
        indeg[v] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == n else None

7Floyd-Warshall: all-pairs DP

Floyd-Warshall fills a V \times V distance matrix by trying every vertex k as an intermediate: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). After all k, every entry is a shortest path (or \infty if unreachable), assuming no negative cycle. Time O(V^3) and space O(V^2) — simpler than V Dijkstra runs on dense graphs, and it handles negatives the same way Bellman-Ford does (still no negative cycles).

Figure. Same three-vertex digraph as the Floyd ledger. Direct 1→3 costs 8; after k=2 the matrix holds 5 via vertex 2.

Triple loop over intermediates

1. Seed matrixdist[i][i] = 0; dist[i][j] = w(i,j) for each edge; all other entries \infty.
2. For each kAllow paths that may use vertex k (and previously considered intermediates).
3. Relax i,jFor every pair (i,j), replace dist[i][j] if i → … → k → … → j is shorter.

Floyd-Warshall

def floyd_warshall(dist):
    n = len(dist)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                through = dist[i][k] + dist[k][j]
                if through < dist[i][j]:
                    dist[i][j] = through
    return dist