Single-Source Shortest Path

Suppose you want to fly a private plane on the shortest path from Saint Johnsbury, VT to Waco, TX. Assume you know the distances between the airports for all pairs of cities and towns that are reachable from each other in one nonstop flight of your plane. The best-known algorithm to solve this problem, Dijkstra's Algorithm (illustrated in Figure 6-13), finds the shortest path from Saint Johnsbury to all other airports, although the search may be halted once the shortest path to Waco is known. A variation of this search (A*Search, discussed in Chapter 7), directs the search with heuristic information when approximate answers are acceptable.

Dijkstra's Algorithm with priority queue fact sheet

Figure 6-13. Dijkstra's Algorithm with priority queue fact sheet

Dijkstra's Algorithm conceptually operates in greedy fashion by expanding a set of vertices, S, for which the shortest path from s to every vertex vS is known, but only using paths that include vertices in S. Initially, S equals the set {s}. To expand S, as shown in Figure 6-14, Dijkstra's Algorithm finds the vertex vV-S (i.e., the vertices outside the shaded region in Figure 6-14) whose distance to s is smallest, and follows v's edges to see whether a shorter path exists to another vertex. After processing v2, for example, the algorithm determines that the distance from s to v3 is really 17 through the path <s, v2,v3>. Once S expands to equal V, the algorithm ...

Get Algorithms in a Nutshell now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.