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 to n,
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.