Shortest Path Algorithm
1. Overview
A. Definition
A Shortest Path Algorithm is a collective term for algorithms that find, among the many paths connecting a source vertex and a destination vertex in a weighted graph, the path whose sum of edge weights is minimal. It is divided into Single-Source, Single-Pair, and All-Pairs problems and is implemented on top of two design strategies: Greedy and Dynamic Programming (DP).
The shortest path problem is the mathematical abstraction of the universal question "what is the cheapest way to get from A to B?" Here "cheapness" can be any measure—distance, time, cost, delay, reliability—and once maps, road networks, communication networks, and process flows are modeled as nodes and weighted edges, they are solved by the same algorithm. Navigation route guidance, path decisions in Internet routing protocols, movement of game characters, and logistics delivery optimization are all variants of this one problem, which is why shortest path is regarded as the topic of greatest practical value in graph theory.
The core principles of shortest path algorithms are optimal substructure and relaxation. Optimal substructure is the property that "any intermediate segment contained in the shortest path from source to destination is itself a shortest path," meaning the solution of a large problem is composed of solutions to smaller problems. Relaxation is the operation of "updating the distance estimate to a destination vertex known so far whenever a shorter path is found," and every shortest path algorithm is ultimately distinguished by the order in which, and the number of times, it performs relaxation. As these two principles are implemented through the differing strategies of Greedy (once fixed, never revisited) and DP (systematically updating all cases), the characteristics and constraints of each algorithm diverge.
B. Background and Necessity
For an unweighted graph, breadth-first search (BFS) alone can obtain the shortest path by edge count. However, real connection networks have different distances, elapsed times, tolls, and line delays for each segment, so weights are indispensable. A path is not fast merely because it passes through fewer vertices, since a single edge can exceed the sum of dozens of others. At this point BFS reveals its limits, and a dedicated algorithm that compares and relaxes cumulative cost while accounting for weights is required.
Moreover, real problems have such diverse weight properties and query forms that no single algorithm can cover them all. There are cases where all weights are positive, as in a road network, but there are also cases where negative (−) weights exist, as in currency arbitrage or a cost network including subsidies. Sometimes everything from one source to all destinations must be obtained at once, and sometimes the distances between all vertex pairs must be precomputed. Thus, since the appropriate algorithm differs according to "whether negative edges are allowed, whether negative cycle detection is needed, whether the query is single-source or all-pairs, and whether the graph is sparse or dense," a professional engineer must accurately identify the problem's conditions and have the discernment to choose the right tool among Dijkstra, Bellman-Ford, Floyd-Warshall, and A</strong>*.
2. Classification of Shortest Path Problems and the Relaxation Principle
Shortest path problems are divided into three types by query scope. Single-Source Shortest Path (SSSP) obtains the shortest distances from one source vertex to all remaining vertices, with Dijkstra and Bellman-Ford being representative. Single-Pair Shortest Path requires only a specific source-destination pair; since its general solution is identical to SSSP, one usually solves SSSP and terminates upon reaching the destination, or uses A* to focus the search only in the destination's direction. All-Pairs Shortest Path (APSP) obtains the distances between all vertex pairs, with Floyd-Warshall being typical.
flowchart TB
ROOT["Shortest Path Algorithm"] --> SSSP["Single-Source (SSSP)"]
ROOT --> APSP["All-Pairs (APSP)"]
SSSP --> DIJ["Dijkstra (greedy, no negative edges)"]
SSSP --> BF["Bellman-Ford (DP, negative edge/cycle detection)"]
SSSP --> ASTAR["A* (heuristic-based destination focus)"]
APSP --> FW["Floyd-Warshall (DP, all pairs)"]
APSP --> JOHN["Johnson (APSP for sparse graphs)"]
Along with this classification, it should also be noted that if a graph has no weights at all (or all edges have equal cost), the above algorithms are unnecessary. In that case breadth-first search (BFS) provides the shortest path by edge count in O(V+E), so weighted algorithms are justified only "when each edge has a different cost." In practice, variants with a mix of "unit-distance edges and weighted edges" (0-1 BFS, Dijkstra reductions) also appear; accurately grasping the problem's weight structure and choosing the simplest yet correct tool is the starting point for avoiding over-engineering.
The common operation running through all algorithms is Edge Relaxation. Each vertex v has a tentative shortest distance dist[v] from the source, initially 0 for the source alone and infinity (∞) for the rest. Letting the weight of edge (u, v) be w, relaxation is the simple compare-and-update: "if dist[u] + w < dist[v], reduce dist[v] to dist[u] + w and record v's predecessor as u." By also recording the predecessor, one can reconstruct the actual path by backtracking after arrival. In the end, Dijkstra is the greedy order of "increasing the set of distance-finalized vertices one at a time and relaxing only around them," Bellman-Ford is the exhaustive order of "relaxing all edges repeatedly V−1 times," and Floyd-Warshall is the DP order of "widening the set of allowable intermediate vertices one at a time and relaxing all pairs"; in this sense, the three algorithms can be understood as variations that perform the same relaxation on different schedules.
flowchart LR
U["vertex u: dist=5"] -- "w=3" --> V["vertex v: dist=10"]
V --> CHK{"Is dist[u]+w = 8 less than dist[v] = 10?"}
CHK -->|"Yes"| UPD["update dist[v]=8, prev[v]=u"]
CHK -->|"No"| KEEP["no update, keep existing path"]
3. Greedy-Based: Dijkstra's Algorithm
Dijkstra's algorithm, proposed by Edsger Dijkstra in 1959, is a single-source shortest path algorithm that works on graphs where all edge weights are non-negative (0 or greater). Its core strategy is greedy. It repeats, until all vertices are finalized, the process of "picking one not-yet-finalized vertex with the smallest tentative distance from the source, finalizing that distance, and relaxing the edges incident to that vertex."
The reason this greedy choice is correct lies in the premise of non-negative weights. Consider the vertex u with the minimum tentative distance among currently unfinalized vertices; for another path to reach u more shortly, that path would necessarily have to pass through some vertex with a larger tentative distance than u. But since edge weights are not negative, routing back to u via a farther vertex never reduces the distance. Therefore u's current tentative distance is already the final shortest distance, and a once-finalized vertex need never be updated again. This very "not looking back" produces greedy efficiency, but it is also the root of the fatal limitation that it yields wrong answers when it encounters negative edges, as the premise breaks. With negative edges, a path that "detours farther and then reduces distance via a negative edge" becomes possible, so an already-finalized value can be wrong.
Why Dijkstra fails with negative edges is confirmed by a simple counterexample. Suppose for vertices S·A·B the edges are S→A=1, S→B=4, A→B=−3. Dijkstra, in the first step, finalizes S and then tries to finalize A (1), with its smaller tentative distance, before B (4); but before that, B's tentative distance has been set to dist[B]=4. Later, finalizing A and relaxing A→B should update B to 1+(−3)=−2, yet if the order had finalized B before A, this shorter path would be missed. Indeed, in more complex graphs, situations arise where a negative edge later further reduces an "already-finalized vertex," making the finalized value wrong—this is the fundamental reason negative edges must never be used with Dijkstra. Incidentally, the idea "why not just add a large constant to all weights to make them positive?" is incorrect, because paths contain different numbers of edges, so the amount of the constant added differs, which changes the ranking of the shortest paths.
Let us follow the concrete operation with a small example. Consider vertices S (source)·A·B·C·T (destination) with edges S→A=4, S→B=1, B→A=2, B→C=5, A→C=1, C→T=3. Initially dist[S]=0 and the rest are ∞. In the first step, we finalize S (0), with the minimum tentative distance, and relaxing S's edges gives dist[A]=4, dist[B]=1. Next, we finalize B (1), the minimum among the unfinalized, and relaxing gives, via B→A, 1+2=3 < 4, so dist[A]=3 decreases, and via B→C, dist[C]=6. Then finalizing A (3) and via A→C, 3+1=4 < 6, so dist[C]=4 is updated. Then finalizing C (4), via C→T we get dist[T]=7, and finalizing the last T (7) terminates. The shortest path is reconstructed by backtracking the predecessor array as S→B→A→C→T (cost 7). As this example shows, a once-finalized vertex (S·B·A·C) never decreases again thereafter, and this invariant sustains the correctness of the greedy approach.
Performance hinges on the data structure that finds the minimum-distance vertex among the unfinalized. A simple array scanning linearly each time gives O(V²), while using a priority queue (min-heap) handles each distance update at relaxation in O(log V), improving the whole to O((V + E) log V). In a sparse graph with many vertices but few edges, the heap-based approach is greatly advantageous, whereas in a dense graph with edges near the square of vertices, a simple array may actually be better. Using a Fibonacci heap lowers it theoretically to O(E + V log V), but its large constant makes the binary heap the standard in practice. In heap-based implementations a single vertex may enter the queue multiple times, and the 'lazy deletion' approach—skipping an already-finalized vertex when it is popped again from the queue—is widely used for its simple implementation.
A representative industrial application is the OSPF (Open Shortest Path First) routing protocol. OSPF, using a Link-State approach, has each router share the entire network topology and then run Dijkstra (SPF, Shortest Path First) with itself as root to compute the optimal path to each destination. For example, by converting line bandwidth into cost and assigning a higher cost to a 100 Mbps link than to a 1 Gbps link, one can make Dijkstra naturally prefer high-bandwidth paths. Navigation likewise applies the Dijkstra family with road-segment travel times as weights, but since a nationwide road network has tens of millions of vertices and pure Dijkstra is slow, it is accelerated by A* or preprocessing techniques described below.
4. DP-Based: Bellman-Ford and Floyd-Warshall
Bellman-Ford's algorithm allows the negative edges that Dijkstra gave up. Its strategy is exhaustive: it "repeats V−1 times the task of relaxing every edge of the graph once." Since a shortest path contains no cycle, it consists of at most V−1 edges; because at least one edge of the shortest path is definitively relaxed in each pass, all shortest distances converge after V−1 passes. Its time complexity is O(V·E), slower than Dijkstra, but unlike the greedy approach that never looks back, it relaxes all edges repeatedly and so obtains correct answers even when negative edges intrude.
Why V−1 passes suffice can be understood through the propagation speed of relaxation. After the 1st pass, the shortest distances of all vertices reachable by 1 edge from the source are finalized; after the 2nd pass, paths reachable by 2 edges are finalized, and so on, so the k-th pass guarantees "shortest paths using at most k edges." Since no shortest path exceeds V−1 edges, the whole converges in V−1 passes. This shows that, unlike Dijkstra which "finalizes vertices one at a time in distance order," Bellman-Ford is a DP that "widens the path length (edge count) one layer at a time." However, if the edge relaxation order is good, it converges much earlier than V−1 passes, so an early-termination optimization that stops immediately when no update occurs in a pass is commonly used.
Another decisive value of Bellman-Ford is negative cycle detection. If, after V−1 iterations, relaxing edges once more (the V-th time) still finds an edge whose distance decreases, it means a negative cycle exists whose cost decreases the more it is traversed. In this case the shortest path diverges to negative infinity and is undefined, so the algorithm reports it. This property is directly applied to currency arbitrage detection—placing currencies as vertices and the negative log of exchange rates as edge weights, the existence of a negative cycle means "a trading opportunity that leaves a profit after going around a loop." In routing, RIP (Routing Information Protocol) applies the Bellman-Ford principle in a distributed manner via a Distance-Vector approach; since only neighbors exchange path information, convergence is slow and there is a 'count-to-infinity' problem, so it is limited to small networks by capping the hop count at 15.
Looking a little more closely at RIP's distance-vector approach reveals the distributed nature of Bellman-Ford. Each router, without knowing the full map, updates its own routing table with "the per-destination distance reported by a directly connected neighbor plus the cost between itself and that neighbor." This is the same as distributing and repeatedly performing Bellman-Ford's relaxation across the whole network. The problem is the count-to-infinity phenomenon, where, when a link breaks, distances slowly soar to infinity as "an old path the neighbor does not yet know is referenced again," and to mitigate it, complementary techniques such as a hop-count cap (15), split horizon, and route poisoning are used. The point that a theoretical algorithm, once placed in a distributed and dynamic environment, gives rise to the new challenge of convergence is an important insight from a professional engineer's perspective.
Floyd-Warshall's algorithm is a DP technique that obtains the shortest distances between all vertex pairs (APSP) at once. Its core idea is "widening the set of intermediate vertices allowed for transit one vertex at a time." At the k-th step, it obtains the shortest distance for all pairs (i, j) "when only vertices 1..k may be used as intermediates," with the recurrence dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). That is, it chooses the shorter of "the existing path not going through k" and "the path i→k→j going through k." It is implemented concisely with a triple loop, with complexity O(V³). It allows negative edges but must have no negative cycle, and if a diagonal entry dist[i][i] becomes negative, a negative cycle has been detected. It is especially suitable when the number of vertices is small, on the order of hundreds, and all-pairs distances are needed (e.g., a delay matrix for a small network, precomputation for a game map). For example, to obtain the delay matrix between all points of an in-house network with 300 vertices, rather than repeating Dijkstra 300 times (300×O((V+E)log V)), a single triple loop of O(300³)=27 million operations is more advantageous in practice, being both simpler to implement and better in cache locality. Conversely, if APSP is needed in a sparse graph of millions of vertices, Floyd-Warshall's V³ is excessive, so Johnson's algorithm, which runs Dijkstra from every vertex but removes negative edges via reweighting, is more efficient.
Comparison: Which Algorithm to Use When
The choice among the three algorithms is organized along three axes: "whether negative edges exist, query scope, and graph density." The table below summarizes the differences, but the reasons they arise are rooted in the design principles of the preceding sections.
| Category | Dijkstra | Bellman-Ford | Floyd-Warshall |
|---|---|---|---|
| Design strategy | Greedy | Dynamic programming (edge iteration) | Dynamic programming (intermediate expansion) |
| Query scope | Single-source | Single-source | All-pairs |
| Negative edges | Not allowed | Allowed | Allowed (when no negative cycle) |
| Negative cycle detection | Not possible | Possible | Possible |
| Time complexity | O((V+E)log V) | O(V·E) | O(V³) |
| Suitable situation | Large-scale routing with positive weights | Negative edges/arbitrage/RIP | Small-scale all-pairs distances |
The practical implication is clear. When, as in road networks or OSPF, weights are always positive and paths must be extracted at scale from a single source, Dijkstra is overwhelmingly fast. On the other hand, when costs include negatives or negative cycles themselves are the detection target, Bellman-Ford must be used despite being slower. When the number of vertices is small and all-pairs distances are needed, Floyd-Warshall, the simplest to implement, is better. Choosing Dijkstra based on complexity alone and then producing a wrong answer because of negative edges is a classic design mistake, and conversely using Floyd-Warshall on a positive graph and needlessly paying the V³ cost is also excessive.
Summarizing the relationship among the three algorithms in one sentence: Dijkstra is "a fast greedy specialized for positive graphs," Bellman-Ford is "a safe DP that handles even negatives," and Floyd-Warshall is "a concise DP that obtains all pairs at once." Rather than being in competition, they are a mutually complementary toolkit whose roles are divided according to problem conditions, and real systems often combine them. For example, a large-scale routing system can adopt a hybrid design that normally extracts paths quickly with Dijkstra, but applies Bellman-Ford only to the region where policy-based reward/discount weights corresponding to negatives are introduced.
5. Advanced: A* Heuristic Search and Acceleration of Large-Scale Path Finding
In large-scale real-time path finding, even pure Dijkstra is slow. Because Dijkstra finalizes distances in all directions centered on the source regardless of the destination's direction, it searches even vertices on the opposite side unnecessarily even when the destination is on one side. A* (A-star) algorithm adds a heuristic estimation function h(n) here to guide it to "prioritize searching vertices that appear close to the destination." A* evaluates each vertex's priority as f(n) = g(n) + h(n), where g(n) is the distance actually accumulated from the source to n, and h(n) is the estimated distance from n to the destination (e.g., the straight-line distance on map coordinates). If h(n) satisfies the admissible condition of never overestimating the actual distance, A* guarantees the optimal solution identically to Dijkstra while narrowing the search scope toward the destination, making it far faster. Setting h(n)=0 makes A* exactly Dijkstra, so A* can be seen as a generalization of Dijkstra.
A* is the de facto standard for game AI pathfinding and robot path planning. When moving a unit to a target point on a grid map, using straight-line (Euclidean) or grid (Manhattan) distance as the heuristic enables real-time movement by expanding only a small number of nodes even on maps of millions of cells. However, if the heuristic overestimates, optimality is lost, and if computing the heuristic itself is expensive, the benefit is offset, so the design of h(n) governs performance.
Let us gauge the heuristic's effect with numbers. On a 1,000×1,000 grid map with the source and destination at opposite ends of the map, Dijkstra may finalize hundreds of thousands of cells, spreading out like concentric circles centered on the source. In contrast, A* using Manhattan distance as the heuristic concentrates the search into a narrow band toward the destination and, on maps with few obstacles, finds the same optimal path while expanding only on the order of a few thousand cells proportional to the path length. The more obstacles there are, so that the heuristic's 'straight-line estimate' diverges greatly from the actual detour distance, the more A*'s advantage shrinks and approaches Dijkstra—this well illustrates the principle that the higher the informedness of the heuristic, the more efficient the search. In games where real-time performance is absolute, Weighted A*, which adds weight to the heuristic to produce a 'good enough' path faster instead of a fully optimal one, is also used, which is a classic trade-off that buys response time by conceding some optimality.
A road network with tens of millions of vertices, like nationwide navigation, is insufficient with A* alone and uses preprocessing-based acceleration. Representatively, Contraction Hierarchies removes low-importance vertices in advance while adding shortcut edges to build a hierarchical structure, and at query time computes nationwide paths within milliseconds via bidirectional search. Another technique, bidirectional search, proceeds with the search simultaneously from the source and destination so that they meet in the middle, reducing the area the search spreads to roughly half or less—if a unidirectional search explores a circle of radius r, bidirectional explores two circles of radius r/2, so the area shrinks greatly. Furthermore, since real navigation is a dynamic-weight environment where weights change frequently with traffic, techniques of periodically recomputing distances to reflect real-time traffic information or incrementally updating only the affected segments are combined. This flow of expansion—"static shortest path algorithm → heuristic → preprocessing → dynamic update"—shows that shortest path technology is a domain that keeps advancing beyond textbook algorithms.
6. Considerations and Implications
When designing and applying shortest path algorithms from a professional engineer's perspective, the following should be considered comprehensively.
First fix the nature of the weights, then choose the algorithm. If all edges are positive, Dijkstra is best, but if even one negative edge exists, Dijkstra yields a wrong answer, so one must switch to Bellman-Ford or Floyd-Warshall. In the requirements analysis stage, "whether costs can turn negative and whether negative cycle detection is the goal" must be identified without fail, and overlooking this mass-produces wrong results that look correct.
Tune the data structure and complexity according to query scope and graph density. Heap-based Dijkstra (O((V+E)log V)) suits single-source, sparse graphs; Floyd-Warshall (O(V³)) suits all-pairs, small dense graphs; and Johnson suits all-pairs, large sparse graphs. If queries are frequent and the graph is static, a strategy of paying preprocessing (Contraction Hierarchies) cost to accelerate queries is effective.
Include actual path reconstruction and tie handling in the design. Not only distance values but also the predecessor (prev) array must be maintained to backtrack the path itself. Furthermore, when multiple paths of equal shortest distance exist, specifying a tie-breaking rule for which to choose (minimum edge count, a specific priority, etc.) yields reproducible results.
Consider convergence and scalability in dynamic/distributed environments. In environments where topology and weights change, such as routing, the cost of full recomputation and convergence delay become issues. Link-state (OSPF, global information + Dijkstra) converges quickly but has a heavy information-sharing load, while distance-vector (RIP, local information + Bellman-Ford) is simple but carries the risk of count-to-infinity and slow convergence, so they must be chosen and mixed according to network scale and volatility.
Manage the trade-off between heuristics and approximation. A*'s heuristic greatly increases speed but loses optimality if the admissibility condition is violated. In ultra-large-scale, real-time demands, approximation/preprocessing techniques that concede a little of the optimal solution to secure response time can be reasonable, so judgment that tunes the 'accuracy vs. responsiveness' trade-off to the service level agreement (SLA) is needed.
Check numerical stability and implementation pitfalls. When representing infinity (∞) as a very large integer, set a bound so that
∞ + woverflow does not occur during relaxation, and beware of the classic error of using Dijkstra when negative edges exist, or of getting Floyd-Warshall's iteration order wrong (k must be the outermost loop). Since a small implementation error can create a 'plausible but wrong' path leading to an operational incident, include verification of boundary cases (unreachable vertices, self-loops, equal-cost multiple paths) in the design.Leverage connections with neighboring graph problems. Shortest path shares design principles with other graph problems such as minimum spanning tree (MST), max-flow, and topological sort, and is often combined with them. For example, in a DAG (directed acyclic graph), relaxing just once in topological-sort order obtains shortest paths—including negative edges—in O(V+E), so grasping the graph's structural characteristics allows applying a specialized solution faster than the general algorithm. The modeling ability to reduce a problem to shortest path and solve it is also important.
In sum, shortest path algorithms, on the common principles of relaxation and optimal substructure, split into greedy (Dijkstra) and DP (Bellman-Ford·Floyd-Warshall), to which heuristics (A*) and preprocessing/dynamic updates are added, forming a foundational technology that underpins routing, navigation, games, and logistics as a whole. A professional engineer must accurately diagnose the problem's conditions (weight nature, query scope, graph scale, volatility) and possess the capability to select and combine the right algorithm and acceleration strategy at the balance point of accuracy, performance, and scalability.
References
- E. W. Dijkstra, "A note on two problems in connexion with graphs", Numerische Mathematik, 1959. https://link.springer.com/article/10.1007/BF01386390
- P. E. Hart, N. J. Nilsson, B. Raphael, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths", IEEE Transactions on Systems Science and Cybernetics, 1968. https://ieeexplore.ieee.org/document/4082128
- RFC 2328, "OSPF Version 2". https://www.rfc-editor.org/rfc/rfc2328
- RFC 2453, "RIP Version 2". https://www.rfc-editor.org/rfc/rfc2453
In one line: Shortest path algorithms, on the basis of relaxation and optimal substructure, divide into greedy Dijkstra (strong for single-source on positive graphs), DP Bellman-Ford (handling negative edges/cycles), Floyd-Warshall (obtaining all pairs), and A* (focusing search on the destination via a heuristic), and the key is to diagnose weight nature, query scope, and graph scale and select/accelerate at the balance point of accuracy and performance.