Algorithms in a Nutshell

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.

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 v∈S 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 v∈V-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 v₂, for example, the algorithm determines that the distance from s to v₃ is really 17 through the path <s, v₂,v₃>. Once S expands to equal V, the algorithm ...