10.20 Choosing the Right Shortest-Path Algorithm

This chapter introduced a substantial collection of shortest-path algorithms.

algorithmsshortest-pathsgraphs

10.20 Choosing the Right Shortest-Path Algorithm

This chapter introduced a substantial collection of shortest-path algorithms.

At first glance, the algorithms may appear unrelated.

Some use queues.

Some use priority queues.

Some use dynamic programming.

Some rely on graph transformations.

Some use heuristics.

In practice, the most important skill is not memorizing every algorithm. It is recognizing which algorithm fits a particular problem.

This recipe summarizes the major shortest-path techniques and provides a framework for selecting the right tool.

Problem

Given a shortest-path problem, determine the most appropriate algorithm based on:

  • Graph structure
  • Edge weights
  • Number of sources
  • Number of destinations
  • Performance requirements

The goal is to choose an algorithm that is both correct and efficient.

Start with the Edge Weights

The first question should always be:

What kinds of edge weights exist?

This single question eliminates many possibilities immediately.

Unweighted Graph

Every edge has equal cost.

A -> B
B -> C
C -> D

Use:

BFS

Complexity:

O(V + E)

BFS is optimal for this case.

Anything more sophisticated is unnecessary.

Weights Restricted to 0 and 1

Example:

Preferred move = 0
Alternative move = 1

Use:

0-1 BFS

Complexity:

O(V + E)

The deque-based implementation is usually faster and simpler than Dijkstra.

Nonnegative Weights

Example:

1
5
12
100

Use:

Dijkstra

Complexity:

O((V + E) log V)

This is the default shortest-path algorithm for weighted graphs.

Negative Weights

Example:

-3
2
7

Use:

Bellman-Ford

Complexity:

O(VE)

Dijkstra is no longer safe.

Negative Cycles

Example:

A -> B = 1
B -> C = -4
C -> A = 2

Use:

Bellman-Ford

to detect them.

No shortest path exists if a reachable negative cycle is present.

Check for Special Graph Structure

Many graphs have properties that permit faster algorithms.

Directed Acyclic Graph

Example:

Tasks
Dependencies
Build systems
Pipelines

Use:

DAG shortest paths

Complexity:

O(V + E)

Even negative edge weights are allowed.

Grid

Example:

Maze
Game map
Robot workspace

Use:

BFS

for uniform movement cost.

Use:

Dijkstra

for weighted terrain.

Use:

A*

when a target is known and a heuristic exists.

Road Networks

Example:

GPS routing
City maps
Navigation systems

Use:

A*

or:

Bidirectional Dijkstra

These dramatically reduce search space.

How Many Sources Exist?

The second major decision concerns sources.

One Source

Example:

Find shortest paths from A

Use:

BFS
Dijkstra
Bellman-Ford
DAG shortest paths

depending on edge weights.

Multiple Sources

Example:

Nearest hospital
Nearest warehouse
Nearest charging station

Use:

Multi-source BFS

or:

Multi-source Dijkstra

Initialize all sources simultaneously.

Every Source

Example:

Distance between every pair of vertices

Use an all-pairs algorithm.

All-Pairs Shortest Paths

Sometimes every pair matters.

Dense Graph

Use:

Floyd-Warshall

Complexity:

O(V³)

Advantages:

  • Simple
  • Supports negative edges
  • Easy path reconstruction

Sparse Graph

Use:

Johnson's algorithm

Complexity:

O(VE log V)

Advantages:

  • Handles negative edges
  • Efficient on sparse graphs

Is There a Specific Target?

Some shortest-path problems have a known destination.

Others do not.

No Specific Target

Example:

Shortest path to every vertex

Use:

BFS
Dijkstra
Bellman-Ford

Known Target

Example:

Route from A to Z

Use:

A*

or:

Bidirectional Search

The destination information can substantially reduce work.

Decision Tree

A practical decision process looks like:

Negative cycle detection?
|
+-- Yes -> Bellman-Ford
|
+-- No
    |
    +-- DAG?
    |   |
    |   +-- Yes -> DAG Shortest Paths
    |
    +-- Unweighted?
    |   |
    |   +-- Yes -> BFS
    |
    +-- Weights {0,1}?
    |   |
    |   +-- Yes -> 0-1 BFS
    |
    +-- Negative weights?
    |   |
    |   +-- Yes -> Bellman-Ford
    |
    +-- Single source?
    |   |
    |   +-- Yes -> Dijkstra
    |
    +-- All pairs?
        |
        +-- Sparse -> Johnson
        |
        +-- Dense -> Floyd-Warshall

This decision tree solves the majority of practical cases.

Comparison Table

Algorithm Negative Weights Negative Cycles Complexity
BFS No No O(V + E)
0-1 BFS No No O(V + E)
Dijkstra No No O((V + E) log V)
Bellman-Ford Yes Yes O(VE)
DAG Shortest Paths Yes No O(V + E)
Floyd-Warshall Yes Yes O(V³)
Johnson Yes Yes O(VE log V)
A* No No Heuristic dependent

This table is worth memorizing.

It captures most algorithm-selection decisions.

Real-World Examples

GPS Navigation

Properties:

Weighted graph
Known destination
Geographic coordinates

Choice:

A*

Network Routing

Properties:

Weighted graph
Many destinations

Choice:

Dijkstra

Dependency Scheduling

Properties:

DAG

Choice:

DAG shortest paths

Currency Arbitrage

Properties:

Negative weights
Negative-cycle detection

Choice:

Bellman-Ford

Distance Between All Cities

Properties:

All pairs
Dense graph

Choice:

Floyd-Warshall

Massive Sparse Transportation Network

Properties:

All pairs
Sparse graph
Negative edges possible

Choice:

Johnson

Common Misconceptions

"Dijkstra Solves Everything"

It does not.

Negative weights invalidate its correctness guarantees.

"Bellman-Ford Is Always Better Because It Handles More Cases"

It handles more cases but is usually much slower.

Use it only when necessary.

"Floyd-Warshall Is the Universal Solution"

Its cubic complexity becomes prohibitive on large graphs.

"A* Always Beats Dijkstra"

Only when a useful heuristic exists.

A poor heuristic reduces A* to Dijkstra.

"BFS Works on Weighted Graphs"

Only when every edge has equal cost.

Many incorrect shortest-path implementations fail because of this assumption.

Practical Strategy

When solving a new problem:

  1. Identify the state representation.
  2. Determine edge costs.
  3. Determine graph structure.
  4. Count sources and targets.
  5. Check for negative edges.
  6. Check for cycles.
  7. Select the simplest correct algorithm.

The simplest correct algorithm is usually the best choice.

Avoid sophisticated algorithms unless the problem genuinely requires them.

Discussion

The shortest-path algorithms in this chapter form a family rather than a collection of isolated techniques.

They share:

  • Distance labels
  • Relaxation
  • Path reconstruction
  • Graph traversal

The differences arise from assumptions.

Additional assumptions often permit faster algorithms.

For example:

Unweighted

allows BFS.

Acyclic

allows topological relaxation.

0-1 weights

allow deque optimization.

Known target

allows heuristics.

Recognizing these assumptions is the key to algorithm selection.

Complexity Summary

Algorithm Runtime
BFS O(V + E)
0-1 BFS O(V + E)
DAG Shortest Paths O(V + E)
Dijkstra O((V + E) log V)
Bellman-Ford O(VE)
Floyd-Warshall O(V³)
Johnson O(VE log V)

These complexity bounds provide a useful mental checklist during design.

Takeaway

Choosing the correct shortest-path algorithm begins with understanding the graph rather than the algorithm. Edge weights, graph structure, source count, destination requirements, and performance constraints determine the appropriate solution. BFS handles unweighted graphs, Dijkstra dominates nonnegative weighted graphs, Bellman-Ford manages negative edges, Floyd-Warshall and Johnson solve all-pairs problems, and A* accelerates goal-directed searches. In practice, successful shortest-path design is often more about recognizing problem structure than implementing algorithms.