Procedure Dijkstra ( G, W, Vs)
The above procedure finds the shortest path from the given graph. It uses the concept of relaxing all edges of graph repeatedly once.
Step 1 Initialization, loop
for Vi ¬ V1, V2, .... Vn R for each Vi in V
set dist [Vi] ¬ + ¥
set color [Vi] ¬ white
set pre [Vi] ¬ NULL
set dist [Vs] ¬ 0.
Step 2 Putting all vertices in Q
set Q ¬ call to prio Queue (V) R Put vertices in Q
while ( non-empty (Q) )
set Vi ¬ Extract_minimum (Q)
start loop 2
for Vj ¬ V1, V2, .... Adj [Vi] R for each Vj in Adj [Vi]
if ( dist [Vi] + W (Vi, Vj) <>j] ) then
set dist [Vj] ¬ dist [Vi] + W (Vi, vj)
call to Decrease-key (Q, Vi, dist [Vj])
} set pre [Vj] ¬ Vi
End of loop 2
Step 4 Coloring
set color [Vi] ¬ Black
end of loop 1.
Step 5 Return at the point of call