Shortest Paths — Overview & Map

Finding the shortest route between two points is one of the most useful things a computer does — it’s what powers map directions, network routing, game AI pathfinding, and a surprising number of problems that don’t look like maps at all (word ladders, puzzle solving, dependency resolution).

This page is the map of the territory. Each algorithm below has its own detailed page; start here to understand which one you actually need.

The problem, stated precisely

We have a graph: a set of nodes (also called vertices) connected by edges. Each edge may carry a weight — a cost, distance, or time to travel along it.

The shortest path from a start node $s$ to a target node $t$ is the sequence of edges connecting them with the minimum total weight. In the graph above, the cheapest way from A to F is A → C → B → D → E → F with total cost $2+1+5+2+3 = 13$ — not the route with the fewest hops, and not the one that looks most direct.

Variants of the question

“Shortest path” is really several related problems:

Variant	What you ask for
Single-pair	Shortest path from one $s$ to one $t$ (map directions)
Single-source	Shortest paths from one $s$ to every other node
All-pairs	Shortest paths between every pair of nodes

Most single-source algorithms also solve single-pair — you just stop early once $t$ is reached.

The family of algorithms

Which algorithm you reach for depends on two questions: are the edges weighted? and can weights be negative?

Algorithm	Works on	Handles negative weights?	Typical use	Page
BFS	Unweighted graphs	n/a (no weights)	Fewest-hops path, mazes	BFS
Dijkstra	Non-negative weights	❌ No	The default for road/network maps	Dijkstra
Bidirectional Dijkstra	Non-negative weights	❌ No	Long single-pair queries, faster in practice	Bidirectional Dijkstra
A*	Non-negative weights + a heuristic	❌ No	Games, grids, geographic routing	A*
Bellman–Ford	Any weights	✅ Yes (and detects negative cycles)	Currency arbitrage, routing protocols	Bellman–Ford
Floyd–Warshall	Any weights (all-pairs)	✅ Yes	Small graphs, all-pairs distances	(mentioned below)

A decision guide

Are edges weighted?
├── No  ──────────────►  BFS
└── Yes
    ├── Any negative weights?
    │   ├── Yes ─────────►  Bellman–Ford  (or Floyd–Warshall for all-pairs)
    │   └── No
    │       ├── Need one s → t, large graph?
    │       │   ├── Have a good distance heuristic? ──►  A*
    │       │   └── No heuristic ───────────────────►  Bidirectional Dijkstra
    │       └── Need distances to everything?  ─────►  Dijkstra

Floyd–Warshall is the odd one out: instead of exploring outward from a start node, it fills a table of every node-to-node distance using dynamic programming in $O(V^3)$ time. It’s only practical for small graphs (a few hundred nodes), but when you genuinely need all-pairs distances and the graph is small, its three-nested-loop simplicity is unbeatable. For point-to-point queries on big graphs, prefer the outward-exploring algorithms above.

The one idea underneath most of them

Almost every algorithm here is built on edge relaxation. Each node keeps a “best distance found so far” estimate, starting at $\infty$ for everything except the source (which is $0$). Relaxing an edge $u \to v$ with weight $w$ asks a single question:

$$\text{if } \operatorname{dist}(u) + w < \operatorname{dist}(v) \text{, then } \operatorname{dist}(v) \leftarrow \operatorname{dist}(u) + w$$

In words: “Is going through $u$ a cheaper way to reach $v$ than anything I’ve found before? If so, record it.”

The algorithms differ mainly in the order they relax edges — greedily by smallest distance (Dijkstra), guided by a heuristic (A*), or exhaustively in rounds (Bellman–Ford). Understanding relaxation once makes all of them click.

Where to go next

• New to graphs? Start with BFS — the simplest case.
• Want the workhorse? Dijkstra is the one to know cold.
• Then Bidirectional Dijkstra and A* for faster point-to-point queries, and Bellman–Ford for negative weights.