Skip to main content

Shortest Path Problem Variants

What This Concept Is​

Choose the path problem before the algorithm: source set, targets, direction, objective, weight domain and requested witness. BFS handles unit-cost hops. Nonnegative additive weights permit Dijkstra. DAGs permit one topological pass even with signed weights. Bellman–Ford handles signed general directed graphs and diagnoses source-reachable negative cycles. Floyd–Warshall is an all-pairs matrix method; repeated single-source methods may suit sparse queries.

Why It Matters Here​

A result has three distinct meanings: unreachable, finite minimum cost, or unbounded-below walk cost. A negative cycle anywhere in the graph does not force the third status for every source/target pair. This distinction belongs in the API, tests and explanation, not merely an exception string.

Concrete Examples​

Take 0→1:2,1→2:-3,2→1:1,2→3:4,0→4:7,5→5:-1. From 0, vertices 1,2,3 have unbounded-below costs, vertex 4 has finite cost 7, and vertex 5 is unreachable. The cycle at 5 is irrelevant to this source. For a target t, unboundedness requires a negative cycle reachable from source that can also reach t.

For multiplicative route reliability with independent edge success probabilities in (0,1], minimizing sums of -log(p) can maximize the product. This requires the probabilistic model and treatment of zero probabilities to be stated; ordinary addition of probabilities does not maximize route reliability.

Common Confusion / Misconceptions​

Minimum total spanning weight is not shortest root-to-vertex distance. Widest capacity paths maximize a minimum; minimax paths minimize a maximum; neither uses the same objective as additive distance. Simple-path restrictions can make signed-weight questions different from the repeated-walk shortest-path problem.

How To Use It​

Write an algorithm-selection table with preconditions and representation costs. For repeated queries include preprocessing, graph changes and output size. Do not claim that one algorithm universally wins sparse/dense workloads in wall time without measurements. For 0/1 weights, deque-based 0–1 BFS is a useful extension with its own relaxation discipline, not ordinary first-discovery BFS.

Check Yourself​

  1. What two reachability conditions make one target unbounded?
  2. When can a negative edge still permit linear-time shortest paths?
  3. What model justifies converting a probability product to a sum?
  4. Why does a single-pair query not always need all-pairs preprocessing?

Mini Drill or Application​

Classify five cases: unit-hop reachability, nonnegative weighted routing, signed DAG scheduling, a reachable negative cycle with an unaffected branch, and minimum-bottleneck routing. Give preconditions and a counterexample to one wrong choice. See P9 and the certificate lesson.

Read This Only If Stuck​

Find shortest-path variants, weight domains, and negative-cycle scope in Skiena, CLRS, or Sedgewick and Wayne. These are book indexes, not exact section links. The reading guide names bounded assignments and local source files. Attempt the worked examples before adding more reading.