Page 278 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 13: Graphs

Here is the algorithm. Notes

1. Let V be the set of all the vertices of the graph and S be the set of all the vertices considered
for the determination of the minimal path.
2. Set S ={}.
3. While there are still vertices in V – S.

(a) Sort the vertices in V – S according to the current best estimate of their distance from
the source.
(b) Add u, the closest vertex in V – S, to S.

(c) Re-compute the distances for the vertices in V – S
(d) Consider the following example for illustration. Find the shortest path from node X
to node Y in the following graph. A label on an edge indicates the distance between
the two nodes the edge connects.

2
A D
5
8 4
1
C
X Y
4
3
3
7
B E
5

Applying Dijkstra algorithm:

1. S = {X}
Distances of all the nodes from the nodes in the S:
XA = 8 XB = 3 XC = ∞
XD = ∞ XE = ∞ XY = ∞
2. Since, minimum distance from S to V-S is 3 (XB), S = {X, B} and E = {XB}

3. Distances of all the nodes from the nodes in the S:
XA = 8 XC = ∞ XD = ∞ XE = ∞ XY = ∞
XBA = ∞ XBC = 7 XBD = ∞ XBE = 8 XBY = 6
4. Since, minimum distance from S to V – S is 6 (XBY), S = {X, B, Y} and E = {XBY}.

5. Distances of all the nodes from the nodes in the S:
XA = 8 XC = ∞ XD = ∞ XE = ∞
XBA = ∞ XBC = 7 XBD = ∞ XBE = 8
XBYA = ∞ XBYC = ∞ XBYD = ∞ XBYE = ∞
Continuing in similar manner, we find that the shortest path between nodes X and Y is XBY with

cost value 6.

LOVELY PROFESSIONAL UNIVERSITY 273