With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

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 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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required