Computer Science 136 |
Lecture 33: Dijkstra's Algorithm, Maps and Dictionaries
Date: December 2, 2005
T is the empty graph;
PQ is an empty priority queue;
All vertices in V are marked unvisited;
Add s to T; mark s as visited in G;
Add each edge (s,v) of G to PQ with appropriate value
while (T.size() < G.size() and PQ not empty)
do
nextEdge = PQ.remove();
until(one vertex of nextEdge is visited and the other is unvisited)
or until there are no more edges in PQ
// assume nextEdge = (v,u) where v is visited (in T) and u is
unvisited (not in T)
Add u to T; mark u as visited in G;
Add (u,v) to T;
for each unvisited neighbor w of u
add (u,w) to PQ with appropriate weight