Introduction

Large systems look messy up close—queues, caches, RPCs, retries—but from a distance they are just graphs. Components act as vertices, each one representing a distinct unit of computation or state. Edges trace the directional interactions that bind them together—RPC calls, dependency lookups, message flows, data pipelines. Weights enrich those edges with the operational constraints that shape system behavior: typical and tail latencies, retry overhead, throughput limits, and failure probabilities. When we adopt this lens, operational questions reduce to graph questions and the right algorithm becomes a matter of fit—anchored to concrete costs and guarantees.

Three recurring decisions shape real-world performance:

1. Can we get there at all? Before optimizing, we need a quick test for reachability to fail fast when the target is isolated or misrouted.
2. In what order can work run safely? Dependencies create partial orders; violating them risks deadlocks, partial writes, or wasted retries.
3. What route minimizes cost under current conditions? With heterogeneous latencies and reliability, the path with minimum total cost wins—unless hidden negative cycles make “cheapest” meaningless.

Each of these questions aligns with a specific algorithmic tool, giving us dependable procedures with clear performance bounds:

• Breadth-First Search (BFS) answers reachability and yields the fewest-hop route on unweighted graphs.
• Topological Sort emits a valid dependency order and exposes cycles when none exists.
• Dijkstra’s Algorithm finds a minimum-cost path when all weights are non-negative—typical for latency and monetary cost.
• Bellman–Ford handles negative edges and detects negative cycles explicitly.

We then anchor the discussion in a compact but realistic checkout workflow, using it to show how each algorithm interacts with practical system limits—how wider fan-outs increase CPU time, how larger search frontiers create more memory pressure, and how different weight patterns influence worst-case latency. This keeps the analysis tied to engineering reality: fewer expansions mean less work, steadier data structures avoid unnecessary pauses, and identifying cycles in the dependency graph stops the system from chasing work that can never finish. The treatment draws on the original algorithm papers (Dijkstra 1959; Bellman 1958; Ford 1956) and pairs them with accessible platform documentation such as MDN’s material on event-loop scheduling to show how these ideas manifest in everyday code.

Example System

To make the ideas tangible, we map a pared-down checkout workflow onto a directed, weighted graph. Each node is a service boundary; each edge represents a synchronous call; each weight approximates the 95th-percentile latency observed for that hop under load. This abstraction lets us reason about reachability, dependency ordering, and end-to-end cost without getting lost in implementation details.

• Client → CheckoutService (0) The entry edge carries no real latency budget; it simply marks where the server begins accounting.

• CheckoutService → AuthService (30) Authentication dominates early in the request. A 30 ms p95 indicates both network and compute variability the algorithm must treat as a non-trivial weight.

• CheckoutService → CartService (15) Cart resolution is cheaper but still noticeable. Its presence creates a fork in the graph that BFS, topological ordering, and shortest-path algorithms handle differently.

• AuthService → PaymentGateway (40) Payment introduces the first heavy edge. At p95 this is often the controlling cost, and algorithms sensitive to weight magnitude treat it as a meaningful barrier.

• CartService → OrdersDB (10) Cart data fans into the database at low cost, establishing an alternate path to the same sink node (OrdersDB).

• PaymentGateway → OrdersDB (20) Payment confirmation converges with cart data at the same sink. This parallel structure is precisely where path-finding algorithms show their value: one path is cheaper in isolation, but the total route depends on upstream weights and edge ordering.

A minimal helper constructs a directed, weighted adjacency list for the algorithms below.

// src/graphs/model.ts

export type VertexId = string;

export interface WeightedEdge {
  from: VertexId;
  to: VertexId;
  weight: number;
}
export interface WeightedAdjList {
  directed: true;
  neighbors: Map<VertexId, Array<{ to: VertexId; weight: number }>>;
}

export function buildWeightedAdjList(edges: WeightedEdge[]): WeightedAdjList {
  const neighbors = new Map<
    VertexId,
    Array<{ to: VertexId; weight: number }>
  >();
  for (const { from, to, weight } of edges) {
    if (!neighbors.has(from)) neighbors.set(from, []);
    neighbors.get(from)!.push({ to, weight });
  }
  return { directed: true, neighbors };
}

export const checkoutEdges: WeightedEdge[] = [
  { from: "Client", to: "CheckoutService", weight: 0 },
  { from: "CheckoutService", to: "AuthService", weight: 30 },
  { from: "CheckoutService", to: "CartService", weight: 15 },
  { from: "AuthService", to: "PaymentGateway", weight: 40 },
  { from: "CartService", to: "OrdersDB", weight: 10 },
  { from: "PaymentGateway", to: "OrdersDB", weight: 20 },
];

export const checkoutGraph = buildWeightedAdjList(checkoutEdges);

Reachability with Breadth-First Search

BFS provides the most direct test of whether one component can reach another. It expands the search layer by layer, examining all vertices at distance k before touching those at distance k+1. In an unweighted setting this ordering matters: the first time a vertex appears, we have already discovered the minimal number of hops needed to reach it. The cost profile is predictable. Time grows linearly with the size of the graph—O(V + E)—because each vertex and edge is processed at most once. Space is dominated by the frontier, the set of vertices waiting to be explored; in wide fan-out structures this frontier controls memory consumption and can approach O(V) in the worst case.

// src/graphs/bfs.ts

import type { VertexId } from "./model";

export interface AdjList {
  neighbors: Map<VertexId, VertexId[]>;
}

export function bfsReachable(
  graph: AdjList,
  source: VertexId,
  target: VertexId
): boolean {
  const seen = new Set<VertexId>([source]);
  const q: VertexId[] = [source];
  let head = 0; // avoid Array.shift() copying
  while (head < q.length) {
    const u = q[head++]!;
    if (u === target) return true;
    for (const v of graph.neighbors.get(u) ?? []) {
      if (!seen.has(v)) {
        seen.add(v);
        q.push(v);
      }
    }
  }
  return false;
}

To apply BFS on the weighted model, project a reachability view by discarding weights and retaining only the directed structure. This collapses the system down to its essential question: can control or data flow from A to B at all? In practice, this is often the first and cheapest check. Most operational failures—miswired dependencies, missing routes, incorrect feature flags, or incomplete deployments—manifest as simple disconnections long before latency or cost become relevant. By stripping weights, BFS isolates these structural pathologies without incurring the overhead of heavier algorithms. If no path exists in this unweighted graph, no amount of optimization on the weighted one will fix it; if a path does exist, we can proceed to the more expensive ordering and cost-sensitive analyses with confidence that the topology itself is sound.

Dependency Ordering with Topological Sort

A topological sort produces a sequence in which every component appears after all of the components it depends on. The standard approach (Kahn’s algorithm) operates by tracking each vertex’s in-degree—the number of incoming edges—and repeatedly selecting those with in-degree 0. Emitting such a vertex is safe because nothing remains upstream of it; removing its outgoing edges may unlock additional vertices whose dependencies are now satisfied.

If the process stalls with vertices that still have positive in-degree, the remaining subgraph forms a cycle. In systems terms, this reveals a deadlocked dependency pattern: some components require results from one another in a loop that cannot be resolved by ordering alone. The algorithm exposes this structural flaw without executing any work.

The cost scales predictably. Each edge and vertex is processed a constant number of times, yielding O(V + E) time and O(V) space. This makes topological sort a practical precondition check before executing workflows, migrations, or build steps that must obey strict dependency constraints.

// src/graphs/toposort.ts

import type { VertexId } from "./model";

export interface DirAdjList {
  neighbors: Map<VertexId, VertexId[]>;
  directed: true;
}

export function topologicalSortOrThrow(graph: DirAdjList): VertexId[] {
  const indeg = new Map<VertexId, number>();
  for (const [u, vs] of graph.neighbors) {
    if (!indeg.has(u)) indeg.set(u, 0);
    for (const v of vs) indeg.set(v, (indeg.get(v) ?? 0) + 1);
  }
  const order: VertexId[] = [];
  const q: VertexId[] = [];
  for (const [v, d] of indeg) if (d === 0) q.push(v);
  let head = 0;
  while (head < q.length) {
    const u = q[head++]!;
    order.push(u);
    for (const v of graph.neighbors.get(u) ?? []) {
      indeg.set(v, indeg.get(v)! - 1);
      if (indeg.get(v) === 0) q.push(v);
    }
  }
  if (order.length !== indeg.size)
    throw new Error("cycle detected: no valid order");
  return order;
}

Minimum-Cost Path with Dijkstra

When multiple routes exist, the goal is to identify the one with the lowest accumulated latency from Client to OrdersDB. Dijkstra’s algorithm does this by maintaining a table of tentative distances and repeatedly expanding the vertex with the currently smallest known total cost. A min-heap keeps these candidates ordered so that each extraction reflects the next provably optimal step.

The guarantee hinges on a simple condition: all weights must be non-negative. Latency, monetary cost, and most operational penalties meet this requirement, which makes Dijkstra a natural fit for service graphs. As the algorithm progresses, each relaxation step—checking whether an alternate route yields a better total—captures the real engineering trade-off: expensive edges can be tolerated if they reduce downstream calls, while seemingly cheap edges may accumulate into a slower overall path.

The cost profile reflects the use of a priority queue. Each push and pop costs log V, and every edge is examined at most once, giving a predictable O((V + E) log V) runtime. For systems that need to compare routing strategies, estimate end-to-end latency, or model user-visible performance under load, this provides an efficient and reliable baseline.

// src/graphs/dijkstra.ts

import type { WeightedAdjList, VertexId } from "./model";

class MinPQ<T> {
  private a: Array<{ k: number; v: T }> = [];
  push(k: number, v: T) {
    this.a.push({ k, v });
    this.up(this.a.length - 1);
  }
  pop(): { k: number; v: T } | undefined {
    if (!this.a.length) return;
    const top = this.a[0];
    const last = this.a.pop()!;
    if (this.a.length) {
      this.a[0] = last;
      this.down(0);
    }
    return top;
  }
  size() {
    return this.a.length;
  }
  private up(i: number) {
    while (i) {
      const p = (i - 1) >> 1;
      if (this.a[p].k <= this.a[i].k) break;
      [this.a[p], this.a[i]] = [this.a[i], this.a[p]];
      i = p;
    }
  }
  private down(i: number) {
    for (;;) {
      const l = 2 * i + 1;
      const r = l + 1;
      let s = i;
      if (l < this.a.length && this.a[l].k < this.a[s].k) s = l;
      if (r < this.a.length && this.a[r].k < this.a[s].k) s = r;
      if (s === i) break;
      [this.a[i], this.a[s]] = [this.a[s], this.a[i]];
      i = s;
    }
  }
}

export function dijkstra(
  graph: WeightedAdjList,
  source: VertexId,
  target: VertexId
) {
  const dist: Record<string, number> = {};
  const prev: Record<string, VertexId | null> = {};
  for (const v of graph.neighbors.keys()) {
    dist[v] = Infinity;
    prev[v] = null;
  }
  dist[source] = 0;
  const pq = new MinPQ<VertexId>();
  pq.push(0, source);

  while (pq.size()) {
    const { k: d, v: u } = pq.pop()!;
    if (d !== dist[u]) continue; // stale entry
    if (u === target) break;
    for (const { to, weight } of graph.neighbors.get(u) ?? []) {
      const nd = d + weight;
      if (nd < dist[to]) {
        dist[to] = nd;
        prev[to] = u;
        pq.push(nd, to);
      }
    }
  }

  const path: VertexId[] = [];
  for (let at: VertexId | null = target; at != null; at = prev[at])
    path.push(at);
  path.reverse();
  return { distance: dist[target], path };
}

On our numbers, Dijkstra prefers Client → CheckoutService → CartService → OrdersDB (25 ms) over the CheckoutService → AuthService → PaymentGateway → OrdersDB route (90 ms)—a 3.6× improvement that directly affects tail latency when hops serialize.

When to Use Bellman–Ford

Bellman–Ford becomes essential when the graph violates Dijkstra’s assumption that all edges have non-negative weights. Optimization pipelines, dynamic pricing, quota enforcement, and credit-based routing can introduce edges representing rebates, penalties, or preference boosts—effectively negative costs.

Bellman–Ford relaxes every edge up to V−1 times, ensuring that any valid shortest path—regardless of weight sign—has enough opportunities to propagate improvements. A final pass checks for further improvements; if any edge can still relax, the graph contains a negative cycle, meaning total cost can drop without bound. In operational terms, this exposes workflows or routing rules that allow runaway retries or unbounded cost accumulation.

The trade-off is computational cost: O(V·E) time and O(V) space. It is slower but necessary when correctness is paramount under fluctuating or adversarial weights.

// src/graphs/bellmanFord.ts

import type { WeightedEdge, VertexId } from "./model";

export function bellmanFord(
  vertices: VertexId[],
  edges: WeightedEdge[],
  source: VertexId
) {
  const dist: Record<string, number> = {};
  const prev: Record<string, VertexId | null> = {};
  for (const v of vertices) {
    dist[v] = Infinity;
    prev[v] = null;
  }
  dist[source] = 0;

  for (let i = 0; i < vertices.length - 1; i++) {
    let changed = false;
    for (const { from, to, weight } of edges) {
      if (dist[from] + weight < dist[to]) {
        dist[to] = dist[from] + weight;
        prev[to] = from;
        changed = true;
      }
    }
    if (!changed) break;
  }

  for (const { from, to, weight } of edges) {
    if (dist[from] + weight < dist[to]) throw new Error("negative cycle");
  }
  return { dist, prev };
}

Conclusion

A single graph model captures the structural and operational constraints of most service workflows. Once that structure is in place, the choice of procedure is not aesthetic—it is a direct expression of the question being asked. Reachability collapses to BFS; dependency safety aligns with toposort; cost-sensitive routing flows through Dijkstra; and environments with penalties or preference signals require Bellman–Ford for correctness.

These algorithms differ not just in theory but in how they behave under real load. BFS grows and shrinks a frontier that can dominate heap pressure. Toposort walks edges once but exposes cycles that would otherwise burn CPU in futile retries. Dijkstra balances exploration against bookkeeping overhead through its priority queue. Bellman–Ford brute-forces correctness, consuming work proportional to the full cross-product of vertices and edges.

Choosing well means aligning the procedure with both the question and the system’s tolerance for cost. In wide fan-out topologies or high-frequency routing paths, the difference between linear and superlinear cost directly maps to latency, throughput ceilings, and slack for downstream tiers. Graph modeling makes these trade-offs explicit and gives us a vocabulary for reasoning about system behavior before touching production.

Key Takeaways

• Map the decision to the algorithm: reachability → BFS; ordering → toposort; minimum cost (non-negative) → Dijkstra; negatives or required cycle detection → Bellman–Ford.
• Complexity is cost: linear O(V+E), heap-augmented O((V+E) log V), and pass-heavy O(V·E) translate directly into CPU time, memory pressure, cache effects, and latency.
• Assumptions matter: Dijkstra requires non-negative weights; when that cannot be guaranteed, Bellman–Ford provides correctness and explicit detection of unbounded cycles.
• Implementation details surface in performance: avoid array operations that induce copying, guard against stale priority-queue entries, reconstruct paths from predecessor maps, and keep adjacency structures cache-friendly to reduce traversal stalls.

I originally published this article on my web development company Bliztek, LLC Blog.