25-09-2013, 04:28 PM
ALGORITHMS IN NETWORKS
AIM:
Single source shortest path algorithm for directed weighted graphsijkstra’s
algorithm
Similar to the single source shortest path algorithm for unweighted graphs.
Algorithm:
s – starting node
DT – Distance Table,
PQ – priority queue, the priority of a node is equal to the distance from s to that node
Initialize DT(s,0) = 0, DT(s,1) = 0, all remaining DT(j,k) = -1
1. Store s in PQ with distance = 0
2. While there are vertices in the queue:
1. DeleteMin a vertex v from the queue