O'Reilly logo

Mastering Algorithms with C by Kyle Loudon

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

No credit card required

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

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

Start Free Trial

No credit card required