Shortest Path Algorithms

Introduction

Finding the shortest path between two points is one of the most fundamental problems in graph theory and computer science. GPS navigation systems find shortest routes through road networks. Internet routers find shortest paths through communication networks. Logistics companies optimize delivery routes.

The shortest path problem comes in several variants. Single-source shortest path finds the shortest paths from one vertex to all others. Single-pair shortest path finds the path between two specific vertices. All-pairs shortest path finds paths between every pair of vertices.

Different algorithms are optimal for different scenarios. Dijkstra's algorithm handles non-negative weights efficiently. Bellman–Ford handles negative weights and detects negative cycles. Floyd–Warshall computes all-pairs shortest paths. Understanding these algorithms and their trade-offs is essential for solving real-world optimization problems.

This page presents the major shortest path algorithms, analyzing their correctness, complexity, and appropriate use cases.

Problem Formulation

Weighted Graphs

Consider a directed graph $G=(V,E)$ with a weight function
$w:E\to ℝ$ assigning a real number to each edge. The weight of a path is the sum of weights of its edges.

For vertices $u$ and $v$, the shortest-path weight is defined as the minimum weight of any path from $u$ to $v$, or infinity if no path exists:

$\delta (u,v)=\min (w\left(p\right):p\text{ is a path from }u\text{ to }v)$

Negative Weights and Cycles

Negative edge weights are allowed in some algorithms but complicate the problem. A negative-weight cycle is a cycle whose edges sum to a negative weight. If such a cycle is reachable from the source and reaches the destination, the shortest path is undefined (negative infinity).

Dijkstra algorithm requires non-negative weights. Bellman-Ford handles negative weights and detects negative cycles. Detecting and handling negative cycles is important in financial arbitrage detection.

Dijkstra Algorithm

Overview

Dijkstra algorithm, published by Edsger Dijkstra in $1959$ , solves the single-source shortest path problem for graphs with non-negative edge weights. It is the standard algorithm for route planning in road networks.

The algorithm maintains a set $S$ of vertices whose shortest paths from the source are known, and a priority queue of remaining vertices. It repeatedly extracts the vertex with minimum distance estimate, adds it to $S$, and relaxes its outgoing edges.

The Algorithm

Initialize: Set $d\left[s\right]=0$ for the source $s$, and $d\left[v\right]=\infty$ for all other vertices. Insert all vertices into a priority queue keyed by $d$ values.

Main loop: While the priority queue is not empty, extract the vertex $u$ with minimum $d\left[u\right]$. For each neighbor $v$ of $u$, if $d\left[u\right]+w(u,v)$, update $d\left[v\right]=d\left[u\right]+w(u,v)$ and decrease the key of $v$ in the queue.

The relaxation step checks if going through $u$ provides a shorter path to $v$ than the current best known path. If so, it updates the estimate.

Correctness

Dijkstra algorithm is correct because when a vertex $u$ is extracted from the queue, $d\left[u\right]$ equals the true shortest path distance. The proof is by induction: the first vertex extracted is the source with $d\left[s\right]=0$. For subsequent vertices, the non-negativity of edge weights ensures no shorter path can be found later.

This greedy choice is safe: the minimum-distance vertex in the queue cannot have its distance improved by paths through other unprocessed vertices, because those paths would have greater or equal length.

Complexity

The complexity depends on the priority queue implementation. With a binary heap, extract-min takes $O({\log }_{}n)$ and decrease-key takes $O({\log }_{}n)$. Since we perform $n$ extract-min operations and at most $m$ decrease-key operations:

$T(n,m)=O((n+m){\log }_{}n)$

With a Fibonacci heap, decrease-key is amortized $O\left(1\right)$, giving $O(m+n{\log }_{}n)$. For sparse graphs where $m=O\left(n\right)$, the complexity is $O(n{\log }_{}n)$. For dense graphs where $m=O\left(n^2\right)$, it is $O(n^2{\log }_{}n)$ with a binary heap or $O\left(n^2\right)$ with a Fibonacci heap.

Bellman-Ford Algorithm

Overview

The Bellman-Ford algorithm solves single-source shortest paths with negative edge weights and can detect negative-weight cycles. It is slower than Dijkstra but more general.

The Algorithm

Initialize: Set $d\left[s\right]=0$ for the source and $d\left[v\right]=\infty$ for all other vertices.

Main loop: Repeat $n-1$ times: for each edge $(u,v)$, relax by setting $d\left[v\right]=\min (d\left[v\right],d\left[u\right]+w(u,v))$.

Negative cycle detection: After $n-1$ iterations, perform one more pass. If any distance can still be reduced, a negative-weight cycle is reachable from the source.

Correctness

After $k$ iterations, $d\left[v\right]$ is at most the weight of any shortest path using at most $k$ edges. Since shortest paths without negative cycles have at most $n-1$ edges, $n-1$ iterations suffice.

Complexity

The algorithm performs $n-1$ passes over all $m$ edges, giving time complexity $O(nm)$. This is slower than Dijkstra but necessary when negative weights are present.

Floyd-Warshall Algorithm

Overview

Floyd-Warshall computes shortest paths between all pairs of vertices simultaneously. It uses dynamic programming and handles negative edge weights (but not negative cycles).

The Algorithm

Let d[i][j] denote the shortest path from i to j using only intermediate vertices from {1, 2, ..., k}. Initialize d[i][j] = w(i,j) if edge exists, 0 if i = j, infinity otherwise.

Let $d\left[i\right]\left[j\right]$ denote the shortest path from $i$ to $j$ using only intermediate vertices from $\{1,2,\dots ,k\}$. Initialize $d\left[i\right]\left[j\right]=w(i,j)$ if edge exists, $0$ if $i=j$, infinity otherwise.

The recurrence is: for $k$ from $1$ to $n$, for all $i$, $j$: $d\left[i\right]\left[j\right]=\min (d\left[i\right]\left[j\right],d\left[i\right]\left[k\right]+d\left[k\right]\left[j\right])$.

This considers whether the shortest path from $i$ to $j$ should go through vertex $k$. If going through $k$ is shorter, we update the distance.

Complexity

The three nested loops each run $n$ times, giving $O\left(n^3\right)$ time and $O\left(n^2\right)$ space for the distance matrix. For dense graphs, this is efficient for all-pairs shortest paths.

Negative cycles are detected if any diagonal entry $d\left[i\right]\left[i\right]$ becomes negative after the algorithm completes.

Breadth-First Search for Unweighted Graphs

When all edges have equal weight (or weight $1$), BFS finds shortest paths in $O(n+m)$ time. Starting from the source, BFS visits vertices in order of their distance from the source.

The algorithm uses a queue: enqueue the source with distance $0$. Repeatedly dequeue a vertex $u$ and enqueue all unvisited neighbors $v$ with distance $d\left[v\right]=d\left[u\right]+1$.

BFS is optimal for unweighted graphs and is the basis for more sophisticated algorithms. Many graph algorithms are variations or extensions of BFS and DFS.

A* Algorithm

A* is a heuristic search algorithm that extends Dijkstra by using an admissible heuristic $h\left(v\right)$ estimating the distance from $v$ to the target. It prioritizes vertices by $ƒ\left(v\right)=d\left[v\right]+h\left(v\right)$.

An admissible heuristic never overestimates the true distance. With such a heuristic, A* finds optimal paths while often exploring far fewer vertices than Dijkstra. For geographic routing, the Euclidean distance is a common heuristic.

A* is widely used in games, robotics, and navigation systems. The choice of heuristic trades off between optimality guarantees and computational efficiency.

Applications

Navigation and Routing

GPS systems and mapping applications use shortest path algorithms to compute driving directions. Modern systems use A* with geographic heuristics and precomputed auxiliary data structures for near-instant responses.

Network Routing

Internet routing protocols use shortest path algorithms. OSPF (Open Shortest Path First) uses Dijkstra algorithm. Each router maintains a map of the network and computes shortest paths to all destinations.

Social Network Analysis

The shortest path between users in a social network measures degrees of separation. Betweenness centrality, measuring how often a vertex lies on shortest paths between others, identifies influential network nodes.

Arbitrage Detection

In currency exchange, taking logarithms of exchange rates converts multiplication to addition. A negative cycle in this transformed graph represents an arbitrage opportunity. Bellman-Ford detects such opportunities.

Algorithm Selection Guide

• Use BFS for unweighted graphs $O(n+m)$.

• Use Dijkstra for non-negative weights $O(m{\log }_{}n)$.

• Use Bellman-Ford for negative weights or cycle detection $O(nm)$.

• Use Floyd-Warshall for all-pairs queries $O\left(n^3\right)$.

• Use A* when a good heuristic is available.

Summary

Shortest path algorithms find paths minimizing total edge weight in weighted graphs. The main variants are single-source (one source to all vertices), single-pair (specific source and target), and all-pairs (between every pair).

Dijkstra algorithm is optimal for single-source shortest paths with non-negative weights. It uses a priority queue to always process the vertex with minimum distance estimate, achieving $O(m{\log }_{}n)$ time with a binary heap.

Bellman-Ford algorithm handles negative edge weights by relaxing all edges $n-1$ times. It runs in $O(nm)$ time and can detect negative-weight cycles by checking for further improvements after $n-1$ iterations.

Floyd-Warshall computes all-pairs shortest paths using dynamic programming in $O\left(n^3\right)$ time. It builds solutions by incrementally allowing more intermediate vertices.

A* extends Dijkstra with heuristic guidance, often finding optimal paths much faster by prioritizing promising directions. BFS is optimal for unweighted graphs.

These algorithms are fundamental to navigation systems, network routing, social network analysis, and many optimization problems. Choosing the right algorithm depends on edge weight properties, graph density, and query type.