Shortest Paths — Compute shortest paths conceptually and with basic algorithms (intro)

Historical Context & Motivation

The problem of finding the shortest path through a network is one of the most fundamental questions in discrete mathematics and computer science. While humans have intuitively optimized routes for millennia—ancient trade routes, Roman road networks, and postal systems all reflect an instinctive drive to minimize travel cost—the formal mathematical treatment of shortest-path problems only crystallized in the twentieth century alongside the rise of graph theory and operations research. The urgency of wartime logistics and the advent of digital computers created a fertile environment for researchers to develop algorithms that could efficiently solve routing problems on networks with thousands or even millions of nodes.

The story of shortest-path algorithms is intertwined with the broader development of combinatorial optimization. Leonhard Euler's 1736 solution to the Königsberg bridge problem established graph theory as a discipline, but it was the demands of twentieth-century infrastructure—telephone routing, airline scheduling, and military supply chains—that drove the creation of practical shortest-path algorithms. These algorithms remain indispensable today, powering everything from GPS navigation to internet packet routing and social-network analysis.

The central question these developments address is deceptively simple: given a network of locations connected by paths of varying costs, what is the least-cost route between two specified locations? Answering this question rigorously requires a formal vocabulary of vertices, edges, and weights, as well as systematic algorithmic strategies—topics we develop in the sections that follow.

Core Principles & Definitions

Before tackling algorithms, we must establish the formal language of weighted graphs. A weighted graph G = (V, E, w) consists of a set V of vertices (also called nodes), a set E of edges connecting pairs of vertices, and a weight function w : E → ℝ that assigns a numerical cost (distance, time, price, etc.) to each edge. A path in G is a sequence of vertices v₁, v₂, …, vₖ where each consecutive pair (vᵢ, vᵢ₊₁) is an edge in E. The length (or cost) of a path is the sum of the weights of its constituent edges.

Visual Explanation — A Weighted Graph

The diagram below presents a small weighted graph with six vertices (A through F) and nine edges. Each edge is labeled with its weight. The highlighted path from A to F illustrates the shortest route, whose total cost is 9. Notice that this path does not necessarily use the fewest edges; the shortest path by edge count (A → B → F, with two edges) has a total weight of 14, which is suboptimal. This underscores a crucial distinction: shortest path refers to minimum total weight, not minimum number of edges.

In the diagram, vertex A serves as the source and vertex F is the destination. The cyan path A → C → E → F achieves a total cost of 2 + 3 + 4 = 9, which is strictly less than every other A-to-F path. Observe that the path passes through three edges and four vertices; a different path, A → B → F, uses only two edges but carries a total weight of 14. The key lesson is that greedy choices on individual edges do not guarantee global optimality—the cheapest first step from A leads to C (weight 2), and continuing greedily from C leads to E (weight 3), then E to F (weight 4). In this particular instance, the greedy heuristic happens to yield the shortest path, but in general, a systematic algorithm is required.

Mathematical Framework

We now formalize the shortest-path problem and introduce the two most important introductory algorithms: Dijkstra's algorithm for graphs with non-negative weights and a brief look at the Bellman–Ford algorithm for more general cases. Both algorithms rely on the principle of relaxation and optimal substructure described earlier.

Dijkstra's Algorithm Outline

Dijkstra's algorithm maintains a set S of vertices whose shortest distances from the source are finalized, and a priority queue Q of remaining vertices keyed by tentative distances. Initially, d[s] = 0 and d[v] = ∞ for all v ≠ s. At each iteration, the vertex u with the smallest tentative distance is extracted from Q and added to S. Then, for every neighbor v of u, the edge (u, v) is relaxed. The process repeats until Q is empty. Because each extraction is provably optimal (a consequence of non-negative weights), the algorithm correctly computes δ(s, v) for every vertex v.

Bellman–Ford Algorithm Outline

The Bellman–Ford algorithm is simpler but slower. It initializes d[s] = 0 and d[v] = ∞ for v ≠ s, then performs |V| − 1 passes over every edge, relaxing each one. After |V| − 1 rounds, all shortest-path distances are finalized. A final (|V|-th) pass checks for negative-weight cycles: if any edge can still be relaxed, a negative cycle exists and no finite shortest path is defined. The running time is O(|V| × |E|), which is slower than Dijkstra's but handles negative edge weights.

Detailed Breakdown — Tracing Dijkstra's Algorithm

To solidify understanding, let us trace Dijkstra's algorithm step by step on the graph from Section 3. We seek the shortest path from vertex A (the source) to every other vertex. The diagram below captures the state of the distance labels and finalized set after each extraction.

Each iteration of the algorithm extracts the vertex with the smallest tentative distance from the priority queue and finalizes it. In iteration 1, we extract A (distance 0) and relax edges to B (d[B] updated to 7) and C (d[C] updated to 2). In iteration 2, C is extracted at distance 2, and relaxation reaches E (d[E] = 2 + 3 = 5) and B (no improvement since 2 + 6 = 8 > 7). The process continues until every vertex is finalized. The total cost to reach F is confirmed as δ(A, F) = 9, achieved via the path A → C → E → F.

Worked Example — Finding the Shortest Path

Consider a new graph with five cities connected by roads of varying lengths. We wish to find the shortest path from city S to city T using Dijkstra's algorithm. The edges and weights are: S–A (4), S–B (1), A–B (2), A–C (5), B–A (1), B–C (8), C–T (3), A–T (12).

Strengths, Limitations & Algorithm Comparisons

No single shortest-path algorithm dominates in all scenarios. The choice of algorithm depends on the structure of the graph (sparse vs. dense), the presence or absence of negative edge weights, and whether you need shortest paths from one source or between all pairs of vertices. The table below compares the three foundational algorithms introduced in this lesson.

Connection to Advanced Theory

The introductory algorithms covered here form the foundation for a rich ecosystem of advanced shortest-path techniques. As networks grow to billions of nodes—think continental road maps or the global internet—vanilla Dijkstra becomes impractical, motivating sophisticated extensions. Understanding the basic versions equips you to appreciate the design rationale behind these more powerful tools.

In subsequent coursework you may encounter these extensions, particularly A* search in artificial intelligence and network flow problems in operations research, which generalize shortest paths to find maximum throughput in capacitated networks. The same principles of relaxation, optimal substructure, and systematic exploration underpin all of these methods. Mastering Dijkstra's and Bellman–Ford provides the conceptual scaffolding on which every advanced routing algorithm is built.

Practice Problems

Lesson Summary