Graph Algorithms for Contests — Math for Competitive Programming | Sabaoon Academy

Graph problems make up a significant portion of competitive programming. This lesson covers the algorithms you need — shortest paths, MST, topological sort, and SCCs — with contest-ready implementations.

Shortest Paths

Dijkstra's Algorithm — O((V + E) log V)

Single-source shortest paths in graphs with non-negative edge weights.

import heapq

def dijkstra(graph, src, n):
    # graph[u] = [(weight, v), ...]
    dist = [float('inf')] * n
    dist[src] = 0
    pq = [(0, src)]   # (distance, node)

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue   # stale entry
        for w, v in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))

    return dist

Key invariant: once a node is popped from the priority queue with its final distance, that distance is optimal. This fails with negative weights (use Bellman-Ford).

Bellman-Ford — O(VE)

Handles negative edge weights. Detects negative cycles.

def bellman_ford(edges, src, n):
    # edges = [(u, v, w), ...]
    dist = [float('inf')] * n
    dist[src] = 0

    for _ in range(n - 1):     # relax all edges n-1 times
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    # Check for negative cycles
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            return None   # negative cycle exists

    return dist

Floyd-Warshall — O(V³)

All-pairs shortest paths. Good when V ≤ 500.

def floyd_warshall(n, edges):
    dist = [[float('inf')] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = min(dist[u][v], w)

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

After Floyd-Warshall: negative cycle exists if dist[i][i] < 0 for any i.

Which to Use?

Situation	Algorithm
Single source, non-negative weights	Dijkstra O((V+E)logV)
Single source, negative weights	Bellman-Ford O(VE)
All pairs, V ≤ 500	Floyd-Warshall O(V³)
All pairs, sparse graph	Dijkstra from every source
DAG shortest paths	Topological sort + DP O(V+E)
Unweighted shortest paths	BFS O(V+E)

Minimum Spanning Tree

Kruskal's Algorithm — O(E log E)

Sort edges by weight, greedily add edges that don't create a cycle (use Union-Find).

def kruskal(n, edges):
    # edges = [(weight, u, v)]
    edges.sort()
    parent = list(range(n))
    rank = [0] * n

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

    def union(x, y):
        px, py = find(x), find(y)
        if px == py: return False
        if rank[px] < rank[py]: px, py = py, px
        parent[py] = px
        if rank[px] == rank[py]: rank[px] += 1
        return True

    mst_weight = 0
    mst_edges = []
    for w, u, v in edges:
        if union(u, v):
            mst_weight += w
            mst_edges.append((u, v, w))
            if len(mst_edges) == n - 1:
                break

    return mst_weight, mst_edges

Prim's Algorithm — O(E log V)

Grow the MST one vertex at a time from a seed, always adding the cheapest edge connecting the tree to an unvisited vertex.

def prim(graph, n):
    # graph[u] = [(weight, v)]
    visited = [False] * n
    dist = [float('inf')] * n
    dist[0] = 0
    pq = [(0, 0)]
    total = 0

    while pq:
        w, u = heapq.heappop(pq)
        if visited[u]: continue
        visited[u] = True
        total += w
        for ew, v in graph[u]:
            if not visited[v] and ew < dist[v]:
                dist[v] = ew
                heapq.heappush(pq, (ew, v))

    return total

Kruskal vs Prim: Kruskal is simpler for sparse graphs (sort edges). Prim is faster for dense graphs (E close to V²) with adjacency matrix.

Topological Sort

A linear ordering of vertices in a DAG such that for every edge u → v, u appears before v.

Kahn's Algorithm (BFS-based)

from collections import deque

def topo_sort(n, adj):
    in_degree = [0] * n
    for u in range(n):
        for v in adj[u]:
            in_degree[v] += 1

    queue = deque(u for u in range(n) if in_degree[u] == 0)
    order = []

    while queue:
        u = queue.popleft()
        order.append(u)
        for v in adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)

    if len(order) < n:
        return None   # cycle detected
    return order

If the result has fewer than n nodes, a cycle exists — the graph is not a DAG.

Applications: dependency resolution (make, npm), course scheduling, detecting deadlocks, DP on DAGs.

DP on DAGs

Once topologically sorted, DP over vertices in order to compute shortest/longest paths, counting paths, etc.:

def dag_longest_path(n, adj, weights, order):
    dp = [0] * n
    for u in order:
        for v, w in adj[u]:
            dp[v] = max(dp[v], dp[u] + w)
    return max(dp)

Strongly Connected Components (SCC)

An SCC is a maximal set of vertices where every vertex is reachable from every other.

Kosaraju's Algorithm — O(V + E)

def kosaraju(n, adj):
    # Step 1: DFS on original graph, record finish order
    visited = [False] * n
    finish_order = []

    def dfs1(u):
        visited[u] = True
        for v in adj[u]:
            if not visited[v]:
                dfs1(v)
        finish_order.append(u)

    for u in range(n):
        if not visited[u]:
            dfs1(u)

    # Step 2: DFS on transposed graph in reverse finish order
    radj = [[] for _ in range(n)]
    for u in range(n):
        for v in adj[u]:
            radj[v].append(u)

    visited = [False] * n
    sccs = []

    def dfs2(u, comp):
        visited[u] = True
        comp.append(u)
        for v in radj[u]:
            if not visited[v]:
                dfs2(v, comp)

    for u in reversed(finish_order):
        if not visited[u]:
            comp = []
            dfs2(u, comp)
            sccs.append(comp)

    return sccs

Applications: SCC condensation turns any directed graph into a DAG of SCCs, enabling DP. Used in: 2-SAT solving, Kosaraju's on the implication graph, finding strongly connected web components.

2-SAT

A satisfiability problem where each clause has at most 2 literals can be solved in O(V + E) using SCCs on the implication graph.

Each variable x has two nodes: x and ¬x. Clause (a ∨ b) adds implications (¬a → b) and (¬b → a).

After finding SCCs: if x and ¬x are in the same SCC, the formula is unsatisfiable. Otherwise, assign x = True if x's SCC appears later in topological order than ¬x's SCC.

Key Takeaways

Dijkstra: non-negative weights, O((V+E)logV). Bellman-Ford: negative weights, O(VE), detects negative cycles. Floyd-Warshall: all-pairs, O(V³).
Kruskal: sort edges + Union-Find. Prim: priority queue growing from seed. Both give MST in O(E log V).
Topological sort (Kahn's): process zero-in-degree nodes iteratively. Enables O(V+E) DP on DAGs.
SCC (Kosaraju's): two DFS passes — one on original graph, one on reversed graph. O(V+E).
Condensing SCCs into a DAG is a powerful transformation for problems with cyclic structure.
2-SAT reduces to SCC on an implication graph — solvable in linear time.