Graphs and Graph Algorithms Questions

Direct answer

is_bipartite(graph) runs a BFS two-coloring pass from every not-yet-colored node (handling disconnected input), assigning each newly discovered node the opposite color of the node that discovered it, and returns False the instant an edge connects two nodes already colored the same. If the BFS completes with no such conflict, the graph is bipartite and the accumulated coloring is a valid 2-coloring, returned alongside True.

Structured elaboration

Why BFS coloring works. In a bipartite graph, every edge must connect the two groups, never two nodes within the same group, so any correct 2-coloring must alternate colors across every edge. BFS naturally colors nodes by their distance parity from the component's start node (all nodes at even distance get one color, all nodes at odd distance get the other), and this is EXACTLY a valid bipartition whenever one exists, because two nodes connected by a direct edge always differ in BFS distance by exactly 1 in a correctly-behaving coloring, guaranteeing opposite colors. A conflict (an edge whose endpoints end up the same color) can only arise when the graph structure forces two nodes at the same distance-parity from the start to also be directly connected, which happens precisely when an odd-length cycle exists.

Handling disconnection. Nodes with no path to the component the algorithm happened to start with have no BFS-derived color yet; the outer loop over every node index ensures each such component gets its OWN independent coloring pass, since disconnected components impose no constraint on each other's color choice.

Complexity. $O(V+E)$: every node is colored exactly once, and every edge is examined at most twice (once from each endpoint) across the whole run, the same bound as any BFS/DFS traversal over the full graph.

Worked example

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

def is_bipartite(graph: List[List[int]]) -> Tuple[bool, Optional[List[int]]]:
    n = len(graph)
    color = [-1] * n
    for start in range(n):
        if color[start] != -1:
            continue
        color[start] = 0
        q = deque([start])
        while q:
            u = q.popleft()
            for v in graph[u]:
                if color[v] == -1:
                    color[v] = 1 - color[u]
                    q.append(v)
                elif color[v] == color[u]:
                    return False, None
    return True, color

if __name__ == "__main__":
    # Case 1: bipartite (square, 0-1-2-3-0)
    graph1 = [[1, 3], [0, 2], [1, 3], [2, 0]]
    ok1, coloring1 = is_bipartite(graph1)
    print("graph1:", graph1)
    print("is_bipartite:", ok1, "coloring:", coloring1)

    # Case 2: NOT bipartite (triangle, 0-1-2-0)
    graph2 = [[1, 2], [0, 2], [0, 1]]
    ok2, coloring2 = is_bipartite(graph2)
    print("\ngraph2:", graph2)
    print("is_bipartite:", ok2, "coloring:", coloring2)

    # Case 3: disconnected, mix of a bipartite path and an isolated node
    graph3 = [[1], [0, 2], [1], []]
    ok3, coloring3 = is_bipartite(graph3)
    print("\ngraph3:", graph3)
    print("is_bipartite:", ok3, "coloring:", coloring3)

Output:

graph1: [[1, 3], [0, 2], [1, 3], [2, 0]]
is_bipartite: True coloring: [0, 1, 0, 1]

graph2: [[1, 2], [0, 2], [0, 1]]
is_bipartite: False coloring: None

graph3: [[1], [0, 2], [1], []]
is_bipartite: True coloring: [0, 1, 0, 0]

Graph 1 (a 4-node cycle) two-colors cleanly ([0,1,0,1], alternating perfectly around the cycle). Graph 2 (a 3-node cycle, a triangle, the smallest possible odd cycle) fails, correctly returning None for the coloring rather than a partial or misleading result. Graph 3 (a disconnected graph: a 3-node bipartite path 0-1-2 plus an isolated node 3) succeeds, and node 3, having no edges, keeps whatever color the outer loop happens to assign it (color 0 here, since it starts its own trivial single-node component); an isolated node can never itself cause a conflict, since it has no edges to check.

Trade-offs and pitfalls

• Common mistake: returning False but still returning a PARTIAL, invalid coloring array instead of None (or otherwise clearly signaling invalidity). A caller that does not carefully check the boolean first could mistake a partial, contradiction-containing coloring for a genuine 2-coloring; returning None for the coloring on the False path makes this class of bug impossible rather than merely unlikely.
• Common mistake: only starting BFS once, from node 0. On a graph with disconnected components, this leaves later components entirely uncolored and unchecked; the fix is looping the outer for start in range(n) over every node, which this implementation does correctly.
• An isolated node is trivially bipartite on its own (it has no edges to violate the bipartition condition), and this implementation handles it for free: it becomes its own singleton component, gets colored, and the while-loop body (which only runs on an edge) never executes for it.
• This early-returns on the FIRST conflict found, which is efficient (no wasted work continuing to color a graph already known non-bipartite) but means the specific coloring state at the moment of the return is an implementation artifact of traversal order, not something a caller should read any meaning into beyond "a conflict exists somewhere."

Direct answer

Detect circular service dependencies automatically by building a directed graph from the same manifests that already declare "A depends on B" (Kubernetes manifests, Helm charts, Terraform modules, or an internal service registry), running a linear-time cycle-detection pass (depth-first search, DFS, with the standard white/gray/black coloring, or Tarjan's strongly connected components (SCC) algorithm if a richer diagnostic is wanted) over that graph, and blocking the merge in continuous integration (CI) the moment a cycle is found, before the change that introduces it ever reaches a running environment.

Structured elaboration

Which algorithm to run. A plain DFS-based cycle check (white/gray/black coloring, detecting a back edge into a still-gray node) is sufficient to answer yes/no and, with parent tracking, to reconstruct the specific offending cycle; it runs in $O(V+E)$ and is the simplest correct tool for the job. Tarjan's SCC algorithm, also $O(V+E)$, is a genuinely richer diagnostic: it partitions the ENTIRE graph into strongly connected components in one pass, so if multiple independent cycles exist simultaneously (plausible in a large, poorly-audited dependency graph), Tarjan's reports every one of them at once, each as its own component, rather than requiring the simple DFS check to be re-run repeatedly after each cycle is manually removed. For a one-shot pre-merge gate answering "is THIS specific change introducing a cycle," plain DFS is enough; for a periodic full-repository audit surfacing every existing tangle for cleanup, Tarjan's SCC output is more actionable.

Constructing the dependency graph from manifests. The graph's nodes are services (or components, or modules, whatever the deployable unit is); edges are extracted by parsing each manifest type for its own dependency-declaration convention:

• Kubernetes manifests: a Deployment referencing another service's Service endpoint (via an environment variable, a ConfigMap/Secret reference, or an initContainer that waits on another service) is a dependency edge.
• Helm charts: a chart's values.yaml or Chart.yaml referencing a subchart or another chart's release is a dependency edge.
• Terraform: an explicit depends_on block, or an implicit dependency inferred from one module referencing another module's output, is a dependency edge.
• Application-level manifests: an explicit services: [auth, db]-style declared dependency list, where the application itself states what it needs running first, is the most direct and least ambiguous source, when it exists.

Every source normalizes to the same output shape: a plain edge list (or adjacency map) keyed by a canonical service identifier (cluster + namespace + service name, to avoid two same-named services in different namespaces being conflated into one node), which the cycle-detection algorithm then consumes uniformly regardless of which manifest type originally declared the edge.

Where to integrate the check. As a mandatory, blocking step in the pull-request (PR) merge pipeline: parse every changed manifest in the PR (plus enough of the surrounding, UNCHANGED graph to know what those changed pieces connect to), run cycle detection, and fail the CI check with the SPECIFIC cycle's node path if one is found, before the PR is mergeable at all. This is deliberately a pre-merge gate, not a post-deploy alarm, because the whole point is preventing a circular dependency from ever reaching a state where it could cause a deployment-ordering deadlock (an on-call engineer discovering two services each waiting on the other to become healthy first). A secondary, non-blocking NIGHTLY full-repository scan is worth running in addition, specifically to catch a cycle introduced indirectly (two independently-merged, individually-cycle-free PRs whose combination creates a cycle neither PR's own incremental check would have seen in isolation, since each PR's incremental check only sees its own diff against the graph as it existed at merge time).

Scaling for large repos and many services. Three concrete techniques, layered:

1. Incremental, diff-scoped checking on the PR path. Re-parsing and re-checking the ENTIRE dependency graph on every PR does not scale as the service count grows into the thousands; instead, parse only the changed manifests, resolve which existing nodes their new or modified edges touch, and run cycle detection on the union of "changed nodes plus their existing neighbors," which is sufficient to catch any NEW cycle the PR could introduce, since a cycle must pass through at least one changed edge to be new.
2. Cache the parsed graph, invalidated by manifest changes. Rebuilding the whole graph from every manifest in the repository on every check is wasteful when the vast majority of manifests are unchanged between runs; a persisted graph snapshot, updated incrementally as manifests change (keyed by manifest content hash, so an unchanged file is never re-parsed), keeps the common-case check fast regardless of total repository size.
3. Run the check as a small, containerized job reading a repository-metadata export, not as a step that re-clones and re-parses the entire monorepo from scratch inside the CI runner; separating "extract the manifest snapshot" from "run graph analysis on it" lets the analysis step scale independently and be reused by both the PR-scoped fast path and the nightly full-repository scan.

Worked example

A PR modifies service-payments's manifest to add a dependency on service-notifications. The incremental check resolves the existing graph neighborhood: service-notifications already depends on service-audit, which already depends on service-payments (declared in a completely different, unrelated PR merged months earlier). Adding the new edge service-payments -> service-notifications closes the cycle service-payments -> service-notifications -> service-audit -> service-payments. Because the check resolves not just the changed manifest but its existing neighbors, it catches this even though neither service-notifications's nor service-audit's manifests were touched by this PR at all; a check that only validated the PR's own changed files in isolation, without pulling in their existing graph context, would have missed this cycle entirely.

Trade-offs and pitfalls

• Common mistake: checking only the files changed in the PR without resolving what they connect to in the EXISTING graph, which misses exactly the cross-PR cycle shown in the worked example above; the check's scope needs to be "changed edges plus their existing graph neighborhood," not merely "changed files."
• Common mistake: running the check only as a nightly batch job and not as a blocking PR gate. A nightly-only check still lets a cycle merge and potentially deploy before the next scheduled scan catches it, turning a preventable, cheap-to-block-at-merge-time problem into a reactive incident.
• False negatives from incomplete manifest parsing. If the extraction logic misses a real dependency-declaration convention (a newer Helm pattern, a nonstandard annotation used by one team), the graph is silently incomplete, and cycle detection cannot catch a cycle formed through an edge it never saw. Treating the extraction step's coverage itself as something to monitor (what fraction of known dependency-declaration patterns does the parser recognize, and is that fraction tracked over time) is a real, ongoing maintenance cost, not a one-time build.
• Reporting quality matters as much as detection. A CI failure that says "cycle detected" with no further detail sends an engineer hunting through possibly dozens of services; surfacing the SPECIFIC cycle path (as DFS with parent tracking, or Tarjan's SCC membership, both directly support) turns a vague failure into an actionable one, and should be treated as a hard requirement of the check, not a nice-to-have.
• Human-friendly output in the PR itself (an inline comment on the specific manifest line that introduced the offending edge, via the CI platform's checks/comments API) meaningfully shortens the time to fix versus a failure that only points at a build log an engineer has to go dig through separately.

Direct answer

A tree is a special case of a graph: connected, acyclic, and with exactly $n-1$ edges for $n$ nodes. Those three properties are not independent facts to memorize separately, any two of them imply the third for a graph on $n$ nodes (connected and acyclic implies exactly $n-1$ edges; connected with $n-1$ edges implies acyclic; acyclic with $n-1$ edges implies connected). The single most useful consequence is that a tree has EXACTLY ONE simple path between any two nodes, which is what lets several algorithms drop bookkeeping that a general graph requires.

Structured elaboration

The defining properties.

• Connected: every node is reachable from every other node.
• Acyclic: no sequence of edges returns to a starting node without repeating an edge.
• Exactly $n-1$ edges: the minimum number of edges that can connect $n$ nodes (fewer would leave the graph disconnected), and simultaneously the maximum a connected graph can have before a cycle becomes unavoidable.

Why unique simple paths follow. If two different simple paths existed between the same pair of nodes $u$ and $v$, combining them (going from $u$ to $v$ along one path and back along the other) would trace out a cycle, since the two paths, taken together, revisit $u$ without repeating any single edge twice. This contradicts acyclicity, so at most one simple path can exist; connectivity guarantees at least one exists; together, exactly one.

How this simplifies algorithms. A general graph traversal (breadth-first search (BFS) or depth-first search (DFS)) needs a visited set specifically to avoid two things a tree traversal never has to worry about: re-processing a node reached by more than one route (impossible in a tree, since only one route exists), and looping forever around a cycle (impossible, since there are none). A tree traversal from a chosen root still benefits from tracking "the parent I came from" to avoid immediately walking back the edge just traversed, but that is a much lighter requirement than a full visited set, since it only needs to exclude one specific neighbor (the parent), not remember an arbitrarily large set of everywhere already visited. This is also why tree algorithms can often be written as a clean recursive function of "process this node, then recurse into every neighbor except the parent," with no separate visited-tracking data structure at all.

Worked example

Model as a tree: an organizational reporting hierarchy (each employee has exactly one manager, forming a rooted tree), a filesystem directory structure (each file or folder has exactly one parent directory, ignoring symbolic links), or a binary decision tree used for classification (each internal node has exactly one path down from the root). In each case, "does A report (transitively) to B" or "what is the path from the root to this file" has exactly one answer, and that answer can be found by walking up parent pointers without ever needing to consider an alternative route.

Model as a general graph: a social network (a person can be connected to many others through multiple independent paths, and cycles like mutual-friend triangles are common and meaningful), a service-dependency graph (multiple services may all depend on a shared cache, creating multiple paths between two other services through it), or a road network (there are almost always multiple ways to get from one intersection to another). Forcing any of these into a tree structure would either lose real information (dropping legitimate alternate paths) or require artificially picking one "true" parent per node, discarding the graph's actual shape.

A concrete boundary case worth naming: a graph can look tree-like in casual description ("each task depends on its predecessor") while actually being a directed acyclic graph (DAG), not a tree, the moment a task has more than one direct dependency (two edges pointing INTO the same node). A DAG is still acyclic, but multiple parents mean it is not a tree, and it does not get the "exactly one path between any two nodes" guarantee, a build system's dependency graph is the standard example: a shared library can be a prerequisite for many independent components at once, giving that library multiple incoming edges from unrelated parts of the graph.

Trade-offs and pitfalls

• Common mistake: treating "acyclic" and "tree" as synonyms. A DAG is acyclic but can have nodes with multiple parents (multiple incoming edges), which breaks the unique-simple-path property that trees rely on; algorithms that assume tree structure (a plain parent-pointer walk with no visited set) will double-count or infinite-loop-free-but-redundantly-revisit shared nodes in a DAG, even though the DAG has no cycle to get stuck in.
• Common mistake: assuming "connected with no cycles found so far" is the same as "is a tree," without separately checking the edge count. A connected graph with $n$ nodes and MORE than $n-1$ edges necessarily contains a cycle (by the same counting argument that shows $n-1$ is the connectivity-preserving maximum), so if a traversal reports "no cycle found" on a graph that was never checked for edge count, that traversal may simply not have reached the cycle-forming edge yet, especially in a partial or early-terminated search.
• Real systems often START as trees and DRIFT into general graphs as requirements grow: an initial single-parent category hierarchy in a product catalog is a tree, but the moment a product needs to belong to two categories at once (multiple parents), the structure is a DAG, and any code written assuming a tree (recursive descent with no cycle guard, path-uniqueness assumptions in a breadcrumb trail) needs to be revisited, not just extended.
• When in doubt about which structure a system actually has, the edge-count check is cheap and decisive: count edges, count nodes, and confirm $|E| = |V| - 1$ AND connectivity before relying on any tree-only simplification; skipping this and assuming "it's basically a tree" is a common source of subtle graph-traversal bugs once the data eventually violates the assumption.

Direct answer

Seed a single breadth-first search (BFS) queue with all source nodes at distance 0 simultaneously, rather than running BFS once per source and taking the minimum. Because BFS explores in strict distance order, the first time any node is reached from ANY source is guaranteed to be its true minimum distance to the nearest source, so one pass over every vertex and edge suffices.

Structured elaboration

The key insight is that a standard single-source BFS's correctness argument, the first time a node is dequeued its distance is final, does not depend on there being only one source in the queue at the start. Seeding multiple sources at distance 0 just means the frontier expands outward from several points at once; distances still increase monotonically layer by layer, so a node discovered from source A at distance 3 and also reachable from source B at distance 5 will correctly end up recorded at distance 3, whichever source's expansion reaches it first, since BFS explores layer 3 (from either source) entirely before layer 4.

This avoids the alternative of running BFS once per source and taking an elementwise minimum, which costs $O(k \cdot (V+E))$ for $k$ sources instead of a single $O(V+E)$ pass.

Worked example

from collections import deque
from typing import List

def multi_source_bfs(n: int, edges: List[List[int]], sources: List[int]) -> List[int]:
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    dist = [-1] * n
    q = deque()
    for s in set(sources):
        if 0 <= s < n and dist[s] == -1:
            dist[s] = 0
            q.append(s)

    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

if __name__ == "__main__":
    # n=8 undirected graph: a 6-cycle over nodes 0..5, plus a separate isolated pair 6-7
    n = 8
    edges = [[0,1],[1,2],[2,3],[3,4],[4,5],[0,5],[6,7]]
    sources = [0, 4]

    dist = multi_source_bfs(n, edges, sources)
    print("dist:", dist)

    # verify against brute force: minimum over independent single-source BFS runs
    def bfs_from(src):
        d = [-1]*n
        adj = [[] for _ in range(n)]
        for u,v in edges:
            adj[u].append(v); adj[v].append(u)
        d[src]=0
        qq=deque([src])
        while qq:
            u=qq.popleft()
            for v in adj[u]:
                if d[v]==-1:
                    d[v]=d[u]+1
                    qq.append(v)
        return d
    d0, d4 = bfs_from(0), bfs_from(4)
    expected = [min(a,b) if a!=-1 and b!=-1 else (a if a!=-1 else b) for a,b in zip(d0,d4)]
    print("expected (min of independent single-source runs):", expected)
    print("matches:", dist == expected)
    print("unreachable nodes 6 and 7 both -1:", dist[6]==-1 and dist[7]==-1)

Output (actually executed with python3):

dist: [0, 1, 2, 1, 0, 1, -1, -1]
expected (min of independent single-source runs): [0, 1, 2, 1, 0, 1, -1, -1]
matches: True
unreachable nodes 6 and 7 both -1: True

Complexity

• Time: $O(V + E)$, each vertex is dequeued once and each edge is examined at most twice (once from each endpoint).
• Space: $O(V)$ for the adjacency list construction, the dist array, and the queue.

Edge cases

• No sources given: dist stays all -1, no error, since the for s in set(sources) loop simply does not run.
• A source index outside [0, n): silently ignored via the bounds check, rather than crashing on an out-of-range list access.
• Disconnected components not reachable from any source: correctly left at -1, handled naturally since BFS only expands from the seeded frontier.
• Duplicate sources: deduplicated via set(sources) so a repeated source does not enqueue the same starting node twice.

Trade-offs and pitfalls

• Common mistake: running BFS independently once per source and taking the minimum. This gives the same answer but costs $O(k \cdot (V+E))$ instead of $O(V+E)$, a real difference once $k$ (the number of sources) is large, for example this shape shows up as "distance to nearest fire station," "distance to nearest rotten orange," or "distance to nearest cache node."
• Common mistake: initializing all sources into the queue but forgetting to check dist[v] == -1 before overwriting on relaxation, which would let a later, longer path stomp an earlier, shorter one; the -1 sentinel check is what preserves BFS's "first time reached is shortest" guarantee.
• Extending this to a directed graph only requires building adj from directed edges (drop the reverse insert); the algorithm's correctness argument (layer-by-layer expansion) is unaffected by directedness.
• This does NOT generalize directly to weighted graphs with varying positive weights; that requires a priority queue and becomes multi-source Dijkstra, not multi-source BFS, since BFS's "distance equals number of edges" property depends on every edge costing exactly 1.

Direct answer

Dijkstra's algorithm is correct for non-negative edge weights because, by induction on the order nodes are finalized (popped from the priority queue), every node's tentative distance at the moment it is popped equals its true shortest distance: no unfinalized node could possibly offer a cheaper route, since every unfinalized node's tentative distance is already at least as large, and non-negative weights mean extending a path can only make it longer or equal, never shorter. Once even one edge is negative, that "can only get longer" step fails, and a node can be finalized with a distance that a not-yet-explored, seemingly-farther path later proves too high.

Structured elaboration

Proof by induction on finalization order. Let $u_1, u_2, \dots, u_n$ be the order in which Dijkstra finalizes (pops) nodes from source $s$. Claim: for every $k$, $\text{dist}[u_k]$ at the moment of popping equals $\delta(s, u_k)$, the true shortest-path distance.

Base case: $u_1 = s$, $\text{dist}[s] = 0 = \delta(s,s)$, trivially true.

Inductive step: assume the claim holds for $u_1, \dots, u_{k-1}$. Consider any path $P$ from $s$ to $u_k$. If $P$ only passes through already-finalized nodes before reaching $u_k$, the algorithm has already correctly computed and relaxed along every edge of $P$ (by the inductive hypothesis, each finalized predecessor's distance is exact, and relaxation propagates that exact value forward), so $\text{dist}[u_k] \le \text{weight}(P)$ already holds when $u_k$ is popped. If instead $P$ passes through some unfinalized node $w$ before reaching $u_k$, then because every edge weight is non-negative, the prefix of $P$ up to $w$ already costs at least $\text{dist}[w]$ (by the same relaxation argument), and the remaining suffix from $w$ to $u_k$ costs $\ge 0$, so $\text{weight}(P) \ge \text{dist}[w]$. Since $u_k$ was popped before $w$, the priority queue guarantees $\text{dist}[u_k] \le \text{dist}[w] \le \text{weight}(P)$. Either way, $\text{dist}[u_k] \le \text{weight}(P)$ for every path $P$, so $\text{dist}[u_k] \le \delta(s,u_k)$; and since $\text{dist}[u_k]$ is itself achieved by some real path (built up through relaxation), $\text{dist}[u_k] \ge \delta(s,u_k)$ as well. Hence equality, completing the induction.

Where negative weights break this. The step "the prefix of $P$ up to $w$ already costs at least $\text{dist}[w]$, and the suffix costs $\ge 0$" is exactly where non-negativity is load-bearing. If the suffix from $w$ to $u_k$ can have negative total weight, then $\text{weight}(P)$ can fall below $\text{dist}[w]$, which can fall below $\text{dist}[u_k]$: a path through a currently-farther-looking node $w$ can turn out cheaper than the path already finalized for $u_k$, but the algorithm has no mechanism to revisit $u_k$ once popped.

Worked example

Consider $S \to B$ with weight 1, $S \to A$ with weight 2, and $A \to B$ with weight -5.

The true shortest distance from $S$ to $B$ is $\min(1,\ 2+(-5)) = \min(1, -3) = -3$, via $S \to A \to B$.

Tracing Dijkstra: initialize $\text{dist}=\{S{:}0,A{:}\infty,B{:}\infty\}$, queue $=[(0,S)]$. Pop $(0,S)$, finalize $S$. Relax: $\text{dist}[B]=1$, $\text{dist}[A]=2$; push $(1,B)$ and $(2,A)$. Pop $(1,B)$ (smaller than $(2,A)$), finalize $B$ at distance 1. Pop $(2,A)$, finalize $A$. Relax $A\to B$: candidate $2+(-5)=-3$, strictly less than $\text{dist}[B]=1$, but textbook Dijkstra never revisits an already-finalized node, so this improvement is discarded (or, depending on implementation detail, silently applied to a dist entry that the algorithm has already treated as settled and reported). Either way, the algorithm's committed answer for $B$, 1, is wrong; the true shortest distance is $-3$.

This was verified by executing both a "textbook" Dijkstra (which explicitly refuses to relax into an already-finalized node, exactly matching the proof's assumption) and a brute-force enumeration of both $S\to B$ paths on this exact graph:

import heapq

def textbook_dijkstra(graph, source):
    # Once a node is popped (finalized), never relaxed again, matching
    # the assumption the non-negative-weight correctness proof relies on.
    dist = {u: float('inf') for u in graph}
    dist[source] = 0
    pq = [(0, source)]
    finalized = set()
    order = []
    while pq:
        du, u = heapq.heappop(pq)
        if u in finalized:
            continue
        finalized.add(u)
        order.append((u, du))
        for v, w in graph.get(u, []):
            if v in finalized:
                continue
            nd = du + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist, order

graph = {'S': [('B', 1), ('A', 2)], 'A': [('B', -5)], 'B': []}
dist, order = textbook_dijkstra(graph, 'S')
print("Finalization order (node, distance when finalized):", order)
print("Dijkstra's reported distances:", dist)

def all_paths(graph, u, target, cost, visited, out):
    if u == target:
        out.append(cost)
        return
    for v, w in graph.get(u, []):
        if v not in visited:
            all_paths(graph, v, target, cost + w, visited | {v}, out)

out = []
all_paths(graph, 'S', 'B', 0, {'S'}, out)
true_shortest = min(out)
print("All S->B path costs (brute force):", out, "-> true shortest:", true_shortest)
print("Dijkstra's dist['B'] is wrong:", dist['B'] != true_shortest,
      f"(Dijkstra reported {dist['B']}, true shortest is {true_shortest})")

Output (actually executed with python3):

Finalization order (node, distance when finalized): [('S', 0), ('B', 1), ('A', 2)]
Dijkstra's reported distances: {'S': 0, 'A': 2, 'B': 1}
All S->B path costs (brute force): [1, -3] -> true shortest: -3
Dijkstra's dist['B'] is wrong: True (Dijkstra reported 1, true shortest is -3)

Trade-offs and pitfalls

• The property violated by negative weights is precisely the induction's suffix-cost-is-non-negative step, not some vaguer notion of "the algorithm gets confused." Once suffixes can be negative, a path through a node with a larger CURRENT tentative distance can still beat a path through a node with a smaller one, which directly contradicts the priority queue's "smallest popped next is smallest overall" guarantee that the whole algorithm is built on.
• Common mistake: believing the fix is to relax the already-finalized node anyway (as an unmodified, naive priority-queue implementation without an explicit finalized set might accidentally do, since it just checks if nd < dist[v] without checking whether v was already popped). That happens to fix THIS specific example by coincidence (because $B$ has no outgoing edges to further corrupt), but it is not a general fix: with a longer chain of negative edges reachable from an already-finalized node, one relaxation after finalization is not enough, and the node might need to be reopened and re-propagated through repeatedly, which is exactly what Bellman-Ford's repeated-relaxation structure does correctly and Dijkstra's single-pop-per-node structure cannot.
• The right fix is Bellman-Ford, not a patched Dijkstra: it relaxes every edge up to $V-1$ times, which is enough for the negative information to fully propagate along any simple path, at the cost of $O(VE)$ instead of $O((V+E)\log V)$.
• A weaker, sometimes-useful middle ground: if negative edges exist but the graph is a DAG (directed acyclic graph, no cycles at all, positive or negative), a single topological-order relaxation pass computes correct shortest paths in $O(V+E)$, faster than both Dijkstra and Bellman-Ford, since acyclicity alone (not weight sign) is what that approach depends on.