Shortest Cycle in a Graph (Girth and Minimum Weight Cycle)

This is an extension topic beyond most interviews; it pays off when an OA asks for the length of the shortest cycle or the cheapest loop, a question that plain cycle detection does not answer.

Intuition

Detecting whether a cycle exists is one DFS. Finding the shortest one is harder, because DFS explores in an order unrelated to length. The fix is to combine cycle detection with shortest-path machinery:

• Unweighted, undirected (girth). Run BFS from every vertex s. Whenever BFS sees an edge u-v that is not the tree edge it arrived by and v is already discovered, the two tree paths plus that edge form a closed walk of length dist[u] + dist[v] + 1, which contains a cycle at most that long. If s lies on a shortest cycle, BFS from s meets such an edge exactly at the cycle's length. Taking the minimum over all sources is therefore exact.
• Weighted, undirected. Floyd-Warshall has a convenient invariant: just before vertex k becomes usable as an intermediate, dist[i][j] is the shortest i-j path through vertices smaller than k. Every cycle has a largest vertex k with two cycle neighbors i and j, so its weight is dist[i][j] + w(j, k) + w(k, i) at exactly that moment. Check all pairs i < j < k before relaxing with k.
• Weighted, directed. A cycle through s is a shortest path from s to some u plus an edge u -> s. Run Dijkstra from every s (non-negative weights) and close the loop with each edge entering s.

When to use it in interviews / OAs

• "Return the length of the shortest cycle in the graph" (undirected, unweighted, n up to about 1000).
• "Minimum weight cycle", "cheapest round trip", "smallest loop in a road network".
• "Minimum degree of a connected trio" or triangle problems are the length-3 special case (check common neighbors directly).
• As a contrast: "longest cycle" in a general graph is NP-hard, but if every vertex has at most one outgoing edge (a functional graph) you can walk each chain with timestamps in O(n).

Template

Girth of an unweighted undirected graph

import heapq
from collections import deque

INF = float("inf")


def shortest_cycle_unweighted(n: int, edges: list[tuple[int, int]]) -> int:
    # simple undirected graph (no self-loops or parallel edges); -1 if acyclic
    adj: list[list[int]] = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    best = INF
    for s in range(n):
        dist = [-1] * n
        parent = [-1] * n
        dist[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for v in adj[u]:
                if dist[v] == -1:
                    dist[v] = dist[u] + 1
                    parent[v] = u
                    q.append(v)
                elif v != parent[u]:  # non-tree edge: closes a cycle of at most this length
                    best = min(best, dist[u] + dist[v] + 1)
    return -1 if best == INF else best

Minimum weight cycle, undirected (Floyd-Warshall)

def min_weight_cycle_undirected(n: int, edges: list[tuple[int, int, int]]) -> float:
    # cycles with at least 3 vertices; parallel edges keep their cheapest copy
    w = [[INF] * n for _ in range(n)]
    for u, v, c in edges:
        if u != v:
            w[u][v] = w[v][u] = min(w[u][v], c)
    dist = [row[:] for row in w]
    for i in range(n):
        dist[i][i] = 0
    best = INF
    for k in range(n):
        for i in range(k):  # cycles whose largest vertex is k: i ... j (all < k), then j-k-i
            if w[k][i] == INF:
                continue
            for j in range(i + 1, k):
                cand = dist[i][j] + w[j][k] + w[k][i]
                if cand < best:
                    best = cand
        for i in range(n):  # now let k be an intermediate vertex
            dik = dist[i][k]
            if dik == INF:
                continue
            for j in range(n):
                if dik + dist[k][j] < dist[i][j]:
                    dist[i][j] = dik + dist[k][j]
    return best

Minimum weight cycle, directed (Dijkstra from every vertex)

def min_weight_cycle_directed(n: int, edges: list[tuple[int, int, int]]) -> float:
    adj: list[list[tuple[int, int]]] = [[] for _ in range(n)]
    into: list[list[tuple[int, int]]] = [[] for _ in range(n)]  # edges entering each vertex
    for u, v, c in edges:
        adj[u].append((v, c))
        into[v].append((u, c))
    best = INF
    for s in range(n):
        dist = [INF] * n
        dist[s] = 0
        pq = [(0, s)]
        while pq:
            d, u = heapq.heappop(pq)
            if d > dist[u] or d >= best:  # stale, or cannot beat the best cycle
                continue
            for v, c in adj[u]:
                if d + c < dist[v]:
                    dist[v] = d + c
                    heapq.heappush(pq, (dist[v], v))
        for u, c in into[s]:  # close the loop u -> s
            best = min(best, dist[u] + c)
    return best

Complexity

• BFS from every vertex: O(n * (n + m)) time, O(n + m) memory; fine for n around 1000 to 2000.
• Floyd-Warshall variant: O(n^3) time, O(n^2) memory; only for small n (a few hundred in Python).
• Dijkstra from every vertex: O(n * m log n) time; the d >= best cut-off helps a lot in practice.
• Alternative for sparse undirected graphs: for every edge (u, v, w), remove it and run Dijkstra from u to v; the cycle is dist + w. O(m * m log n).

Common pitfalls

• Counting the tree edge as a cycle. In undirected BFS, the edge back to the parent is not a cycle; with parallel edges you would compare edge ids instead of the parent vertex.
• One BFS is not enough. A single source only finds cycles near it; the girth needs every source (or every edge).
• Checking after relaxing in Floyd. The cycle check for k must happen before k is used as an intermediate, otherwise dist[i][j] may already pass through k and the "cycle" reuses vertices.
• Undirected edges in the directed method. Treating an undirected edge as two directed arcs creates fake 2-cycles u -> v -> u.
• Defining "cycle". Decide whether self-loops (length 1) and 2-cycles count; problems usually exclude them for undirected graphs.
• Negative weights. Dijkstra-based methods require non-negative weights; with negative edges, Floyd-Warshall still works and a negative dist[i][i] reveals a negative cycle.

Interview variations

• Shortest cycle in a graph. The BFS template; n up to 1000 is the intended scale.
• Minimum weight cycle. Floyd variant for small n, Dijkstra per vertex or per edge for sparse graphs.
• Minimum degree of a connected trio. Enumerate edges (u, v) and common neighbors w; degree sum minus 6.
• Longest cycle where every node has at most one out-edge. Walk from each unvisited node, stamping visit times; when you hit a node stamped in the current walk, the cycle length is the time difference.
• Negative cycle detection. Bellman-Ford's extra round or Floyd's diagonal, covered with shortest paths.