Page 221 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes

Finally, add v to S.
The predecessor list now defines the shortest path from

each node to s.

Dijkstra’s algorithm

* Initialise d and pi* for each vertex v in V( g )

g.d[v] := infinity
g.pi[v] := nil
g.d[s] := 0;
* Set S to empty *
S := { 0 }
Q := V(g)
* While (V-S) is not null*
while not Empty(Q)

1. Sort the vertices in V-S according to the current best estimate of their distance from the
source u := Extract-Min ( Q );
2. Add vertex u, the closest vertex in V-S, to S, AddNode( S,
u );
3. Relax all the vertices still in V-S connected to u relax( Node u,

Node v, double w[][] )
if d[v] > d[u] + w[u]v] then
d[v] := d[u] + w[u][v]
pi[v] := u

In summary, this algorithm starts by assigning a weight of infinity to all vertices, and then

selecting a source and assigning a weight of zero to it. Vertices are added to the set for which
shortest paths are known. When a vertex is selected, the weights of its adjacent vertices are
relaxed. Once all vertices are relaxed, their predecessor’s vertices are updated (pi). The cycle
of selection, weight relaxation and predecessor update is repeated until the shortest path to all
vertices has been found.

10.5 Summary

a heap is a partially sorted binary tree. Although a heap is not completely in order, it
conforms to a sorting principle: every node has a value less (for the sake of simplicity, I will
assume that all orderings are from least to greatest) than either of its children.

216 LOVELY PROFESSIONAL UNIVERSITY