I came across following problem:

Consider below graph:

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:

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:

But not:

**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?