Shortest path problem - Extended Topics and Applications

Related Concepts and Advanced Applications of Shortest Paths Introduction Shortest path algorithms have numerous important extensions and real-world applications. In this section, we'll explore how shortest paths are used to solve network flow problems, examine variations of the shortest path problem, and understand why some variants become much harder computationally. Shortest-Path Trees A shortest-path tree is a fundamental concept that emerges from shortest path algorithms. Given a source vertex, a shortest-path tree is a spanning tree rooted at that source vertex such that the unique path from the source to any other vertex in the tree is a shortest path in the original graph. In other words, if you run Dijkstra's algorithm or BFS from a source vertex, the edges you use to reach each vertex for the first time form a shortest-path tree. This tree is useful because it captures all shortest paths from the source simultaneously in a compact structure. Example: In the graph shown, if we run a shortest path algorithm from vertex A, the edges that form the first shortest paths to each vertex would constitute the shortest-path tree rooted at A. Network Flow Augmentation Using Shortest Paths One of the most important applications of shortest path algorithms is solving network flow problems. In particular, shortest paths can help us find the optimal way to push flow through a network. The Setup In a network flow problem, we have: A directed graph with weighted edges representing capacities A source vertex (where flow originates) and a sink vertex (where flow terminates) A goal to push the maximum possible flow from source to sink The Residual Graph The key innovation is the residual graph. For each edge in the original graph: Add a forward edge with capacity equal to the original edge's capacity Add a backward edge with capacity initially set to zero These backward edges are crucial—they represent the ability to "undo" flow we've previously sent, which allows us to reroute flow and find better solutions. The Augmentation Process Here's how shortest paths solve the flow problem: Find an augmenting path: Use a shortest path algorithm (or any path-finding algorithm) to find a path from source to sink in the current residual graph. Determine the bottleneck: Calculate the minimum residual capacity along this path. This is the maximum amount of flow we can push along this particular path without exceeding any edge's capacity. Update the flow: Increase flow along the path by this bottleneck amount. This means: Decrease the forward edge capacity by the bottleneck amount Increase the backward edge capacity by the same amount (to allow undoing this flow later) Repeat: Continue finding augmenting paths and updating flow until no path remains from source to sink in the residual graph. When this process terminates, you have found the maximum flow possible from source to sink. The algorithm is elegant because it automatically handles rerouting—the backward edges ensure that if a better path is found later, we can reduce flow on previously used edges. <extrainfo> Related Variations: Bidirectional Search and K-Shortest Paths Bidirectional search is a technique that can speed up shortest path finding. Instead of expanding outward from only the source vertex, bidirectional search simultaneously expands from both the source and the target vertex. When the two search frontiers meet, you've found a shortest path. This can significantly reduce the search space, though it requires careful handling to ensure the path found is actually optimal. K-shortest paths is the problem of finding not just one shortest path, but the $k$ best alternative shortest paths. This is useful in applications where you want backup routes (network routing), alternative plans (transportation), or redundancy (reliability). While finding the single shortest path is polynomial, finding multiple shortest paths can be more complex depending on how you count and eliminate path variations. </extrainfo> Constrained Shortest Path Problems and Computational Complexity The unconstrained shortest path problem—finding the path with minimum total weight—can be solved efficiently in polynomial time using Dijkstra's or Bellman-Ford algorithms. However, adding even simple constraints can make the problem dramatically harder. Secondary Metric Constraints If you add a constraint on a secondary metric, the problem becomes NP-complete. For example: Shortest path with budget: Find the path from source to target with minimum distance, but the total cost must not exceed a given budget. Shortest path with time windows: Find the shortest path where you must reach certain vertices by specific times. These problems are NP-complete, meaning there's no known polynomial-time algorithm to solve them optimally. You either need to accept exponential running time or use approximation/heuristic methods that may not find the true optimum. <extrainfo> Visiting Required Vertices If you require a shortest path to visit a specified set of vertices (in any order), this is equivalent to the Traveling Salesman Problem (TSP), which is also NP-complete. The TSP is one of the most famous hard problems in computer science. The Longest Path Problem Finding the longest path in a graph (rather than shortest) is also NP-complete. This might seem surprising—after all, shouldn't the opposite of an easy problem be easy? But longest paths are genuinely hard because they can be viewed as related to Hamiltonian paths, which are NP-complete. </extrainfo>