. It
can also be used for the all-pairs shortest-path
problem, by the simple expedient of applying it N times---once to each
vertex 
, ...,
.
Dijkstra's single-source shortest-path
algorithm computes all shortest paths from a single
vertex, . It
can also be used for the all-pairs shortest-path
problem, by the simple expedient of applying it N times---once to each
vertex , ...,
.
Dijkstra's sequential single-source algorithm is given as Algorithm 3.2. It
maintains as T the set of vertices for which shortest paths have not
been found, and as 
the shortest known path from 
to vertex 
. Initially, T=V and
all 
. At each
step of the algorithm, the vertex 
in T with the smallest d
value is removed from T . Each neighbor of 
in T is examined to see
whether a path through 
would be shorter than the currently best-known
path (Figure 3.27).
