Advanced Graph Algorithms

Graph algorithms are at the heart of AI systems: knowledge graphs, dependency resolution in ML pipelines, neural architecture search, and resource allocation. This lesson presents five contest-style problems covering the most important advanced graph algorithms, each with an AI/ML twist.

Problem 1: Bellman-Ford — Negative Cycle Detection in Reward Systems

Approach: Bellman-Ford with Negative Cycle Detection

Bellman-Ford relaxes all edges N-1 times. If any edge can still be relaxed after N-1 iterations, a negative cycle exists. To check if it affects the path to N-1, we track which nodes are reachable from negative cycle nodes.

from collections import defaultdict, deque

def bellman_ford(n, edges, src, dst):
    """Bellman-Ford with negative cycle detection on path.
    Time: O(V * E), Space: O(V)
    """
    INF = float('inf')
    dist = [INF] * n
    dist[src] = 0

    # Relax all edges N-1 times
    for i in range(n - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:
            break  # Early termination

    # Detect negative cycles: try one more relaxation
    neg_cycle_nodes = set()
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            neg_cycle_nodes.add(v)

    if not neg_cycle_nodes:
        return dist[dst] if dist[dst] != INF else "UNREACHABLE"

    # BFS from negative cycle nodes to see if dst is reachable
    adj = defaultdict(list)
    for u, v, w in edges:
        adj[u].append(v)

    visited = set(neg_cycle_nodes)
    queue = deque(neg_cycle_nodes)
    while queue:
        node = queue.popleft()
        if node == dst:
            return "EXPLOITABLE"
        for neighbor in adj[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return dist[dst] if dist[dst] != INF else "UNREACHABLE"

# Example: RL environment with 5 states
edges = [
    (0, 1, 4), (0, 2, 5), (1, 2, -3),
    (2, 3, 2), (3, 4, 6), (1, 3, 8)
]
print(bellman_ford(5, edges, 0, 4))  # 9 (0->1->2->3->4 = 4-3+2+6)

# Example with negative cycle
edges_neg = [
    (0, 1, 1), (1, 2, -1), (2, 1, -1), (2, 3, 2)
]
print(bellman_ford(4, edges_neg, 0, 3))  # EXPLOITABLE

Complexity: O(V * E) time, O(V) space.

Problem 2: Floyd-Warshall — All-Pairs Model Similarity

Approach: Floyd-Warshall with Path Reconstruction

def floyd_warshall(n, cost_matrix):
    """All-pairs shortest paths with path reconstruction.
    Time: O(N^3), Space: O(N^2)
    """
    INF = float('inf')

    # Initialize distance and next-hop matrices
    dist = [[INF] * n for _ in range(n)]
    nxt = [[-1] * n for _ in range(n)]

    for i in range(n):
        for j in range(n):
            if i == j:
                dist[i][j] = 0
                nxt[i][j] = j
            elif cost_matrix[i][j] != -1:
                dist[i][j] = cost_matrix[i][j]
                nxt[i][j] = j

    # Floyd-Warshall: try every intermediate node k
    for k in range(n):
        for i in range(n):
            if dist[i][k] == INF:
                continue
            for j in range(n):
                if dist[k][j] == INF:
                    continue
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    nxt[i][j] = nxt[i][k]

    return dist, nxt

def reconstruct_path(nxt, src, dst):
    """Reconstruct shortest path from src to dst"""
    if nxt[src][dst] == -1:
        return []
    path = [src]
    while src != dst:
        src = nxt[src][dst]
        path.append(src)
    return path

# Example: Model zoo transfer costs
# Models: 0=ResNet, 1=VGG, 2=BERT, 3=GPT, 4=ViT
cost = [
    [ 0,  3, -1, -1,  7],  # ResNet
    [-1,  0,  2, -1, -1],  # VGG
    [-1, -1,  0,  1, -1],  # BERT
    [ 6, -1, -1,  0,  1],  # GPT
    [-1, -1,  4, -1,  0],  # ViT
]

dist, nxt = floyd_warshall(5, cost)
models = ["ResNet", "VGG", "BERT", "GPT", "ViT"]

# Print optimal transfer costs
print("Optimal transfer costs:")
for i in range(5):
    for j in range(5):
        if dist[i][j] == float('inf'):
            print(f"  {models[i]} -> {models[j]}: IMPOSSIBLE")
        elif i != j:
            path = reconstruct_path(nxt, i, j)
            path_str = " -> ".join(models[p] for p in path)
            print(f"  {models[i]} -> {models[j]}: cost {dist[i][j]} via {path_str}")

Complexity: O(N^3) time, O(N^2) space. Suitable for N ≤ 500.

Problem 3: Max Flow — Data Pipeline Throughput

Approach: Edmonds-Karp (BFS-based Ford-Fulkerson)

from collections import defaultdict, deque

def max_flow_edmonds_karp(n, edges, source, sink):
    """Edmonds-Karp algorithm (Ford-Fulkerson with BFS).
    Time: O(V * E^2), Space: O(V + E)
    """
    # Build adjacency list with capacity and reverse edges
    graph = defaultdict(dict)
    for u, v, cap in edges:
        # Forward edge
        graph[u][v] = graph[u].get(v, 0) + cap
        # Reverse edge (for residual graph)
        if v not in graph or u not in graph[v]:
            graph[v][u] = graph[v].get(u, 0)

    def bfs(source, sink, parent):
        """Find augmenting path using BFS, return bottleneck capacity"""
        visited = {source}
        queue = deque([(source, float('inf'))])
        while queue:
            node, flow = queue.popleft()
            for neighbor, cap in graph[node].items():
                if neighbor not in visited and cap > 0:
                    visited.add(neighbor)
                    parent[neighbor] = node
                    new_flow = min(flow, cap)
                    if neighbor == sink:
                        return new_flow
                    queue.append((neighbor, new_flow))
        return 0

    total_flow = 0
    while True:
        parent = {}
        bottleneck = bfs(source, sink, parent)
        if bottleneck == 0:
            break

        total_flow += bottleneck

        # Update residual capacities along the path
        node = sink
        while node != source:
            prev = parent[node]
            graph[prev][node] -= bottleneck
            graph[node][prev] = graph[node].get(prev, 0) + bottleneck
            node = prev

    return total_flow

# Example: Data pipeline with capacity constraints
# Node 0 = data source, Node 5 = training server
edges = [
    (0, 1, 10), (0, 2, 8),
    (1, 3, 5),  (1, 4, 7),
    (2, 3, 6),  (2, 4, 4),
    (3, 5, 8),  (4, 5, 9),
]
print(f"Max throughput: {max_flow_edmonds_karp(6, edges, 0, 5)}")
# Max throughput: 18

# Bottleneck analysis: the pipeline can process 18 units/sec
edges_bottleneck = [
    (0, 1, 100), (1, 2, 1), (2, 3, 100)  # Edge 1->2 is bottleneck
]
print(f"Bottleneck pipeline: {max_flow_edmonds_karp(4, edges_bottleneck, 0, 3)}")
# Bottleneck pipeline: 1

Complexity: O(V * E^2) time for Edmonds-Karp. In practice, much faster due to BFS finding shortest augmenting paths.

Problem 4: Bipartite Matching — GPU Task Assignment

Approach: Hungarian Algorithm (Hopcroft-Karp)

def max_bipartite_matching(n_jobs, n_gpus, compatibility):
    """Find maximum bipartite matching using augmenting paths.
    Time: O(V * E), Space: O(V + E)
    """
    # Build adjacency list: job -> list of compatible GPUs
    adj = [[] for _ in range(n_jobs)]
    for job, gpu in compatibility:
        adj[job].append(gpu)

    # match_gpu[g] = job assigned to GPU g (-1 if unassigned)
    match_gpu = [-1] * n_gpus

    def dfs(job, visited):
        """Try to find augmenting path from this job"""
        for gpu in adj[job]:
            if gpu in visited:
                continue
            visited.add(gpu)

            # If GPU is free or we can reassign the current job on it
            if match_gpu[gpu] == -1 or dfs(match_gpu[gpu], visited):
                match_gpu[gpu] = job
                return True
        return False

    matched = 0
    for job in range(n_jobs):
        visited = set()
        if dfs(job, visited):
            matched += 1

    # Build assignment
    assignment = {}
    for gpu, job in enumerate(match_gpu):
        if job != -1:
            assignment[job] = gpu

    return matched, assignment

# Example: 5 training jobs, 4 GPUs
compatibility = [
    (0, 0), (0, 1),         # Job 0 can run on GPU 0 or 1
    (1, 0), (1, 2),         # Job 1 can run on GPU 0 or 2
    (2, 1), (2, 3),         # Job 2 can run on GPU 1 or 3
    (3, 2),                 # Job 3 can only run on GPU 2
    (4, 3),                 # Job 4 can only run on GPU 3
]

matched, assignment = max_bipartite_matching(5, 4, compatibility)
print(f"Maximum simultaneous jobs: {matched}")
print("Assignment:")
for job, gpu in sorted(assignment.items()):
    print(f"  Job {job} -> GPU {gpu}")
# Maximum simultaneous jobs: 4
# Assignment:
#   Job 0 -> GPU 1
#   Job 1 -> GPU 0
#   Job 3 -> GPU 2
#   Job 4 -> GPU 3

Complexity: O(V * E) time for the augmenting path approach. Hopcroft-Karp improves this to O(E * sqrt(V)).

Problem 5: Strongly Connected Components — Knowledge Graph Clustering

Approach: Tarjan's Algorithm

import sys
sys.setrecursionlimit(200000)

def tarjan_scc(n, adj):
    """Find all SCCs using Tarjan's algorithm.
    Time: O(V + E), Space: O(V)
    """
    index_counter = [0]
    stack = []
    on_stack = [False] * n
    index = [-1] * n
    lowlink = [-1] * n
    sccs = []

    def strongconnect(v):
        index[v] = index_counter[0]
        lowlink[v] = index_counter[0]
        index_counter[0] += 1
        stack.append(v)
        on_stack[v] = True

        for w in adj[v]:
            if index[w] == -1:
                strongconnect(w)
                lowlink[v] = min(lowlink[v], lowlink[w])
            elif on_stack[w]:
                lowlink[v] = min(lowlink[v], index[w])

        # If v is a root node, pop the SCC
        if lowlink[v] == index[v]:
            scc = []
            while True:
                w = stack.pop()
                on_stack[w] = False
                scc.append(w)
                if w == v:
                    break
            sccs.append(scc)

    for v in range(n):
        if index[v] == -1:
            strongconnect(v)

    return sccs

# Example: Knowledge graph with entity relationships
# 0=ML, 1=DL, 2=NLP, 3=CV, 4=RL, 5=Robotics, 6=Ethics
adj = [[] for _ in range(7)]
edges = [
    (0, 1), (1, 2), (2, 0),  # ML <-> DL <-> NLP cycle
    (1, 3), (3, 1),           # DL <-> CV cycle
    (4, 5), (5, 4),           # RL <-> Robotics cycle
    (3, 4),                   # CV -> RL (one-way)
    (6, 0),                   # Ethics -> ML (one-way)
]
for u, v in edges:
    adj[u].append(v)

sccs = tarjan_scc(7, adj)
entities = ["ML", "DL", "NLP", "CV", "RL", "Robotics", "Ethics"]
print(f"Number of SCCs: {len(sccs)}")
for i, scc in enumerate(sccs):
    names = [entities[n] for n in scc]
    print(f"  Cluster {i+1}: {names}")

# Number of SCCs: 3
# Cluster 1: ['RL', 'Robotics']
# Cluster 2: ['ML', 'NLP', 'DL', 'CV']
# Cluster 3: ['Ethics']

Complexity: O(V + E) time, O(V) space. Tarjan's is the gold standard for SCC computation.

Key Takeaways

• Bellman-Ford handles negative edge weights and detects negative cycles in O(V * E) — essential for RL reward analysis.
• Floyd-Warshall computes all-pairs shortest paths in O(N^3) — ideal for dense graphs with N ≤ 500.
• Max flow (Edmonds-Karp) finds maximum throughput in capacity-constrained networks in O(V * E^2).
• Bipartite matching assigns tasks to resources optimally — directly applicable to GPU scheduling in ML.
• Tarjan's SCC algorithm finds tightly-coupled components in O(V + E) — used for knowledge graph analysis and dependency cycle detection.