5 min read
On this page

Shortest Paths

Finding the shortest (minimum-weight) path between vertices in a weighted graph. One of the most practically important graph problems.

Single-Source Shortest Paths

Dijkstra's Algorithm

For graphs with non-negative edge weights. Greedy: always process the closest unvisited vertex.

FUNCTION DIJKSTRA(graph, source)
    n ← number of vertices
    dist ← array of size n, all set to INFINITY
    dist[source] ← 0
    heap ← MIN_HEAP containing (0, source)

    WHILE heap is not empty
        (d, u) ← EXTRACT_MIN(heap)
        IF d > dist[u] THEN CONTINUE
        FOR EACH (v, w) IN neighbors of u
            new_dist ← d + w
            IF new_dist < dist[v]
                dist[v] ← new_dist
                INSERT (new_dist, v) INTO heap
    RETURN dist

| Implementation | Time | |---|---| | Array (no heap) | O(V²) | | Binary heap | O((V + E) log V) | | Fibonacci heap | O(E + V log V) |

Binary heap is standard for sparse graphs. Array for dense graphs (E ≈ V²).

Cannot handle negative edges: Dijkstra assumes a processed vertex has its final distance. Negative edges can invalidate this.

Bellman-Ford Algorithm

Handles negative edge weights. Detects negative cycles.

FUNCTION BELLMAN_FORD(edges, n, source)
    dist ← array of size n, all set to INFINITY
    dist[source] ← 0

    // Relax all edges V-1 times
    FOR iteration ← 1 TO n - 1
        FOR EACH (u, v, w) IN edges
            IF dist[u] ≠ INFINITY AND dist[u] + w < dist[v]
                dist[v] ← dist[u] + w

    // Check for negative cycles (V-th relaxation)
    FOR EACH (u, v, w) IN edges
        IF dist[u] ≠ INFINITY AND dist[u] + w < dist[v]
            RETURN NONE   // negative cycle reachable from source
    RETURN dist

Time: O(VE). Space: O(V).

Negative cycle detection: If any distance decreases on the V-th iteration, a negative cycle exists.

SPFA (Shortest Path Faster Algorithm)

An optimization of Bellman-Ford using a queue. Only relax edges from vertices whose distance has recently decreased.

FUNCTION SPFA(graph, source)
    n ← number of vertices
    dist ← array of size n, all set to INFINITY
    in_queue ← array of size n, all false
    count ← array of size n, all 0   // for negative cycle detection
    dist[source] ← 0
    queue ← empty queue
    ENQUEUE(queue, source)
    in_queue[source] ← true

    WHILE queue is not empty
        u ← DEQUEUE(queue)
        in_queue[u] ← false
        FOR EACH (v, w) IN neighbors of u
            IF dist[u] + w < dist[v]
                dist[v] ← dist[u] + w
                IF NOT in_queue[v]
                    ENQUEUE(queue, v)
                    in_queue[v] ← true
                    count[v] ← count[v] + 1
                    IF count[v] ≥ n THEN RETURN NONE   // negative cycle
    RETURN dist

Average time: O(E) in practice (much faster than Bellman-Ford). Worst case: O(VE) (same as Bellman-Ford).

All-Pairs Shortest Paths

Floyd-Warshall

Dynamic programming over intermediate vertices. Finds shortest paths between all pairs.

PROCEDURE FLOYD_WARSHALL(dist)
    n ← number of vertices
    FOR k ← 0 TO n - 1
        FOR i ← 0 TO n - 1
            FOR j ← 0 TO n - 1
                IF dist[i][k] ≠ INFINITY AND dist[k][j] ≠ INFINITY
                    dist[i][j] ← MIN(dist[i][j], dist[i][k] + dist[k][j])

Time: O(V³). Space: O(V²).

Recurrence: dist[i][j] using intermediates {0,...,k} = min(dist[i][j] using {0,...,k-1}, dist[i][k] + dist[k][j]).

Negative cycle detection: If dist[i][i] < 0 for any i after the algorithm.

Path reconstruction: Maintain a predecessor matrix next[i][j]. The shortest path from i to j goes through next[i][j].

Johnson's Algorithm

All-pairs shortest paths for sparse graphs (better than Floyd-Warshall when E ≪ V²).

  1. Add a new vertex s connected to all vertices with weight 0.
  2. Run Bellman-Ford from s to get potentials h[v].
  3. Reweight: w'(u,v) = w(u,v) + h[u] - h[v]. All reweighted edges are non-negative!
  4. Run Dijkstra from each vertex using reweighted edges.
  5. Recover original distances: dist[u][v] = dist'[u][v] - h[u] + h[v].

Time: O(VE + V² log V) with Fibonacci heap Dijkstra. Better than O(V³) when E = O(V).

Special Cases

DAG Shortest Path

For directed acyclic graphs: topological sort, then relax edges in order.

FUNCTION DAG_SHORTEST_PATH(graph, source)
    n ← number of vertices
    order ← TOPOLOGICAL_SORT(graph)
    dist ← array of size n, all set to INFINITY
    dist[source] ← 0

    FOR EACH u IN order
        IF dist[u] = INFINITY THEN CONTINUE
        FOR EACH (v, w) IN neighbors of u
            dist[v] ← MIN(dist[v], dist[u] + w)
    RETURN dist

Time: O(V + E). Works with negative edges (no cycles in a DAG).

Applications: Critical path analysis (project scheduling), longest path in DAG (negate weights).

0-1 BFS

When edge weights are only 0 or 1. Use a deque instead of a priority queue:

  • Weight-0 edge: push to front of deque.
  • Weight-1 edge: push to back of deque.

Time: O(V + E). Like BFS but for 0-1 weighted graphs.

Informed search using a heuristic function h(v) estimating the distance from v to the goal.

f(v) = g(v) + h(v)

where g(v) = distance from source to v, h(v) = heuristic estimate to goal.

Process vertices in order of f(v) (using a priority queue).

Admissible heuristic: h(v) ≤ actual distance to goal. Guarantees optimal solution.

Consistent heuristic: h(u) ≤ w(u,v) + h(v). Guarantees optimal solution without reopening vertices.

Examples of heuristics:

  • Grid with 4-directional movement: Manhattan distance.
  • Grid with 8-directional: Chebyshev distance.
  • Euclidean space: Straight-line distance.
  • Road networks: Great-circle distance.

A = Dijkstra + heuristic guidance*. Without heuristic (h = 0): reduces to Dijkstra.

k-Shortest Paths (Yen's Algorithm)

Find the k shortest simple paths from s to t.

  1. Find the shortest path P₁ using Dijkstra.
  2. For i = 2 to k:
    • For each edge in P_{i-1}, temporarily remove it and find the shortest path.
    • The best of these "spur paths" becomes Pᵢ.

Time: O(kV(V log V + E)). Practical for small k.

Contraction Hierarchies

Preprocessing technique for fast shortest-path queries on road networks.

Preprocessing:

  1. Order vertices by "importance" (various heuristics).
  2. Contract vertices in order: for each contracted vertex v, add a shortcut edge between neighbors u and w if the shortest path u→v→w has no shorter alternative.

Query: Bidirectional Dijkstra on the augmented graph, only relaxing edges going "upward" in the hierarchy.

Performance: Preprocessing: minutes to hours. Query: microseconds (for continental road networks with millions of vertices). Used by OSRM, Google Maps, etc.

Comparison

| Algorithm | Graph Type | Negative Edges | Time | |---|---|---|---| | BFS | Unweighted | N/A | O(V + E) | | Dijkstra (binary heap) | Non-negative | No | O((V+E) log V) | | Bellman-Ford | Any | Yes (detects neg. cycles) | O(VE) | | SPFA | Any | Yes | O(E) average, O(VE) worst | | DAG shortest path | DAG | Yes | O(V + E) | | Floyd-Warshall | Any (all-pairs) | Yes | O(V³) | | Johnson | Sparse (all-pairs) | Yes | O(VE + V² log V) | | A* | Non-negative + heuristic | No | O(E) best, O(V log V) typical |

Applications in CS

  • GPS navigation: Dijkstra/A* with contraction hierarchies on road networks. Real-time routing with traffic.
  • Network routing: OSPF (link-state, Dijkstra), RIP (distance-vector, Bellman-Ford), BGP.
  • Social networks: Shortest path = degrees of separation.
  • Games: Pathfinding (A* on grids, navigation meshes). NPC movement.
  • Robotics: Motion planning (graph search in configuration space).
  • Compiler optimization: Shortest/longest path in control flow graph for scheduling.
  • Arbitrage detection: Negative cycle in currency exchange graph (log-transformed weights).