Graphs and Graph Algorithms Questions

Direct answer

Breadth-first search (BFS) finds the shortest path between two nodes in an unweighted graph because it explores the graph in strict distance order: it fully visits every node at distance 1 from the start before touching any node at distance 2, and so on. The first time any node is reached, that is necessarily via the fewest possible edges, so recording each node's discoverer (its parent) as it is first visited, then walking those parent pointers backward from the target, reconstructs a shortest path in $O(V+E)$ time and $O(V)$ space.

Structured elaboration

Two pieces of state drive the algorithm: a visited set (or equivalently, a parent dict whose keys double as the visited set) to guarantee each node is processed once, and the parent map itself to allow path reconstruction. A first-in-first-out (FIFO) queue guarantees the "distance order" property: the queue always contains nodes from at most two contiguous distance layers at a time, and everything from the current layer is dequeued before anything from the next layer is examined.

Worked example

from collections import deque
from typing import Dict, List

def shortest_path(adj: Dict[int, List[int]], start: int, target: int) -> List[int]:
    # BFS shortest path in an unweighted graph. Returns the node list from
    # start to target inclusive, or [] if target is unreachable.
    if start == target:
        return [start]
    if start not in adj:
        return []

    visited = {start}
    parent = {start: None}
    q = deque([start])
    while q:
        u = q.popleft()
        for v in adj.get(u, []):
            if v not in visited:
                visited.add(v)
                parent[v] = u
                if v == target:
                    q.clear()
                    break
                q.append(v)

    if target not in parent:
        return []

    path = []
    node = target
    while node is not None:
        path.append(node)
        node = parent[node]
    path.reverse()
    return path

if __name__ == "__main__":
    adj = {
        0: [1, 2],
        1: [0, 3],
        2: [0, 3],
        3: [1, 2, 4],
        4: [3],
        5: [6],   # disconnected component
        6: [5],
    }
    print("0 -> 4:", shortest_path(adj, 0, 4))
    print("0 -> 5 (unreachable):", shortest_path(adj, 0, 5))
    print("0 -> 0 (same node):", shortest_path(adj, 0, 0))
    print("7 -> 1 (start not in graph):", shortest_path(adj, 7, 1))

    def bfs_distance(adj, start, target):
        dist = {start: 0}
        q = deque([start])
        while q:
            u = q.popleft()
            for v in adj.get(u, []):
                if v not in dist:
                    dist[v] = dist[u] + 1
                    q.append(v)
        return dist.get(target)

    p = shortest_path(adj, 0, 4)
    ref_dist = bfs_distance(adj, 0, 4)
    print("Path edges match independently computed BFS distance:", len(p) - 1 == ref_dist, f"(path edges={len(p)-1}, ref_dist={ref_dist})")

Output (actually executed with python3):

0 -> 4: [0, 1, 3, 4]
0 -> 5 (unreachable): []
0 -> 0 (same node): [0]
7 -> 1 (start not in graph): []
Path edges match independently computed BFS distance: True (path edges=3, ref_dist=3)

The bfs_distance helper is a separate, minimal BFS that only ever tracks distances, never a path; it exists purely to cross-check the path-returning function's length against an independently computed ground truth, and the two agree.

Complexity

Time $O(V+E)$: each node is enqueued and dequeued at most once, and each edge is examined at most once from each of its endpoints (twice total for an undirected graph, once for a directed graph). Space $O(V)$ for visited and parent, plus the queue, which never holds more nodes than exist at the two frontier layers being processed.

Edge cases

• start == target: returns [start] immediately, a path of length zero (no edges), handled as a special case up front rather than relying on the traversal to "discover" the start node as its own neighbor.
• start not present in adj: returns [] rather than raising, treating an unknown start node the same as "no path exists."
• Disconnected target: the BFS frontier exhausts without ever reaching target; target not in parent catches this and returns [].
• Multiple shortest paths of equal length: BFS returns one of them, determined by adjacency-list iteration order, not necessarily a "canonical" one; if a caller needs a specific tie-break (lexicographically smallest node sequence, for example), that requires sorting each node's neighbor list before traversal.
• Early exit on discovering the target: the q.clear(); break pair stops further expansion the instant the target is first discovered, since BFS guarantees that first discovery is already a shortest path; continuing to explore further nodes would waste work without changing the answer.

Trade-offs and pitfalls

• Common mistake: marking a node visited when it is dequeued rather than when it is first enqueued (discovered). If two different frontier nodes both point to the same not-yet-visited neighbor before either is dequeued, dequeue-time marking lets that neighbor be enqueued twice, wasting work and, worse, letting the second enqueue silently overwrite parent with a different, equally-short but different, predecessor, which is harmless for path length but can produce a different (still valid) path than intended if the caller expects determinism.
• Common mistake: using depth-first search (DFS) instead of BFS for this task. DFS also visits every reachable node, but it does not explore in non-decreasing distance order, so the first path DFS finds to target is not guaranteed to be shortest; DFS proves reachability, not shortest distance, in an unweighted graph.
• A commonly asked variant of this same archetype returns a distance MAP ({node: distance} for every reachable node) instead of a single path. That variant is a strict generalization: the bfs_distance helper above is essentially that function with the path-reconstruction machinery stripped out, and a caller who needs distances to many targets from one source should prefer running that once rather than calling shortest_path repeatedly, which would redundantly re-traverse shared prefixes of the graph on every call.
• For a WEIGHTED graph, none of this generalizes directly. BFS's correctness depends entirely on every edge costing exactly one step; the moment edges have different costs, this becomes Dijkstra's algorithm territory (or 0-1 BFS specifically for {0,1}-weighted edges), not a variant of plain BFS.

Direct answer

Self-loops, parallel edges, isolated nodes, and multi-labeled nodes each break a different assumption that textbook graph algorithms make silently. The fix in every case is the same shape: normalize the input into a well-defined canonical graph once, before any algorithm runs, rather than trying to make every algorithm defensive against every possible malformed input independently.

Structured elaboration

General sanitization, done once up front:

• Canonicalize node identity: if a node can carry multiple labels (say, a user identified by both an internal id and an email), map every label to one canonical id before building the graph, so two labels never get treated as two different vertices.
• Make directedness and weightedness explicit metadata on the graph object, not an assumption baked into each algorithm.
• Decide, as policy, how to treat parallel edges: keep them all, collapse to a single edge with the minimum or summed weight, or reject them, and apply that policy consistently at ingestion time.

Breadth-first search (BFS) and depth-first search (DFS).

• Pitfall: a self-loop (an edge from a node to itself) can cause an algorithm that naively re-enqueues or re-recurses into "unvisited-looking" neighbors to loop forever if it does not check the node against its own visited set before revisiting.
• Pitfall: parallel edges between the same pair of nodes cause duplicate work (the same neighbor gets examined twice) but not incorrectness, if the visited set is checked correctly.
• Pitfall: isolated nodes (no edges at all) are invisible if the traversal only iterates over nodes reachable from a starting adjacency list; they must be included by iterating the full node set, not just the edges.
• Fix: ignore self-loops when expanding neighbors, deduplicate a node's adjacency entries or rely on a visited set to absorb duplicates from parallel edges, and iterate the complete node set (not just nodes that appear in some edge) so isolated nodes are still reported.

Dijkstra's algorithm.

• Pitfall: negative edge weights break Dijkstra's correctness proof outright (it can commit to a shortest distance for a node before a cheaper path through a negative edge is discovered); a self-loop with a negative weight is a degenerate case of the same problem, an infinitely improvable "path."
• Pitfall: parallel edges with different weights, if not collapsed to the minimum, cause the algorithm to needlessly relax the more expensive one.
• Fix: validate no negative weights at ingestion (reject the input, or route to Bellman-Ford instead if negative weights are legitimate); collapse parallel edges to the minimum weight before running; ignore or explicitly reject positive-weight self-loops (they can never improve a shortest path so are safe to drop, but a negative-weight self-loop must be rejected, not silently dropped, since it signals corrupt input).

Union-Find (disjoint set).

• Pitfall: repeated union calls on the same pair (from parallel edges, or a self-loop passed as union(x, x)) are not incorrect, but they are wasted work at scale if the caller does not short-circuit them.
• Pitfall: multi-labeled nodes that were not canonicalized to one id will be unioned as though they were two separate elements, silently splitting what should be one connected component into two.
• Fix: canonicalize labels to ids before any union call; skip a union when find(a) == find(b) already (this is also just good practice for path compression); with path compression and union by rank, redundant unions from parallel edges cost only a few extra find calls, not a correctness problem.

Topological sort.

• Pitfall: a self-loop or any cycle makes a valid topological order impossible to produce, and an implementation that does not check for this can either infinite-loop or silently return a partial, wrong order.
• Pitfall: parallel edges inflate a node's in-degree count in Kahn's algorithm; if the algorithm decrements in-degree once per edge (correct) but the caller expected in-degree to reflect the number of DISTINCT predecessors (a different definition), results diverge from expectations even though the algorithm itself is correct.
• Fix: run cycle detection first (or let Kahn's algorithm detect it implicitly: if fewer than $V$ nodes are output, a cycle exists) and fail with a clear error naming the graph as invalid rather than returning a partial order silently; be explicit about which in-degree definition (edge count vs. distinct-predecessor count) the implementation uses.

Worked example

A small ingestion pipeline for a dependency graph: raw edges arrive as [(A,B), (A,B), (B,B), (B,C), (D,D)], where node A has two labels ("A" and "A_alias") elsewhere in the source data.

Canonicalization step: map "A_alias" -> "A". Then classify: (A,B) appears twice (parallel edge, policy: collapse), (B,B) and (D,D) are self-loops (policy: drop for BFS/DFS/topo-sort; reject if these were meant to carry negative Dijkstra weights), (B,C) is a normal edge, and D otherwise has no other edges (it is effectively isolated once its self-loop is dropped, so it must still appear in the node set with an empty adjacency list).

After sanitization, the canonical graph is: nodes {A, B, C, D}, edges {A->B, B->C}, D isolated. A topological sort on this is well-defined: A, B, C, D (D can appear anywhere, it has no dependencies). Running the same sort on the RAW, unsanitized edge list would either double-process the A->B edge (wasted, not wrong) or, worse, if (B,B) were left in, a naive cycle-unaware implementation could report the whole graph as cyclic when it is not, since the self-loop alone is technically a cycle even though it does not affect ordering between A, B, C, D.

Trade-offs and pitfalls

• Fail fast and specifically: a Dijkstra call that silently ignores a negative edge weight instead of rejecting the input produces a confidently wrong shortest-path answer, which is worse than an error, since nothing downstream will notice.
• Make the collapse-vs-keep-parallel-edges policy configurable rather than hardcoded, since the correct choice depends on what the edges represent (multiple communication channels between two services are meaningfully different from a single duplicated log entry).
• Add tests that specifically exercise self-loops, parallel edges, isolated nodes, and multi-label collisions; these are exactly the inputs that a generated test graph (typically simple, well-formed, connected) will never happen to include on its own, so they need to be constructed deliberately.
• Log sanitization metrics (how many labels were merged, how many parallel edges were collapsed, how many self-loops were dropped) so a spike in any of them signals an upstream data quality problem rather than silently degrading algorithm output.

Direct answer

Kahn's algorithm computes a topological order of a directed acyclic graph (DAG) by repeatedly removing vertices whose in-degree (count of incoming edges) is currently zero: track in-degree for every vertex, seed a queue with the zero-in-degree vertices, and each time one is popped and appended to the output, decrement its neighbors' in-degrees, enqueueing any that just hit zero. If fewer vertices end up in the output than exist in the graph, a cycle is blocking the rest from ever reaching in-degree zero, and the function returns None.

Structured elaboration

The implementation below assumes graph is a complete adjacency map: every vertex, including pure sinks with no outgoing edges, has an entry (possibly an empty list). This matters because in-degree needs to be initialized to 0 for every vertex up front, including ones that never appear as a source in an edge.

Worked example

from collections import deque
from typing import Dict, List, Optional

def topological_sort(graph: Dict[int, List[int]]) -> Optional[List[int]]:
    # Kahn's algorithm. graph maps every node id (including sinks) to its
    # list of out-neighbors. Returns one valid topological order, or None if
    # the graph contains a cycle.
    indegree = {u: 0 for u in graph}
    for u in graph:
        for v in graph[u]:
            indegree[v] += 1

    q = deque([u for u in graph if indegree[u] == 0])
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in graph[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                q.append(v)

    if len(order) != len(graph):
        return None  # some node's indegree never hit 0: a cycle is holding it back
    return order

if __name__ == "__main__":
    dag = {0: [1, 2], 1: [3], 2: [3], 3: [4], 4: []}
    result = topological_sort(dict(dag))
    print("DAG order:", result)

    cyclic = {0: [1, 2], 1: [3], 2: [3], 3: [4], 4: [1]}  # 1 -> 3 -> 4 -> 1
    result_cyclic = topological_sort(dict(cyclic))
    print("Cyclic graph result:", result_cyclic)

    def is_valid_topo(order, graph):
        pos = {n: i for i, n in enumerate(order)}
        return all(pos[u] < pos[v] for u in graph for v in graph[u])
    print("DAG order is valid:", is_valid_topo(result, dag))

Output (actually executed with python3):

DAG order: [0, 1, 2, 3, 4]
Cyclic graph result: None
DAG order is valid: True

How cycle detection works. Every vertex on a cycle has at least one incoming edge from within that same cycle, so its in-degree can only reach zero if something outside the cycle first breaks the dependency, which never happens for a pure cycle. The example above adds edge 4 -> 1 to the acyclic graph, creating the cycle 1 -> 3 -> 4 -> 1. Tracing it: vertex 0 has in-degree 0 and is popped first, dropping vertex 2's in-degree to 0 (vertex 2 is not on the cycle); vertex 2 is popped next, but the one edge it contributes (2 -> 3) only drops vertex 3's in-degree from 2 to 1, not to 0, because 3 is still waiting on vertex 1, which is still waiting on vertex 4, which is still waiting on vertex 1. The queue empties with only [0, 2] ever output, two vertices short of the graph's five, and the length check correctly returns None instead of a partial, misleading order.

Complexity

Time $O(V+E)$: every vertex is enqueued and dequeued exactly once, and every edge is inspected exactly once when decrementing its target's in-degree. Space $O(V)$ for the in-degree map and the queue, on top of the $O(V+E)$ already used to store the adjacency list itself.

Edge cases

• Empty graph: graph = {} returns [] immediately, since the length check 0 == 0 passes trivially.
• Self-loop (graph = {0: [0]}): vertex 0's in-degree is 1 from the start (its own edge), so it never enters the queue, and the function correctly returns None, since a self-loop is a one-vertex cycle.
• Disconnected components: each component's own zero-in-degree vertices seed the queue independently; the algorithm does not require a single connected structure, and the final order simply interleaves both components in whatever sequence the queue happens to drain them.
• Multiple valid orders: whenever two or more vertices are simultaneously in-degree zero, their relative order in the output depends on queue insertion order, which is not part of the contract of "a" valid topological order (any of them is correct).

Trade-offs and pitfalls

• Determinism. As written, this function's exact output can depend on Python's dict/list iteration order for graph, which is consistent for identical input but not necessarily portable across a re-implementation in another language. If a caller needs a reproducible, cross-implementation-stable order (for example, for a golden test fixture or an audit log), swap the FIFO deque for a min-heap keyed on vertex id, which forces the lexicographically smallest valid order every time; that variant is common enough to be its own interview question.
• Deployment-ordering framing: the same function, with vertices renamed to services and edges to "must deploy before," is exactly a safe deployment-order computation; the only change needed is deciding what to do with the None case in production (reject the deployment plan and surface the offending services, rather than silently deploying a partial, broken order).
• Machine learning (ML) use-case framing: the same function orders a feature-store's dependency graph so a derived feature is only computed after every feature it reads from; None there means a circular feature definition, a configuration bug worth failing loudly on rather than silently truncating.
• Common mistake: initializing indegree only from vertices that appear as an edge's source, which silently omits pure-sink vertices and can undercount, or skip, legitimate zero-in-degree starting points; the dict comprehension {u: 0 for u in graph} above avoids this by seeding every vertex the caller declared, not just ones seen as an edge source.
• Common mistake: mutating the caller's graph dict in place while consuming it (for example, popping neighbor lists as they are processed); the implementation above only reads graph, never writes to it, so the caller's structure is safe to reuse afterward.

Direct answer

Kruskal's algorithm builds a minimum spanning tree (MST) by sorting all edges by weight ascending, then greedily adding each edge to the MST as long as it does not create a cycle with edges already added, using Union-Find to detect cycles in near-constant time per check. The algorithm stops once $n-1$ edges have been added (a spanning tree on $n$ nodes always has exactly $n-1$ edges), and total runtime is dominated by the sort: $O(E \log E)$, with the Union-Find operations contributing an additional $O(E \cdot \alpha(n))$, which is asymptotically dominated by the sort.

Structured elaboration

Why greedy-by-weight, skip-cycles is correct. This is the cut property in action: for any partition of the nodes into two non-empty sets, the minimum-weight edge crossing that partition must belong to SOME minimum spanning tree. Processing edges in ascending weight order and adding each one that does not close a cycle is exactly equivalent to repeatedly picking the lightest crossing edge for whatever partition the current partial MST implicitly defines (the current set of already-connected components on one "side," everything else on the other), which is why the greedy approach provably produces a GLOBALLY minimum tree, not just a locally reasonable one.

Role of Union-Find. Two nodes already in the same Union-Find set means a path already connects them using edges already accepted into the MST; adding another edge between them would necessarily create a cycle. Checking find(u) != find(v) before accepting an edge is an $O(\alpha(n))$ amortized cycle check, far cheaper than an explicit DFS/BFS cycle check per candidate edge, which is what makes Kruskal's practical at scale.

Sorting complexity dominates. Sorting $E$ edges is $O(E \log E)$. Since $E \le V^2$ for a simple graph (and typically $E = O(V)$ for sparse graphs common in practice), $O(E \log E)$ is also frequently written as $O(E \log V)$ (because $\log(V^2) = 2\log V$, a constant factor difference). The Union-Find operations across all $E$ edges cost $O(E \cdot \alpha(n))$, which is asymptotically smaller than the sort, so the sort is the bottleneck: Kruskal's overall complexity is $O(E \log E)$.

Worked example

from typing import List, Tuple

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

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

    def union(self, x, y) -> bool:
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        return True

def kruskal(n: int, edges: List[Tuple[int, int, int]]) -> List[Tuple[int, int, int]]:
    dsu = DSU(n)
    mst = []
    for u, v, w in sorted(edges, key=lambda e: e[2]):
        if dsu.union(u, v):
            mst.append((u, v, w))
            if len(mst) == n - 1:
                break
    return mst

if __name__ == "__main__":
    n = 6
    edges = [
        (0, 1, 4), (0, 2, 4), (1, 2, 2),
        (2, 3, 3), (2, 5, 2), (2, 4, 4), (3, 4, 3), (5, 4, 3), (5, 3, 1)
    ]
    mst = kruskal(n, edges)
    total_weight = sum(w for _, _, w in mst)
    print("MST edges:", mst)
    print("total weight:", total_weight)
    print("edge count:", len(mst), "(expected n-1 =", n - 1, ")")

Output:

MST edges: [(5, 3, 1), (1, 2, 2), (2, 5, 2), (3, 4, 3), (0, 1, 4)]
total weight: 12
edge count: 5 (expected n-1 = 5 )

Trace by hand: edges sorted by weight are (5,3,1), (1,2,2), (2,5,2), (2,3,3), (3,4,3), (5,4,3), (0,1,4), (0,2,4), (2,4,4). Processing in that order: (5,3,1) accepted (new edge, new component {5,3}). (1,2,2) accepted ({1,2}). (2,5,2) accepted, merging {1,2} and {5,3} into {1,2,5,3}. (2,3,3) rejected, 2 and 3 are already in the same component. (3,4,3) accepted ({1,2,5,3,4}). (5,4,3) rejected, same component already. (0,1,4) accepted, merging in node 0, now 5 edges total, stop. Sum: $1+2+2+3+4=12$, matching the printed output exactly.

Trade-offs and pitfalls

• Common mistake: forgetting the early-stop condition. Once $n-1$ edges are accepted, the MST is complete and any further edges are guaranteed to create a cycle if added; continuing to scan the remaining sorted edges (which Union-Find would correctly reject anyway) wastes work, though it does not produce a WRONG answer, only a slower one on a graph where $E \gg V$.
• Kruskal's requires the graph to be CONNECTED to produce a true spanning tree. On a disconnected graph, the algorithm terminates having accepted fewer than $n-1$ edges (once no more cycle-free edges remain to add), producing a minimum spanning FOREST, one tree per connected component, rather than a single tree; a correct implementation should check len(mst) == n - 1 at the end and treat a shortfall as a signal the graph was disconnected, not silently return a forest labeled as a tree.
• Common mistake: implementing the cycle check with a slower structure (a plain visited-array BFS/DFS per candidate edge, $O(V+E)$ each) instead of Union-Find, which turns an $O(E \log E)$ algorithm into something closer to $O(E \cdot (V+E))$ in the worst case, since every one of the $E$ edges could require a full traversal to check.
• Kruskal's is a better fit than Prim's when the edge list is already available and sorting is cheap relative to the graph's density (sparse graphs); Prim's, which grows a single tree outward using a priority queue keyed on the CHEAPEST edge crossing the current tree's boundary, tends to be preferred on dense graphs where an adjacency-matrix-backed Prim's can run in $O(V^2)$ without ever needing to sort the full edge list.

Direct answer

$V-1$ relaxation passes suffice because the longest a SIMPLE (non-vertex-repeating) shortest path can be, on a graph with $V$ vertices, is $V-1$ edges, and each full pass is guaranteed to extend at least one more edge of every such optimal path's correct distance. A $V$-th pass that still finds an improvement is therefore evidence of something a simple path could never produce: a path effectively "longer" than $V-1$ edges is only possible if it revisits a vertex, and revisiting only helps if the revisited loop is net-negative, which is precisely a negative cycle. Worst-case time is $O(V \cdot E)$. At massive scale, exact detection remains $O(VE)$ in the worst case, but its practical cost can be reduced with sampling, source partitioning, and early-termination heuristics that trade some detection latency (not correctness, when applied carefully) for far less work on graphs that are usually cycle-free.

Structured elaboration

Proof that $V-1$ passes suffice. Let $P = (s = p_0, p_1, \dots, p_k = t)$ be a shortest path from $s$ to $t$ with the fewest possible edges among all shortest paths (a simple shortest path; if the graph has no negative cycle reachable from $s$, every shortest path has an equivalent simple representation, since removing any cycle from a path can only decrease or preserve its weight when the cycle is non-negative, and cannot be forced by a negative cycle if none is reachable). Claim: after pass $i$ of relaxation, $\text{dist}[p_i]$ equals $\delta(s, p_i)$, the true shortest distance.

Proof by induction on $i$. Base case $i=0$: $\text{dist}[p_0] = \text{dist}[s] = 0 = \delta(s,s)$ from initialization, before any pass runs.

Inductive step: assume $\text{dist}[p_{i-1}] = \delta(s, p_{i-1})$ holds after pass $i-1$. Pass $i$ relaxes every edge of the graph, in particular the edge $(p_{i-1}, p_i)$ (since edges are relaxed regardless of order within a pass, every edge gets its chance during every pass). Relaxing that edge sets $\text{dist}[p_i] \le \text{dist}[p_{i-1}] + w(p_{i-1}, p_i) = \delta(s,p_{i-1}) + w(p_{i-1},p_i) = \delta(s,p_i)$, using that $P$ is a shortest path, so its prefix to $p_i$ is also shortest (a standard property of shortest paths: sub-paths of shortest paths are themselves shortest). Since $\text{dist}$ can never fall below the true distance (relaxation only ever assigns achievable path costs), $\text{dist}[p_i] = \delta(s,p_i)$ after pass $i$, completing the induction.

Since $P$ has $k \le V-1$ edges, $\text{dist}[t] = \text{dist}[p_k] = \delta(s,t)$ is guaranteed correct after at most $V-1$ passes, for every $t$ simultaneously (the same argument applies to every vertex's own shortest simple path independently).

Proof that an extra pass exposes a negative cycle. If no negative cycle is reachable from $s$, every vertex's shortest distance is achieved by SOME simple path (of length $\le V-1$), by the argument above, so a $V$-th pass finds nothing left to improve: every $\text{dist}$ value is already correct and stable. Conversely, if a negative cycle $C$ is reachable from $s$, then for any vertex $t$ on $C$, one can construct paths from $s$ to $t$ of arbitrarily low cost by looping $C$ additional times before finally reaching $t$ (each loop subtracts $|w(C)| > 0$ from the total). No finite value of $\text{dist}[t]$ can be a true shortest distance (there is no minimum; the infimum is $-\infty$), so relaxation along $C$'s edges can never stabilize: some edge on or reachable-from $C$ will always still offer an improvement on the $V$-th pass (and every pass thereafter), which is exactly the extra pass's detection signal.

Worst-case complexity. $O(V \cdot E)$: up to $V-1$ passes (no early exit possible when a genuine negative cycle exists, since some edge always still improves), each inspecting all $E$ edges once, plus the fixed-cost detection pass.

Worked example

A 5-node graph: $0\to1$ (weight 1), then a cycle $1\to2\to3\to4\to1$ with weights $-1,-1,-1,2$, summing to $-1$ (negative).

Tracing distance to node 1 across passes, verified by actually running the algorithm rather than
hand-waving the per-pass numbers (edges relax in insertion order 0,1,2,3,4 within each pass, which matters: it
lets a single pass's updates cascade further around the cycle than a naive "one edge per pass" intuition would
suggest):

def bellman_ford_traced(graph, source):
    dist = {u: float("inf") for u in graph}
    pred = {u: None for u in graph}
    dist[source] = 0
    V = len(graph)
    trace = []
    for p in range(V - 1):
        changed = False
        for u in graph:
            if dist[u] == float("inf"):
                continue
            for v, w in graph[u]:
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
                    pred[v] = u
                    changed = True
        trace.append(dict(dist))
        if not changed:
            break
    culprit = None
    for u in graph:
        if dist[u] == float("inf"):
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                culprit = v
                break
        if culprit is not None:
            break
    return trace, culprit is not None

g = {0: [(1, 1)], 1: [(2, -1)], 2: [(3, -1)], 3: [(4, -1)], 4: [(1, 2)]}
trace, has_cycle = bellman_ford_traced(g, 0)
for i, d in enumerate(trace, 1):
    print(f"after pass {i}: dist[1]={d[1]}")
print("negative cycle detected on the extra pass:", has_cycle)

Output (actually executed with python3):

after pass 1: dist[1]=0
after pass 2: dist[1]=-1
after pass 3: dist[1]=-2
after pass 4: dist[1]=-3
negative cycle detected on the extra pass: True

dist[1] reaches 0, not 1, after pass 1: because edges are relaxed in the fixed order 0,1,2,3,4 within a single
pass, pass 1 already walks all the way around the cycle once (0->1 sets dist[1]=1, then 1->2, 2->3, 3->4 propagate
forward, then 4->1 closes the loop and pulls dist[1] back down to 0 within that SAME pass). From pass 2 onward
each additional pass subtracts another 1 as the cycle's net -1 keeps being re-applied, and the extra (5th) pass
still finds an edge to relax, correctly flagging a negative cycle. This is the actual, executed behavior on this
graph, not an estimate: a hand trace that assumes exactly one edge's worth of progress per pass (as an earlier
draft of this answer did) undercounts how far a single pass can propagate when the edge-processing order happens
to align with the cycle's direction, though the qualitative conclusion, distances keep decreasing without bound
and the extra pass detects it, is unaffected by that undercounting.

Trade-offs and pitfalls

• Scaling negative-cycle detection for massive graphs with limited memory.
  1. Source partitioning. Bellman-Ford as described detects cycles reachable from ONE source. For massive graphs, run it from a small set of strategically chosen sources (for example, one per connected component, or per known high-fan-out hub) rather than from every vertex; this trades completeness (a cycle unreachable from any chosen source is missed) for a large constant-factor reduction in total work, which is often an acceptable trade when the goal is "catch cycles that would actually affect real traffic," not "prove the whole graph is cycle-free."
  2. Sampling. On a graph believed to be usually well-formed (cycles are rare bugs, not expected structure, such as a dependency graph or a currency-arbitrage graph most of the time), running full detection on a random subset of edges' surrounding neighborhoods each cycle, rather than the whole graph every time, catches cycles probabilistically over repeated runs while bounding per-run cost; this is a monitoring posture (catch it eventually, cheaply, repeatedly) rather than a one-shot correctness guarantee.
  3. Early-termination heuristics. The standard if not changed: break optimization terminates the moment a pass makes no improvement, which is the common case on real, cycle-free graphs; combined with tracking only the SUBSET of vertices whose distance changed on the previous pass (rather than re-scanning all $E$ edges every pass, an optimization sometimes called SPFA, shortest path faster algorithm), this reduces typical-case work substantially, though the worst-case $O(VE)$ bound remains for adversarial or genuinely cyclic input.
  4. Streaming/partitioned memory strategies. For a graph too large to hold in memory at once, partition vertices across machines and run Bellman-Ford's edge-relaxation passes as a distributed message-passing computation (each partition relaxes its local edges and forwards updated distances for cross-partition edges), a pattern that maps naturally onto systems like Pregel-style graph processing frameworks; this changes the constant factors and adds network cost per pass but preserves the same pass-count guarantee.
• Common mistake: assuming sampling or source-partitioning give the same GUARANTEE as full Bellman-Ford. They trade a hard correctness guarantee for a probabilistic or scoped one; a system that needs a hard guarantee (rejecting a deployment plan, for example) should not silently swap in a sampled check without making that trade-off explicit to whoever consumes the result.
• Common mistake: conflating "no negative cycle found by my source-limited or sampled check" with "no negative cycle exists in the graph." These heuristics reduce false negatives' PROBABILITY, they do not eliminate the possibility, and reporting them with the same confidence as a full run misrepresents what was actually verified.