Skip to main content

Shortest Path Problem Variants

What This Concept Is​

"Shortest path" is not a single problem. It is a family of problems parameterized by three independent choices:

  • Source structure. Single-source (SSSP), single-pair (s to t), all-pairs (APSP), or multi-source (shortest from any of several sources).
  • Edge weights. All unit, nonnegative, real-valued with possible negative edges, or permitting negative cycles.
  • Path cost. Sum of edge weights (classical), max of edge weights (bottleneck), product (multiplicative), or more exotic aggregations.

The combination decides which algorithm can run:

WeightsSSSPAPSP
unitBFS in `O(V
nonnegativeDijkstra in `O((V
real, no negative cyclesBellman-Ford in `O(V
negative cycle presentno finite shortest path; detect insteaddetect instead
DAG, any weightstopo-order relax in `O(V

Two algorithmic families drive this landscape: greedy (Dijkstra, pick closest unfinalized) and relaxation-based DP (Bellman-Ford, Floyd-Warshall). Dijkstra is faster but constrained to nonnegative weights; Bellman-Ford is more general but slower. Floyd-Warshall is the cleanest way to get APSP if the graph is dense and small.

Distinguish sharply: Dijkstra vs Bellman-Ford differ on negative-edge handling (Dijkstra breaks); BFS vs Dijkstra differ on unweighted vs weighted (BFS is faster on unweighted); Floyd-Warshall vs Johnson's differ on density (FW wins dense, Johnson's wins sparse).

Why It Matters Here​

Most shortest-path bugs are variant mismatches: running the wrong algorithm for the problem you actually have. Before coding anything, you must state exactly which variant you are solving. That decision pre-determines what correctness even means - if negative cycles are present, there is no shortest simple path in general, so the right question becomes "detect the negative cycle" rather than "find a distance."

The pattern repeats throughout the semester: naming the problem variant is half the solve.

Concrete Example​

Three near-identical-sounding problems:

  1. "Shortest driving distance from my house to every park in the city." Graph has nonnegative mile weights. Variant: SSSP, nonnegative weights -> Dijkstra.
  2. "Most profitable sequence of currency trades starting from USD." Graph has real-valued log-rate weights (and possibly negative). Variant: SSSP, possibly negative edges, want negative-cycle detection -> Bellman-Ford.
  3. "Fastest travel time between every pair of cities on a small country-wide network of 500 airports." Variant: APSP, nonnegative weights, dense-ish graph -> Floyd-Warshall (simplest) or repeated Dijkstra (if sparse).

Picking the wrong one gives you a running algorithm with an incorrect answer, not a crash.

A visual comparison on the same tiny graph:

  • BFS (pretending weights are 1): returns s -> t via 2 edges through b.
  • Dijkstra (honoring weights): returns s -> b -> a -> t with cost 1+2+3=6.
  • Bellman-Ford: same answer as Dijkstra (no negative edges).
  • Floyd-Warshall: produces shortest distances between every pair.

Change one edge to negative and Dijkstra can silently produce a wrong answer while Bellman-Ford still works.

Common Confusion / Misconceptions​

  • "Shortest silently assumes additive cost." If the path cost is max of edge weights (bottleneck shortest path), standard Dijkstra with addition is wrong; you need a modified relaxation using max instead of + (the monoid changes). Any MST already solves bottleneck shortest paths along tree edges.
  • "Dijkstra fails loudly on negative weights." It does not. It produces a plausible-looking wrong answer. This is the dangerous mode of failure.
  • "Bellman-Ford is only for negative edges." It works with nonnegative edges too, just slower than Dijkstra. Its real job is negative-cycle detection.
  • "APSP always needs Floyd-Warshall." For sparse graphs with nonnegative weights, running Dijkstra from each vertex beats Floyd-Warshall asymptotically: O(V(V+E) log V) = O(V^2 log V + VE log V) vs O(V^3).
  • "Multi-source is a new algorithm." It is not. Push all sources into the priority queue (Dijkstra) or queue (BFS) at distance 0; the rest is unchanged.

How To Use It​

Use this decision flow before choosing an algorithm:

  1. Is the graph a DAG? If yes, relax edges in topological order in O(|V|+|E|).
  2. Are edge weights all equal or unit? Use BFS (or 0-1 BFS for {0,1} weights).
  3. Are all weights nonnegative? Use Dijkstra.
  4. Are some weights negative? Use Bellman-Ford; it also detects negative cycles.
  5. Need distances between every pair, and the graph is small-ish (hundreds to low thousands of vertices)? Use Floyd-Warshall.
  6. Need APSP on a large sparse graph with nonnegative weights? Run Dijkstra from every source (or use Johnson's if negative edges are present but no negative cycles).
  7. Is the cost aggregation non-additive (max, product, probability)? Adapt relaxation to the correct monoid.

Write your answer down before writing code. The commentary you would have placed above the #include line is what you should have written on paper before starting.

Transfer / Where This Shows Up Later​

  • S3 (systems). Routing tables on operating systems and network stacks are shortest-path results; OSPF uses Dijkstra variants, BGP uses distance-vector variants (Bellman-Ford family).
  • S4 (compilers). Register-pressure-aware instruction scheduling minimizes weighted paths in the DAG of scheduled instructions.
  • S5 (OS). Priority inheritance chains in mutex systems use longest-path-in-DAG.
  • S6 (databases). Query optimizers pick plans by cost, effectively doing shortest path in the plan graph. Graph databases (Neo4j, JanusGraph) expose shortest-path queries directly.
  • S7 (architecture). "Blast radius" is a shortest-path query on the service-dependency graph with weighted edges for call latency.
  • S8 (distributed). Routing in SDN, mesh networks, and content delivery uses Dijkstra-family algorithms with periodic recomputation.

Back-link to S1 M2 for graph distance definitions and to M4 greedy algorithms for the greedy-choice proof that Dijkstra leans on.

Check Yourself​

  1. Why can't Dijkstra handle negative edges even when there is no negative cycle?
  2. When does a shortest path fail to exist as a finite simple path?
  3. What does "bottleneck shortest path" mean, and which aggregation replaces addition?
  4. For a DAG, why is shortest-path work linear in |V| + |E| regardless of weight signs?
  5. Explain why multi-source BFS/Dijkstra require no algorithmic change beyond initialization.
  6. Which algorithm would you use for APSP on |V| = 10^5, |E| = 10^6, weights nonnegative? Justify.

Mini Drill or Application​

For each scenario, identify the variant (source structure, weights, path cost) and the best-fit algorithm:

  1. Social-graph degrees of separation between two users.
  2. Minimum-fee money transfer across a network of banks where some fees are negative rebates.
  3. Maximum-reliability communication path where each link has an independent success probability.
  4. Shortest-expected-time path in a road network with deterministic travel times.
  5. Checking whether arbitrage is possible across k currencies with exchange rates.
  6. Shortest number of moves for a knight to reach a square on an infinite chess board.
  7. Minimum-latency path in a cloud region, where edges are latency and vertices are regions.

Then write one line of justification per choice.

Implementation drill. Given a graph library of your choice (yours or NetworkX), pick a single real dataset (e.g., SNAP road networks) and run BFS, Dijkstra, Bellman-Ford, and Floyd-Warshall (where feasible) on the same source vertex; verify the answers agree, and plot wall-clock time vs |V|.

Read This Only If Stuck​