Mastering Algorithms with C

Description of Shortest Paths

Finding the shortest path, or minimum-weight path, from one vertex to another in a graph is an important distillation of many routing problems. Formally stated, given a directed, weighted graph G = (V, E ), the shortest path from vertex s to t in V is the set S of edges in E that connect s to t at a minimum cost.

When we find S, we are solving the single-pair shortest-path problem. To do this, in actuality we solve the more general single-source shortest-paths problem , which solves the single-pair shortest-path problem in the process. In the single-source shortest-paths problem, we compute the shortest paths from a start vertex s to all other vertices reachable from it. We solve this problem because no algorithm is known to solve the single-pair shortest-path problem any faster.

Dijkstra’s Algorithm

One approach to solving the single-source shortest-paths problem is Dijkstra’s algorithm (pronounced “Dikestra”). Dijkstra’s algorithm grows a shortest-paths tree, whose root is the start vertex s and whose branches are the shortest paths from s to all other vertices in G. The algorithm requires that all weights in the graph be nonnegative. Like Prim’s algorithm, Dijkstra’s algorithm is another example of a greedy algorithm that happens to produce an optimal result. The algorithm is greedy because it adds edges to the shortest-paths tree based on which looks best at the moment.

Fundamentally, Dijkstra’s algorithm works by repeatedly selecting a vertex ...