Dijkstra algorithm for shortest path

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

step 3 Loop 1, processing all vertices

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

return.