GATE Overflow Test Series | Algorithms | Test 2 | Question: 25

Question

Suppose we run Dijkstra’s single source shortest-path algorithm on the following edge weighted directed graph with vertex $a$ as the source. In what order do the nodes get included into the set of vertices for which the shortest path distances are finalized? (Assume that whenever there is a tie the vertex whose weight got finalized first is chosen first)


 

• A. $a,b,c,h,g,e,d,f$
• B. $a,b,g,h,c,f,e,d$
• C. $a,b,g,c,h,e,d,f$
• D. $a,b,c,h,g,f,e,d$

Comments

can anyone explain this please?

Answer 1

$a$

Next smallest distance $b – 4$

New distances: $ g-8, c-12$

Next smallest distance $g-8$

New distances: $c-12, h-9$

Next smallest distance: $h-9$

New distances: $f-15, c-11$

Next smallest distance: $c-11$

New distances: $e-15, d-18, f-15$

Next smallest distance: $f-15$ ($f$ got finalized before $e)$

No more changes,

$a,b,g,h,c,f,e,d$ is the correct order as visited by the Dijikstra's algorithm.

Correct option: B.