Shortest Path
Algorithms

Definition

Given a weighted directed graph G = (V, E) with weight function w: E → R and a source vertex s, find the shortest-weight path from s to every reachable vertex.

• Path weight — sum of edge weights along the path: w(p) = Σ w(vi, vi+1)
• Shortest-path weight — δ(s, v) = min { w(p) : s ⤳ v } or +∞ if unreachable
• Predecessor sub-graph — encodes the shortest-path tree rooted at s

Optimal sub-structure

Any sub-path of a shortest path is itself a shortest path. This property is the foundation for every algorithm in this deck.

Problem variants

BFS solves single-source shortest paths when every edge has weight 1. It processes vertices in order of increasing distance from the source.

from collections import deque

def bfs_shortest(graph, source):
    dist = {v: float('inf') for v in graph}
    dist[source] = 0
    prev = {v: None for v in graph}
    queue = deque([source])

    while queue:
        u = queue.popleft()
        for v in graph[u]:
            if dist[v] == float('inf'):
                dist[v] = dist[u] + 1
                prev[v] = u
                queue.append(v)
    return dist, prev

Properties

BFS is the baseline. When edges have varying weights, we need more sophisticated approaches — but for unit-weight graphs, nothing beats BFS.

def dijkstra(graph, source):
    dist = {v: float('inf') for v in graph}
    prev = {v: None for v in graph}
    dist[source] = 0
    Q = set(graph.keys())

    while Q:
        u = min(Q, key=lambda v: dist[v])
        Q.remove(u)
        for v, w in graph[u]:
            if v in Q and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
    return dist, prev

Array-based version shown for clarity — O(V²). Priority queue version on next slide.

Relaxation

The fundamental operation. For edge (u, v) with weight w:

if dist[u] + w < dist[v]:
    dist[v] = dist[u] + w
    prev[v] = u

Key constraint

Lazy deletion (practical default)

import heapq

def dijkstra(graph, source):
    dist = {v: float('inf') for v in graph}
    dist[source] = 0
    pq = [(0, source)]

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue  # stale entry
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    return dist

Practical notes

• Binary heap is the standard choice — simple, cache-friendly, fast in practice
• Fibonacci heap wins asymptotically for dense graphs (E >> V) but has high constant factors
• Lazy deletion avoids decrease-key entirely; push new (dist, v) pairs and skip stale entries on extraction
• For integer weights in range [0, C], dial's algorithm achieves O(V + E + C)

def bellman_ford(vertices, edges, source):
    dist = {v: float('inf') for v in vertices}
    dist[source] = 0

    # V-1 relaxation passes
    for _ in range(len(vertices) - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    # Negative cycle check
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            raise ValueError("Negative cycle")

    return dist

Why |V| - 1 passes?

A shortest path in a graph with |V| vertices has at most |V| - 1 edges. After pass i, all shortest paths using ≤ i edges are found.

What is a negative cycle?

A cycle whose total edge weight is negative. If reachable from s, shortest-path distances are -∞ for all vertices reachable from the cycle.

Cycle weight: 2 + (-5) + 1 = -2

Detection mechanism

After |V| - 1 relaxation passes, all shortest paths are finalized (if no negative cycle). A |V|-th pass that still finds improvements proves a negative cycle exists.

Finding the cycle

• Run the extra pass; record any vertex v that improves
• Follow prev pointers from v for |V| steps to ensure you are on the cycle
• Trace prev pointers until you revisit a vertex — that is the cycle

Applications

from collections import deque

def spfa(graph, source):
    dist = {v: float('inf') for v in graph}
    dist[source] = 0
    in_queue = {v: False for v in graph}
    in_queue[source] = True
    queue = deque([source])

    while queue:
        u = queue.popleft()
        in_queue[u] = False
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                if not in_queue[v]:
                    queue.append(v)
                    in_queue[v] = True
    return dist

SPFA is popular in competitive programming for its simplicity and good average-case performance. In production systems, Dijkstra with a binary heap is preferred for non-negative weights.

from collections import deque

def dag_shortest(graph, source):
    # Kahn's topological sort
    in_deg = {v: 0 for v in graph}
    for u in graph:
        for v, w in graph[u]:
            in_deg[v] += 1
    queue = deque(v for v in graph if in_deg[v] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v, w in graph[u]:
            in_deg[v] -= 1
            if in_deg[v] == 0:
                queue.append(v)

    # Relax in topological order
    dist = {v: float('inf') for v in graph}
    dist[source] = 0
    for u in order:
        if dist[u] < float('inf'):
            for v, w in graph[u]:
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
    return dist

Why it works

In topological order, all predecessors of v are processed before v. When we relax edges from u, dist[u] is already optimal.

Applications

• Critical path analysis — negate weights; shortest = longest in original
• Project scheduling — PERT/CPM networks are DAGs
• Dynamic programming — many DP problems are shortest paths in an implicit DAG

def floyd_warshall(n, edges):
    INF = float('inf')
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

Recurrence

distk(i, j) = min( distk-1(i, j), distk-1(i, k) + distk-1(k, j) )

At step k, consider whether routing through vertex k improves the path from i to j.

Floyd-Warshall is ideal for dense graphs with small V. For sparse graphs, running Dijkstra from every vertex is faster: O(V · E log V).

Core idea

Prioritise vertices by f(v) = g(v) + h(v):

• g(v) — actual cost from source to v
• h(v) — estimated cost from v to goal (the heuristic)
• f(v) — estimated total cost of the cheapest path through v

import heapq

def a_star(graph, source, goal, h):
    g = {source: 0}
    prev = {}
    open_set = [(h(source), source)]

    while open_set:
        f_val, u = heapq.heappop(open_set)
        if u == goal:
            return reconstruct(prev, goal), g[goal]
        for v, w in graph[u]:
            tentative = g[u] + w
            if tentative < g.get(v, float('inf')):
                g[v] = tentative
                prev[v] = u
                heapq.heappush(open_set, (tentative + h(v), v))
    return None, float('inf')

Relationship to Dijkstra

A* explores a focused cone toward the goal; Dijkstra explores a full circle.

Admissible heuristic

A heuristic h is admissible if it never overestimates: h(v) ≤ δ(v, goal) for all v. Admissibility guarantees A* finds the optimal path.

Consistent (monotone) heuristic

h is consistent if h(u) ≤ w(u,v) + h(v) for every edge (u,v). Consistency implies admissibility and ensures each vertex is expanded at most once.

The trade-off

• h = 0 — Dijkstra; explores everything; always optimal
• h = δ — perfect heuristic; A* goes straight to the goal
• h > δ — inadmissible; faster but may return sub-optimal paths
• Stronger admissible heuristics explore fewer vertices but cost more to compute

Common heuristics for grids

Unweighted (bidirectional BFS)

• Alternate layers between forward and backward BFS
• Terminate when a vertex appears in both visited sets
• Shortest path passes through the meeting vertex

Weighted (bidirectional Dijkstra)

• Run forward and backward Dijkstra simultaneously
• Alternate extract-min between the two queues
• Maintain best known path μ = min(distf[v] + distb[v])
• Terminate when both fronts exceed μ

Performance

Where b = branching factor, d = shortest path length.

Requires knowing the target and being able to traverse edges in reverse.

Road network routing

GPS navigation: preprocess the road graph with contraction hierarchies or A* with landmark heuristics. Real-time traffic requires dynamic edge weights and partial re-computation.

Telecommunications

• Minimum-cost routing in telephone switching networks
• Optical network path computation (GMPLS)
• Fibre-optic cable laying — shortest path through geographic terrain

Network routing protocols

Key takeaways

• Shortest-path problems have optimal sub-structure — every sub-path of a shortest path is itself shortest
• Dijkstra is the workhorse for non-negative weights; binary heap + lazy deletion is the practical default
• Bellman-Ford handles negative weights at the cost of O(VE); its extra pass detects negative cycles
• Floyd-Warshall solves all-pairs in O(V³) — ideal for dense graphs with small vertex counts
• Johnson's beats Floyd-Warshall on sparse graphs by reweighting to eliminate negatives
• A* focuses search with a heuristic; admissibility guarantees optimality
• Contraction hierarchies make continental-scale routing feasible in microseconds
• The choice of algorithm depends on graph structure, weight constraints, and query type

Recommended reading