Page 220 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 10: Heaps

Notes
From all the adjacent vertices, choose the closest vertex
to the source s.

As we initialized d[s] to 0, it’s s. (shown in bold circle)
Add it to S
Relax all vertices adjacent to s, i.e u and x
Update vertices u and x by 10 and 5 as the distance from
s.

Choose the nearest vertex, x.
Relax all vertices adjacent to x
Update predecessors for u, v and y.

Predecessor of x = s
Predecessor of v = x ,s
Predecessor of y = x ,s
add x to S

Now y is the closest vertex. Add it to S.
Relax v and adjust its predecessor.

u is now closest, add it to S and adjust its
adjacent vertex, v.

LOVELY PROFESSIONAL UNIVERSITY 215