Fundamentals of Shortest Path Problem

Shortest Path Problem: Definition and Algorithms What is the Shortest Path Problem? The shortest path problem asks a fundamental question: given a graph with weighted edges, what is the minimum-weight path connecting two vertices? The goal is to find a path where the sum of all edge weights along that path is as small as possible. Consider the graph shown below as an example. If we want to travel from vertex A to vertex F with minimum total distance, we need to find which sequence of edges creates the lowest total weight. The problem is straightforward to state but computationally interesting because the number of possible paths can be exponential, making brute force infeasible for large graphs. Key Distinctions: Directed vs. Undirected Graphs In an undirected graph, each edge can be traversed in either direction. Think of a road connecting two cities—you can travel in both directions. In a directed graph, each edge (called an arc) has a direction that must be followed. Think of a one-way street—you can only travel in the designated direction. This distinction matters because it affects which paths are even valid. In the example graph above, the edges have specific directions indicated by arrows, so we must respect those directions when finding paths. Understanding Path Length A path of length k consists of exactly k consecutive edges that connect a sequence of vertices. Note that "length" here refers to the number of edges, not their weights. When all edges have weight 1 (called unit weights), the shortest path is simply the path with the fewest edges. This special case is important because it allows efficient solutions using simpler algorithms like breadth-first search. Problem Variants The "shortest path problem" actually encompasses several related but distinct problems. Understanding which variant you're solving is crucial: Single-Source Shortest Path Single-source shortest path finds the shortest paths from one designated source vertex to every other vertex in the graph. Once you solve this, you know the shortest path from the source to any destination. Example: If you're at vertex A and want to know the shortest distance to reach any other vertex in the graph, you're solving a single-source problem. This is the most commonly solved variant because many other problems reduce to it. Single-Destination Shortest Path Single-destination shortest path finds shortest paths from every vertex to one designated destination vertex. However, there's a clever trick: you can solve this by reversing all edge directions in a directed graph and then solving the single-source problem from the destination. So this variant isn't fundamentally different—it's just solved using the same algorithms applied to the reversed graph. All-Pairs Shortest Path All-pairs shortest path requires finding the shortest path between every pair of vertices in the graph. Instead of one source, you need shortest paths for all possible (source, destination) pairs. Example: If you're building a travel guide and need to know the shortest route between every pair of cities, you're solving an all-pairs problem. Algorithms for Shortest Paths Different algorithms suit different situations. The right choice depends on the graph structure and edge weights. Dijkstra's Algorithm: The Workhorse Dijkstra's algorithm is the most widely-used shortest path algorithm. It solves the single-source shortest path problem efficiently, but with one important requirement: all edge weights must be non-negative. The algorithm works by repeatedly selecting the unvisited vertex with the smallest known distance and updating the distances to its neighbors. This greedy approach is optimal because negative edge weights could cause "shortcuts" that violate the greedy choice. When to use it: Your graph has non-negative edge weights and you need shortest paths from one source vertex. Bellman-Ford Algorithm: Handling Negative Weights Bellman-Ford algorithm solves the single-source shortest path problem and handles negative edge weights—something Dijkstra cannot do. More powerfully, Bellman-Ford can detect negative cycles (cycles whose total weight is negative). If a negative cycle exists on a path to the destination, the shortest path is technically undefined, because you could traverse the cycle repeatedly to arbitrarily decrease the path length. The trade-off is runtime: Bellman-Ford is slower than Dijkstra, making it less suitable when edge weights are non-negative and you know no negative cycles exist. When to use it: You have negative edge weights or need to detect negative cycles. Floyd-Warshall Algorithm: All-Pairs Solution Floyd-Warshall algorithm solves the all-pairs shortest path problem. Unlike single-source algorithms that you run repeatedly, Floyd-Warshall computes all shortest paths in one execution. The algorithm builds up solutions by considering progressively more intermediate vertices. Its cubic time complexity ($O(V^3)$) is particularly efficient for dense graphs where the number of edges is close to $V^2$. When to use it: You need shortest paths between all pairs of vertices and your graph is dense. Breadth-First Search: Unit Weights When all edge weights equal 1, breadth-first search (BFS) finds shortest paths in linear time ($O(V + E)$). This is simpler and faster than Dijkstra because the uniform weight eliminates the need for a priority queue. BFS explores vertices in "layers" from the source, naturally finding shortest paths because it visits each vertex at minimum distance before moving farther away. When to use it: Your edges all have weight 1 (or equivalent unweighted graphs). <extrainfo> Additional Algorithms A Search A search solves the single-pair shortest path problem (finding the path between just two specific vertices, not all pairs). It uses an admissible heuristic—an estimate of distance to the destination that never overestimates—to guide the search intelligently. By preferring vertices that appear closer to the goal, A can be much faster than exploring blindly. This algorithm is popular in games and robotics where you want efficient pathfinding with good intuitive direction. However, it requires domain knowledge to design a good heuristic. Johnson's Algorithm Johnson's algorithm solves all-pairs shortest paths on sparse graphs efficiently. It uses edge reweighting to transform the problem: it adds weights to edges so that all weights become non-negative without changing actual shortest paths. Then it runs Dijkstra from each vertex. This hybrid approach leverages the best properties of both algorithms: Dijkstra's efficiency on non-negative weights and systematic all-pairs computation. Topological-Order Algorithm For directed acyclic graphs (DAGs) specifically, there exists a specialized algorithm that solves single-source shortest paths in linear time $\Theta(V + E)$ by processing vertices in topological order. Since DAGs have no cycles, you can safely process vertices in an order where all predecessors are handled before each vertex, making dynamic programming straightforward. Viterbi Algorithm The Viterbi algorithm solves a probabilistic variant where each node carries an additional weight, typically representing probability. It's used in hidden Markov models and speech recognition rather than standard graphs. </extrainfo>