Shortest Path Algorithms

Shortest path algorithms compute minimum-weight routes between vertices in a weighted graph, with different algorithms suited to nonnegative weights, negative weights, and all-pairs versus single-source queries.

Definition

A shortest path between two vertices in a weighted graph is a path whose total edge weight is minimum; shortest path algorithms compute such paths and their distances, either from one source to all vertices or between all pairs of vertices.

Scope

This topic covers single-source shortest paths (Dijkstra's algorithm for nonnegative weights, Bellman-Ford for graphs with negative weights and for detecting negative cycles), all-pairs shortest paths (Floyd-Warshall, Johnson's algorithm), and shortest paths in directed acyclic graphs. It treats the relaxation principle common to these methods and the role of priority queues in efficient implementation. It excludes unweighted shortest paths obtained by breadth-first search, covered under graph traversal.

Core questions

• How does edge relaxation progressively tighten distance estimates toward true shortest distances?
• Why does Dijkstra's algorithm require nonnegative edge weights to be correct?
• How does Bellman-Ford handle negative weights and detect negative cycles?
• When is computing all-pairs shortest paths more efficient than repeating a single-source method?
• How do priority-queue choices affect the running time of Dijkstra's algorithm?

Key concepts

• edge relaxation
• single-source shortest paths
• Dijkstra's algorithm
• Bellman-Ford algorithm
• negative-weight cycles
• all-pairs shortest paths
• Floyd-Warshall algorithm
• priority-queue implementation

Key theories

Edge relaxation and greedy selection

Shortest-path algorithms repeatedly relax edges, replacing a distance estimate when a shorter route is found; Dijkstra's algorithm greedily finalizes the closest unsettled vertex, which is correct precisely because edge weights are nonnegative.

Dynamic programming for all-pairs paths

The Floyd-Warshall algorithm computes all-pairs shortest paths by a dynamic program over intermediate vertices, running in cubic time and naturally handling negative edge weights (without negative cycles).

Clinical relevance

Shortest-path algorithms power navigation and mapping services, packet routing protocols in networks, route planning in logistics, and any system that finds least-cost paths through a weighted network, including game pathfinding and resource-distance computations in spatial analysis.

History

Dijkstra published his single-source shortest-path algorithm in 1959. The Bellman-Ford algorithm, handling negative weights, emerged from work by Bellman, Ford and Moore in the late 1950s. Floyd's 1962 algorithm, building on Warshall's transitive-closure method, gave a compact all-pairs solution that remains a standard.

Key figures

• Edsger W. Dijkstra
• Richard Bellman
• Lester Ford
• Robert W. Floyd

Seminal works

• dijkstra1959
• floyd1962
• cormen2009

Frequently asked questions

Why can't Dijkstra's algorithm handle negative edge weights?

Dijkstra's algorithm finalizes the closest unsettled vertex and never revisits it, assuming no later path can be shorter. A negative edge could create such a shorter path after a vertex is settled, breaking the assumption. Bellman-Ford, which relaxes all edges repeatedly, is used instead.

When should I use an all-pairs algorithm instead of running Dijkstra from every vertex?

For dense graphs or when many or all source-destination distances are needed, Floyd-Warshall's simple cubic-time all-pairs computation is often preferable. For sparse graphs, running Dijkstra (or Johnson's algorithm for negative weights) from each source can be asymptotically faster.