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.

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

Start Free Trial

No credit card required