0
$\begingroup$

I came across following problem:

Consider below graph:
enter image description here
What will be the shortest path tree starting with node $A$ returned by Dijkstra's algorithm, if we assume priority queue is implemented as binary min heap?

My solution:

I referred Dijkstra from CLRS:
enter image description here

With A as a starting node, we will have priority queue bin min heap as follows:

A{root, 0}
    |
Rest all:{∅,∞}

(Notation: {parent in SPT, shortest path weight})

It will extract A from priority queue and add it to SPT and will relax AC and AB:

    B{A:5}
     /  \
C{A:6}  Rest all:{∅,∞} 

It will extract B from priority queue and and add it to SPT:

   C{A:6}
      |
Rest all:{∅,∞} 

and will relax BE:

            C{A:6}
             /   \
Rest all:{∅,∞}   E{B,6}

Next it will extract C and so one. Thus the SPT will be:

enter image description here

But not:

enter image description here

Q1. Am I correct with above?
Q2. CLRS algo does not dictate which node to add to SPT if multiple of them have same shortest path weight. Hence its dependent on how priority queue is implemented. If no information was given about how priority queue was implemented then we cannot tell how SPT will be formed. Am I right?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.