All-Pairs and Negative Weights

This builds on Shortest Paths, which developed the relaxation primitive and Dijkstra's greedy algorithm for non-negative weights. Dijkstra's whole correctness argument leaned on non-negativity in one place — extending a path never lowers its cost — and one negative edge breaks it. Handling negative weights means abandoning the greedy schedule for dynamic programming, which is where we pick up.

Bellman-Ford as a dynamic program

Dijkstra breaks when edges can be negative — its greedy finalization assumes a finalized estimate can never improve, which negative edges violate. $Bellman-Ford$ trades speed for generality. It is best derived not as relax everything repeatedly but as a genuine dynamic program. That framing is worth keeping, because it explains where the $∣ V ∣ - 1$ comes from.

The subproblem. Bound the number of edges a walk may use. For each vertex $v$ and each budget $k$ , define

OPT (k, v) = cost of a cheapest s ⇝ v walk using at most k edges.

The full answer we want is $OPT (n - 1, v)$ for $n = ∣ V ∣$ , since (as we prove below) shortest paths never need more than $n - 1$ edges.

The recurrence. A cheapest walk to $v$ using at most $k$ edges either uses at most $k - 1$ edges already, or it takes one final edge $(u, v)$ after a cheapest $\leq (k - 1)$ -edge walk to $u$ . Minimizing over both:

OPT (k, v) = min (OPT (k - 1, v), (u, v) \in E min OPT (k - 1, u) + w (u, v)),

with base cases $OPT (0, s) = 0$ and $OPT (0, v) = \infty$ for $v \neq = s$ . This is relaxation in another guise: filling row $k$ of the table from row $k - 1$ is one full pass that relaxes every edge. The tabular form makes the layering explicit, with row $k$ holding the best walk of length $\leq k$ :

Algorithm 3:

\textsc{Bellman-Ford-DP}(G, w, s)

— the explicit DP table

1
$\text{OPT}[0, s] \gets 0$ ; $\text{OPT}[0, v] \gets \infty$ for $v \neq s$
2
for $k \gets 1$ to $n - 1$ do
one pass over all edges per row
3
foreach vertex $v \in V$ do
4
$\text{OPT}[k, v] \gets \text{OPT}[k-1, v]$
inherit: no extra edge
5
foreach edge $(u, v) \in E$ do
6
if $\text{OPT}[k-1, u] + w(u, v) < \text{OPT}[k, v]$ then
7
$\text{OPT}[k, v] \gets \text{OPT}[k-1, u] + w(u, v)$
8
$v.\pi \gets u$
9
return $\text{OPT}[n-1, \cdot]$ and $\pi$

Why stop after $n - 1$ rounds? This is the theorem that licenses the whole algorithm.

So the rows of the DP stop changing by row $n - 1$ .

A second, sharper argument gives the same bound, phrased directly in terms of relaxation.¹ It explains not just that $n - 1$ rounds suffice but which vertices are already correct after each round.

Round $i$ of Bellman-Ford relaxes every edge, in particular the $i$ -th edge of any shortest path you care to name, and it does so after round $i - 1$ handled the $(i - 1)$ -st. So after round $i$ , every vertex whose shortest path uses at most $i$ edges holds its exact distance, and since no shortest path needs more than $n - 1$ edges, $n - 1$ rounds settle every vertex. The correct region grows along every shortest path by at least one edge per round:

Path relaxation along one shortest path

s \to v_{1} \to \dots \to v_{4}

. Round

i

relaxes every edge, in particular edge

i

of this path; each bracket marks the prefix whose estimates are guaranteed exact after that round.

Saving space. The recurrence only ever reads row $k - 1$ , so we collapse the table to a single 1-D array $d [\cdot]$ updated in place, recovering the familiar form of Bellman-Ford as $n - 1$ rounds of relaxing every edge. (In-place updates can only make estimates better than the strict row-by-row schedule; the path-relaxation lemma tolerates the extra interleaved relaxations.) Negative edges are fine; only a negative cycle breaks the theorem.

Algorithm 4:

\textsc{Bellman-Ford}(G, w, s)

— space-saved; with cycle check

1
foreach vertex $v \in V$ do
2
$v.d \gets \infty$
3
$v.\pi \gets \text{nil}$
4
$s.d \gets 0$
5
for $i \gets 1$ to $n - 1$ do
V-1 full-relaxation rounds
6
foreach edge $(u, v) \in E$ do
7
call $\textsc{Relax}(u, v, w)$
8
foreach edge $(u, v) \in E$ do
extra pass: detect neg cycle
9
if $u.d + w(u, v) < v.d$ then
10
return false
neg cycle reachable from s
11
return true

Detecting negative cycles. After $n - 1$ rounds, if any edge can still be relaxed, some walk was improved using $n$ edges — only possible if a negative cycle lets the cost descend without bound. So one extra pass serves as the test: relax everything once more, and any successful relaxation certifies a negative cycle reachable from $s$ (where cheapest cost to reach a vertex is no longer even well-defined).² The extra pass is a decision procedure, and it is both sound and complete: a relaxation can succeed only when a reachable negative cycle exists (soundness, no false alarm), and any such cycle forces some edge to relax on that pass (completeness, none is missed). Dijkstra entirely lacks that capability. The cost is $Θ (V \cdot E)$ : $∣ V ∣ - 1$ passes, each relaxing all $∣ E ∣$ edges.

Laid out as the DP table $OPT [k, v]$ , the layering is plain: row $k$ holds the cheapest walk of at most $k$ edges, each row computed from the one above by a single full pass of relaxation. The entries that improved on each row are shaded; the table stops changing after row $2$ , well within the $n - 1 = 4$ bound:

The Bellman-Ford DP table

OPT [k, v]

for the trace digraph. Row

k

= cheapest

s ⇝ v

walk of

\leq k

edges; shaded cells improved that round. Rows freeze after

k = 2

bellman_ford.pypython

from collections.abc import Hashable
from typing import Generic, NamedTuple, Optional, TypeVar

from graph import Graph

Label = TypeVar("Label", bound=Hashable)

class BellmanFordResult(NamedTuple, Generic[Label]):
  """
    A Bellman-Ford run. `has_negative_cycle` is True when a negative cycle is\n
    reachable from the source, in which case the distances are not meaningful.\n
    Otherwise `distance` and `predecessor` describe the shortest-path tree.\n
  """
  distance: dict[Label, float]
  predecessor: dict[Label, Optional[Label]]
  has_negative_cycle: bool

  def path_to(self, target: Label) -> Optional[list[Label]]:
    """
      The shortest path from the source to `target`, or None if it is\n
      unreachable. Meaningless when `has_negative_cycle` is True.\n
    """
    if self.distance.get(target, float("inf")) == float("inf"):
      return None

    # walk predecessors back from the target to the source, then flip.
    path: list[Label] = []
    cursor: Optional[Label] = target
    while cursor is not None:
      path.append(cursor)
      cursor = self.predecessor[cursor]

    path.reverse()
    return path

def bellman_ford(graph: Graph[Label], source: Label) -> BellmanFordResult[Label]:
  """
    Shortest paths from `source` over a graph that may carry negative edges.\n
    Relaxes every edge V-1 times, then one extra pass: any edge that can\n
    still relax proves a negative cycle is reachable from `source`.\n
  """
  # every estimate starts at infinity except the source at zero.
  distance: dict[Label, float] = {label: float("inf") for label in graph.labels}
  predecessor: dict[Label, Optional[Label]] = {label: None for label in graph.labels}
  distance[source] = 0.0
  vertex_count: int = len(graph)

  # V-1 rounds; each round is one full pass relaxing every edge.
  for _ in range(vertex_count - 1):
    relaxed_any: bool = False
    for edge in graph.edges():
      source_label: Label = edge.source.label
      target_label: Label = edge.target.label
      candidate: float = distance[source_label] + edge.weight

      # a cheaper route to the target improves its estimate this round.
      if candidate < distance[target_label]:
        distance[target_label] = candidate
        predecessor[target_label] = source_label
        relaxed_any = True

    # an early fixpoint means no further round can change anything.
    if not relaxed_any:
      break

  # extra pass: a successful relaxation now can only come from a neg cycle.
  for edge in graph.edges():
    source_label = edge.source.label
    if distance[source_label] + edge.weight < distance[edge.target.label]:
      return BellmanFordResult(distance, predecessor, True)

  return BellmanFordResult(distance, predecessor, False)

dag_shortest_paths.pypython

from collections.abc import Hashable
from typing import Generic, NamedTuple, Optional, TypeVar

from graph import Graph

Label = TypeVar("Label", bound=Hashable)

class DagPaths(NamedTuple, Generic[Label]):
  """
    Shortest-path distances and predecessors from a fixed source on a DAG.\n
  """
  distance: dict[Label, float]
  predecessor: dict[Label, Optional[Label]]

  def path_to(self, target: Label) -> Optional[list[Label]]:
    """
      The shortest path from the source to `target`, or None if unreachable.\n
    """
    if self.distance.get(target, float("inf")) == float("inf"):
      return None

    # walk predecessors back from the target to the source, then flip.
    path: list[Label] = []
    cursor: Optional[Label] = target
    while cursor is not None:
      path.append(cursor)
      cursor = self.predecessor[cursor]

    path.reverse()
    return path

def topological_order(graph: Graph[Label]) -> list[Label]:
  """
    A topological ordering of `graph`'s labels via Kahn's algorithm.\n
    Raises ValueError if the graph contains a directed cycle.\n
  """
  # count incoming edges for every vertex.
  indegree: dict[Label, int] = {label: 0 for label in graph.labels}
  for edge in graph.edges():
    indegree[edge.target.label] += 1

  # seed the queue with every source (indegree zero), in insertion order.
  ready: list[Label] = [label for label in graph.labels if indegree[label] == 0]
  order: list[Label] = []

  while ready:
    current_label: Label = ready.pop()
    order.append(current_label)

    # dropping this vertex may expose new sources among its successors.
    for edge in graph.vertex(current_label).outgoing:
      neighbor_label: Label = edge.target.label
      indegree[neighbor_label] -= 1
      if indegree[neighbor_label] == 0:
        ready.append(neighbor_label)

  # a leftover vertex was never freed, so some cycle trapped it.
  if len(order) != len(graph):
    raise ValueError("graph is not a DAG: a directed cycle was found")
  return order

def dag_shortest_paths(graph: Graph[Label], source: Label) -> DagPaths[Label]:
  """
    Shortest paths from `source` on a directed acyclic `graph`.\n
    Relaxes outgoing edges in one topological sweep; negative edges allowed.\n
  """
  # every estimate starts at infinity except the source at zero.
  distance: dict[Label, float] = {label: float("inf") for label in graph.labels}
  predecessor: dict[Label, Optional[Label]] = {label: None for label in graph.labels}
  distance[source] = 0.0

  for current_label in topological_order(graph):
    # vertices unreachable from the source never relax their successors.
    if distance[current_label] == float("inf"):
      continue

    # one sweep: relax each outgoing edge of the now-finalized vertex.
    for edge in graph.vertex(current_label).outgoing:
      neighbor_label: Label = edge.target.label
      candidate: float = distance[current_label] + edge.weight
      if candidate < distance[neighbor_label]:
        distance[neighbor_label] = candidate
        predecessor[neighbor_label] = current_label

  return DagPaths(distance, predecessor)

graph.pypython

from collections.abc import Hashable, Iterator
from typing import Generic, Optional, TypeVar


Label = TypeVar("Label", bound=Hashable)


class Edge(Generic[Label]):
  """
    A directed connection from `source` to `target`, carrying a weight.\n
  """

  def __init__(
    self,
    source: Vertex[Label],
    target: Vertex[Label],
    weight: float = 1.0,
  ) -> None:
    self.source: Vertex[Label] = source
    self.target: Vertex[Label] = target
    self.weight: float = weight

  def __repr__(self) -> str:
    return f"Edge({self.source.label!r} -> {self.target.label!r}, w={self.weight})"


class Vertex(Generic[Label]):
  """
    A graph vertex: a label plus the list of edges leaving it.\n
  """

  def __init__(self, label: Label) -> None:
    self.label: Label = label
    self.outgoing: list[Edge[Label]] = []

  def neighbors(self) -> list[Vertex[Label]]:
    """
      The vertices reachable from this one by a single edge.\n
    """
    return [edge.target for edge in self.outgoing]

  def edge_to(self, label: Label) -> Optional[Edge[Label]]:
    """
      The outgoing edge to the vertex with `label`, or None.\n
    """
    for edge in self.outgoing:
      if edge.target.label == label:
        return edge
    return None

  def __repr__(self) -> str:
    return f"Vertex({self.label!r})"


class Graph(Generic[Label]):
  """
    A graph of Vertex objects linked by Edge objects.\n
    Pass `directed=True` for a digraph; otherwise each `add_edge` inserts\n
    the reverse edge too.\n
  """

  def __init__(self, directed: bool = False) -> None:
    self.directed: bool = directed
    self._vertices: dict[Label, Vertex[Label]] = {}

  def add_vertex(self, label: Label) -> Vertex[Label]:
    """
      Return the vertex for `label`, creating it if it is absent.\n
    """
    # reuse the existing vertex, or mint and register a fresh one.
    vertex = self._vertices.get(label)
    if vertex is None:
      vertex = Vertex(label)
      self._vertices[label] = vertex
    return vertex

  def add_edge(
    self,
    source_label: Label,
    target_label: Label,
    weight: float = 1.0,
  ) -> None:
    """
      Connect two labels (creating either vertex as needed).\n
      Adds the reverse edge as well when the graph is undirected.\n
    """
    source = self.add_vertex(source_label)
    target = self.add_vertex(target_label)

    # link source to target, and mirror it back when undirected.
    source.outgoing.append(Edge(source, target, weight))
    if not self.directed:
      target.outgoing.append(Edge(target, source, weight))

  def vertex(self, label: Label) -> Vertex[Label]:
    """
      The vertex carrying `label` (raises KeyError if absent).\n
    """
    return self._vertices[label]

  @property
  def vertices(self) -> list[Vertex[Label]]:
    """
      Every vertex, in insertion order.\n
    """
    return list(self._vertices.values())

  @property
  def labels(self) -> list[Label]:
    """
      Every vertex label, in insertion order.\n
    """
    return list(self._vertices)

  def edges(self) -> Iterator[Edge[Label]]:
    """
      Each edge once — an undirected edge is yielded a single time.\n
    """
    # track undirected endpoint pairs so each is emitted only once.
    seen: set[frozenset[Label]] = set()

    for vertex in self._vertices.values():
      for edge in vertex.outgoing:
        # skip an undirected edge already yielded from the other endpoint.
        if not self.directed:
          endpoints = frozenset((edge.source.label, edge.target.label))
          if endpoints in seen:
            continue
          seen.add(endpoints)

        yield edge

  def __contains__(self, label: Label) -> bool:
    return label in self._vertices

  def __iter__(self) -> Iterator[Vertex[Label]]:
    return iter(self._vertices.values())

  def __len__(self) -> int:
    return len(self._vertices)

Floyd-Warshall: all pairs at once

Sometimes we want $δ (u, v)$ for every pair of vertices, a full distance matrix. Running Bellman-Ford from each source costs $O (V^{2} E)$ , up to $Θ (V^{4})$ on dense graphs, but $Floyd-Warshall$ does better with a dynamic program parameterized not by edge count but by which vertices a path is allowed to pass through.

The recurrence lifts $d^{(k - 1)}$ to $d^{(k)}$ by a case split that is exhaustive by construction: a shortest path counted by $d_{ij}^{(k)}$ either uses vertex $k$ as an intermediate or it does not, and there is no third possibility. If it does not, its intermediates already lie in ${1, \dots, k - 1}$ and it is counted by $d_{ij}^{(k - 1)}$ . If it does, then (assuming no negative cycles, we may take the path simple, so $k$ appears exactly once) $k$ splits the path into an $i ⇝ k$ half and a $k ⇝ j$ half, neither of which contains $k$ in its interior. Both halves have intermediates in ${1, \dots, k - 1}$ , and by optimal substructure each half is a shortest path of its own class, so their costs are exactly $d_{ik}^{(k - 1)}$ and $d_{k j}^{(k - 1)}$ . Taking the better case:

d_{ij}^{(k)} = min (d_{ij}^{(k - 1)}, d_{ik}^{(k - 1)} + d_{k j}^{(k - 1)}) .

Why the recurrence is exhaustive. A shortest

i ⇝ j

path with intermediates in

{1, \dots, k}

either avoids

k

entirely — the

d_{ij}^{(k - 1)}

case — or passes through

k

exactly once, splitting into halves

d_{ik}^{(k - 1)} + d_{k j}^{(k - 1)}

whose interiors use only vertices below

k

Induction on $k$ turns this into correctness: $d^{(0)}$ is right by definition, and if $d^{(k - 1)}$ holds every $(k - 1)$ -limited distance, the case split shows the recurrence computes every $k$ -limited one. After round $n$ , no restriction remains.

Consider one round of the recurrence. Starting from $d^{(0)}$ — direct edges only — and admitting intermediates from ${1, 2}$ produces $d^{(2)}$ : the entry $d_{13}$ drops from $8$ to $5$ via $1 \to 2 \to 3$ , and the once-unreachable $d_{42}, d_{43}$ become finite by routing through vertex $1$ then $2$ . The five matrices $d^{(0)}, \dots, d^{(4)}$ below trace one round per permitted intermediate; the entries that improved in each round are shaded:

Floyd-Warshall, one matrix per round.

d^{(k)}

uses only vertices

{1, \dots, k}

as intermediates; each round's pivot vertex

k

is marked in blue on the indices (its row and column drive that round's updates), and the entries that improved when

k

was admitted are shaded.

d^{(4)}

holds the all-pairs shortest distances.

Three nested loops over $k$ , $i$ , $j$ evaluate this recurrence directly: the outer loop admits one intermediate vertex $k$ per round (exactly the five matrices above), and the inner two relax every pair against a route through it.

Algorithm:

\textsc{Floyd-Warshall}(W)

— all-pairs shortest paths in

O(V^3)

1
$d \gets W$
$d_{ij}$ : edge weight; $0$ on the diagonal, else $\infty$
2
for $k \gets 1$ to $n$ do
admit vertex $k$ as an intermediate
3
for $i \gets 1$ to $n$ do
4
for $j \gets 1$ to $n$ do
5
if $d_{ik} + d_{kj} < d_{ij}$ then
routing through $k$ is shorter
6
$d_{ij} \gets d_{ik} + d_{kj}$
7
return $d$

The pseudocode quietly drops the superscripts and updates one matrix in place, and this needs a word of justification: during round $k$ , could an entry $d_{ik}$ or $d_{k j}$ that the recurrence reads have already been overwritten with a round- $k$ value? It could, but harmlessly, because row and column $k$ do not change during round $k$ : $d_{ik}^{(k)} = min (d_{ik}^{(k - 1)}, d_{ik}^{(k - 1)} + d_{k k}^{(k - 1)}) = d_{ik}^{(k - 1)}$ , since $d_{k k} = 0$ (and $\geq 0$ whenever no negative cycle exists). Reading new values is the same as reading old ones, so one $n \times n$ matrix suffices.

Running time. The algebra is the shortest of the lesson: three nested loops of $n$ iterations each, with a constant-time comparison in the body: $n \cdot n \cdot n = Θ (V^{3})$ time and $Θ (V^{2})$ space. No priority queue, no per-edge bookkeeping: compact, cache-friendly, and a clean win on dense graphs.³ It handles negative edges, and a negative entry on the diagonal ( $d_{ii} < 0$ ) flags a negative cycle through $i$ . For sparse graphs with non-negative weights, running Dijkstra from every source costs $O (V E + V^{2} log V)$ , which beats $Θ (V^{3})$ when $E ≪ V^{2}$ ; Floyd-Warshall wins on dense inputs and on any input where its tiny constant factor and trivial implementation matter more than asymptotics.

floyd_warshall.pypython

from collections.abc import Hashable
from typing import Generic, NamedTuple, Optional, TypeVar

from graph import Graph

Label = TypeVar("Label", bound=Hashable)

class AllPairsPaths(NamedTuple, Generic[Label]):
  """
    All-pairs shortest paths. `distance[source][target]` is the cheapest cost\n
    between the pair; `successor[source][target]` is the next vertex on that\n
    path, used to reconstruct it. `has_negative_cycle` flags a negative cycle.\n
  """
  distance: dict[Label, dict[Label, float]]
  successor: dict[Label, dict[Label, Optional[Label]]]
  has_negative_cycle: bool

  def path_between(self, source: Label, target: Label) -> Optional[list[Label]]:
    """
      The shortest path from `source` to `target` as a vertex list, or None\n
      if `target` is unreachable. Meaningless when a negative cycle exists.\n
    """
    if self.distance[source][target] == float("inf"):
      return None

    # follow successor pointers forward from the source to the target.
    path: list[Label] = [source]
    cursor: Label = source
    while cursor != target:
      next_label: Optional[Label] = self.successor[cursor][target]
      if next_label is None:
        return None
      cursor = next_label
      path.append(cursor)

    return path

def floyd_warshall(graph: Graph[Label]) -> AllPairsPaths[Label]:
  """
    Shortest distances between every ordered pair of vertices in `graph`.\n
    Handles negative edges; sets `has_negative_cycle` when some vertex can\n
    reach itself at negative cost.\n
  """
  labels: list[Label] = graph.labels
  infinity: float = float("inf")

  # initialize with direct edges; zero on the diagonal, infinity elsewhere.
  distance: dict[Label, dict[Label, float]] = {
    source: {target: (0.0 if source == target else infinity) for target in labels}
    for source in labels
  }
  successor: dict[Label, dict[Label, Optional[Label]]] = {
    source: {target: None for target in labels} for source in labels
  }
  for edge in graph.edges():
    source_label: Label = edge.source.label
    target_label: Label = edge.target.label

    # keep the cheapest parallel edge between a pair.
    if edge.weight < distance[source_label][target_label]:
      distance[source_label][target_label] = edge.weight
      successor[source_label][target_label] = target_label

  # admit one intermediate vertex per round; relax every pair through it.
  for intermediate in labels:
    for source_label in labels:
      if distance[source_label][intermediate] == infinity:
        continue
      for target_label in labels:
        candidate: float = (
          distance[source_label][intermediate]
          + distance[intermediate][target_label]
        )

        # routing through the intermediate beats the best known direct cost.
        if candidate < distance[source_label][target_label]:
          distance[source_label][target_label] = candidate
          successor[source_label][target_label] = successor[source_label][intermediate]

  has_negative_cycle: bool = any(distance[label][label] < 0 for label in labels)
  return AllPairsPaths(distance, successor, has_negative_cycle)

graph.pypython

from collections.abc import Hashable, Iterator
from typing import Generic, Optional, TypeVar


Label = TypeVar("Label", bound=Hashable)


class Edge(Generic[Label]):
  """
    A directed connection from `source` to `target`, carrying a weight.\n
  """

  def __init__(
    self,
    source: Vertex[Label],
    target: Vertex[Label],
    weight: float = 1.0,
  ) -> None:
    self.source: Vertex[Label] = source
    self.target: Vertex[Label] = target
    self.weight: float = weight

  def __repr__(self) -> str:
    return f"Edge({self.source.label!r} -> {self.target.label!r}, w={self.weight})"


class Vertex(Generic[Label]):
  """
    A graph vertex: a label plus the list of edges leaving it.\n
  """

  def __init__(self, label: Label) -> None:
    self.label: Label = label
    self.outgoing: list[Edge[Label]] = []

  def neighbors(self) -> list[Vertex[Label]]:
    """
      The vertices reachable from this one by a single edge.\n
    """
    return [edge.target for edge in self.outgoing]

  def edge_to(self, label: Label) -> Optional[Edge[Label]]:
    """
      The outgoing edge to the vertex with `label`, or None.\n
    """
    for edge in self.outgoing:
      if edge.target.label == label:
        return edge
    return None

  def __repr__(self) -> str:
    return f"Vertex({self.label!r})"


class Graph(Generic[Label]):
  """
    A graph of Vertex objects linked by Edge objects.\n
    Pass `directed=True` for a digraph; otherwise each `add_edge` inserts\n
    the reverse edge too.\n
  """

  def __init__(self, directed: bool = False) -> None:
    self.directed: bool = directed
    self._vertices: dict[Label, Vertex[Label]] = {}

  def add_vertex(self, label: Label) -> Vertex[Label]:
    """
      Return the vertex for `label`, creating it if it is absent.\n
    """
    # reuse the existing vertex, or mint and register a fresh one.
    vertex = self._vertices.get(label)
    if vertex is None:
      vertex = Vertex(label)
      self._vertices[label] = vertex
    return vertex

  def add_edge(
    self,
    source_label: Label,
    target_label: Label,
    weight: float = 1.0,
  ) -> None:
    """
      Connect two labels (creating either vertex as needed).\n
      Adds the reverse edge as well when the graph is undirected.\n
    """
    source = self.add_vertex(source_label)
    target = self.add_vertex(target_label)

    # link source to target, and mirror it back when undirected.
    source.outgoing.append(Edge(source, target, weight))
    if not self.directed:
      target.outgoing.append(Edge(target, source, weight))

  def vertex(self, label: Label) -> Vertex[Label]:
    """
      The vertex carrying `label` (raises KeyError if absent).\n
    """
    return self._vertices[label]

  @property
  def vertices(self) -> list[Vertex[Label]]:
    """
      Every vertex, in insertion order.\n
    """
    return list(self._vertices.values())

  @property
  def labels(self) -> list[Label]:
    """
      Every vertex label, in insertion order.\n
    """
    return list(self._vertices)

  def edges(self) -> Iterator[Edge[Label]]:
    """
      Each edge once — an undirected edge is yielded a single time.\n
    """
    # track undirected endpoint pairs so each is emitted only once.
    seen: set[frozenset[Label]] = set()

    for vertex in self._vertices.values():
      for edge in vertex.outgoing:
        # skip an undirected edge already yielded from the other endpoint.
        if not self.directed:
          endpoints = frozenset((edge.source.label, edge.target.label))
          if endpoints in seen:
            continue
          seen.add(endpoints)

        yield edge

  def __contains__(self, label: Label) -> bool:
    return label in self._vertices

  def __iter__(self) -> Iterator[Vertex[Label]]:
    return iter(self._vertices.values())

  def __len__(self) -> int:
    return len(self._vertices)

Choosing an algorithm

Algorithm	Solves	Negative edges?	Time
BFS	SSSP, unweighted	n/a	$O (V + E)$
DAG relaxation	SSSP on a DAG	yes	$O (V + E)$
$Dijkstra$	SSSP	no	$O (E + V log V)$
$Bellman-Ford$	SSSP, + cycle detection	yes	$O (V \cdot E)$
$Floyd-Warshall$	all-pairs	yes	$O (V^{3})$

The decision tree is short: unweighted, use BFS; a DAG, relax in topological order; non-negative weights, use Dijkstra (the fastest for one source); negative edges possible, use Bellman-Ford and let it detect negative cycles; every pair at once, use Floyd-Warshall on dense graphs, or repeated Dijkstra ( $O (V E + V^{2} log V)$ ) when the graph is sparse and the weights non-negative. All five are disciplined applications of the same $Relax$ primitive; they differ only in which edges they relax, and in what order.

Sparse all-pairs and what negative cycles buy you

Johnson's algorithm. Floyd-Warshall's $Θ (V^{3})$ is fine on dense graphs but wasteful on sparse ones. Johnson's algorithm computes all-pairs shortest paths in $O (V E + V^{2} log V)$ — the cost of $V$ Dijkstra runs — while still tolerating negative edges.⁴ It uses a reweighting that removes the negatives without changing which paths are shortest. Add a dummy vertex $q$ with a zero-weight edge to every vertex, run Bellman-Ford once from $q$ to get a potential $h (v) = δ (q, v)$ , then reweight each edge to

w^{'} (u, v) = w (u, v) + h (u) - h (v) .

The triangle inequality $h (v) \leq h (u) + w (u, v)$ makes every $w^{'} (u, v) \geq 0$ , and the $h (u) - h (v)$ terms telescope along any path, so a path's reweighted length differs from its true length by the constant $h (s) - h (t)$ — same ordering, same shortest paths. Now run Dijkstra from every source on the non-negative $w^{'}$ , and undo the shift. One Bellman-Ford pass establishes non-negativity; $V$ Dijkstra passes finish the job. (This is the same potential trick that underlies A* from the previous lesson.)

SPFA and the practical Bellman-Ford. In practice, few graphs force all $V - 1$ Bellman-Ford rounds. The shortest-path faster algorithm keeps a queue of vertices whose estimate just improved and only relaxes out of those, often finishing in far fewer than $V E$ operations — though its worst case is still $Θ (V E)$ , so it is a constant-factor win, not an asymptotic one. Bellman-Ford also parallelizes cleanly: every edge in a round relaxes independently, which is why GPU shortest-path codes favor it over Dijkstra's inherently sequential extraction order.

What a negative cycle is worth. Bellman-Ford's negative-cycle detector is useful in its own right: some problems ask for the cycle itself. In currency arbitrage, let each currency be a vertex and each exchange rate $r_{uv}$ an edge of weight $- log r_{uv}$ . A path's total weight is $- log$ of the product of rates along it, so any cycle of negative total weight is a sequence of trades that multiplies the starting sum by more than $1$ .⁵ Detecting arbitrage is Bellman-Ford's extra pass, and reconstructing the offending cycle from the predecessor pointers recovers the trades.

Arbitrage as a negative cycle. Each edge

u \to v

carries weight

w_{uv} = - log r_{uv}

, so the cycle USD to EUR to GBP to USD has total weight

w_{1} + w_{2} + w_{3} = - log (r_{1} r_{2} r_{3})

; it is negative exactly when the product of rates exceeds

1

, i.e. the loop is profitable.

The pattern generalizes: minimum-mean-cycle, difference constraints (systems of $x_{j} - x_{i} \leq c$ solved by a single Bellman-Ford), and deadlock detection all reduce to shortest paths with negative edges. Whenever a problem's cost is a sum you want to drive as low as possible around a loop, Bellman-Ford's cycle machinery is the tool.

Takeaways

Shortest paths rest on relaxation plus two structural facts: the triangle inequality and optimal substructure.
$Dijkstra$ greedily finalizes the closest frontier vertex; the cut argument shows an extracted vertex's estimate is already exact. Correct only for non-negative weights; a single negative edge lets a cheap route arrive after its target is frozen. $O (E + V log V)$ with a Fibonacci heap.
$Bellman-Ford$ is a dynamic program: $OPT (k, v)$ = cheapest $s ⇝ v$ walk of $\leq k$ edges, and one DP row = one pass of relaxing all edges. Shortest paths need $\leq ∣ V ∣ - 1$ edges (short-circuit any cycle), so $∣ V ∣ - 1$ rounds suffice; one extra round detects negative cycles. Slower at $Θ (V \cdot E)$ but handles negative edges.
On a DAG, relaxing in topological order solves SSSP in $Θ (V + E)$ .
$Floyd-Warshall$ computes all-pairs shortest paths in $Θ (V^{3})$ via a dynamic program over intermediate vertices.

CLRS, Ch. 24 & 25 — Single-Source and All-Pairs Shortest Paths — relaxation, the triangle inequality, and optimal substructure. ↩
Erickson, Ch. 8 & 9 — Shortest Paths — Bellman-Ford's extra relaxation pass detecting a negative cycle. ↩
Skiena, §6 — Weighted Graph Algorithms — Floyd-Warshall's $Θ (V^{3})$ all-pairs dynamic program. ↩
Johnson, D. B. (1977), Efficient algorithms for shortest paths in sparse networks, Journal of the ACM 24(1), 1–13 — reweighting for all-pairs shortest paths on sparse graphs. ↩
Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms (CLRS), Problem 24-3 — currency arbitrage as a negative-weight cycle under $- log$ rates. ↩

Bellman-Ford as a dynamic program

Floyd-Warshall: all pairs at once

Choosing an algorithm

Sparse all-pairs and what negative cycles buy you

Takeaways

Footnotes