We can use Dijkstra's algorithm to find the shortest path between
any two vertices (,*t*) in a weighted graph, where each edge
has non-negative edge weight.
Although most applications of shortest path involve graphs with positive
edge weights, such a condition is not needed for either Prim's or Kruskal's
algorithm to work correctly.
The problems that negative edges cause Dijkstra's algorithm will become
apparent once you understand the algorithm.

The principle behind Dijkstra's algorithm is that given the shortest path
between and each of a given set of
vertices , there must exist some other vertex *x*
such that the shortest path from to *x* must go from to to *x*,
for some .
Specifically, it is the vertex *x*
that minimizes over all ,
where
*w*(*i*,*j*) is the length of the edge from *i* to *j*
and *dist*(*i*,*j*) is the length of the shortest path between them.

This suggests a dynamic programming-like strategy.
The shortest path from to itself is trivial unless there are negative
weight edges, so *dist*(,)=0.
Armed with the shortest path to , if (,*y*) is the lightest edge
incident to , then *d*(,*y*) = *w*(,*y*).
As soon as we decide that we have determined the shortest path
to a node *x*, we search through all the outgoing edges of *x*
to see whether there is a better path from
to some unknown vertex through *x*:

ShortestPath-Dijkstra(

G,s,t)

for

i=1 ton,for each edge (,

v),dist[v]=w(,v)

last=while ( )

select , the unknown vertex minimizing

dist[v]for each edge ,

To be certain of finding the shortest path between and *t*,
we might have to first find the shortest path
between and all other vertices.
This defines a shortest path spanning tree rooted in .
For undirected graphs, this will be the breadth-first search tree, but in
general it provides the shortest path between and all other vertices.

What is the running time of this algorithm?
When implemented using adjacency lists
and a Boolean array to mark what is known about each vertex,
the complexity is .
This is the same running time as a proper version of Prim's algorithm;
indeed, except for the extension condition, it *is* the same algorithm
as Prim's.

Mon Jun 2 23:33:50 EDT 1997