$\quad\textbf{DIJKSTRA}{(G,w,s)}$
$\quad 1 \quad \textbf{INITIALIZE-SINGLE-SOURCE}(G,s)$
$\quad 2 \quad S = \emptyset$
$\quad 3\quad Q = G.V$
$\quad 4\quad \textbf{while } Q \neq \emptyset$
$\quad 5\quad \quad u = \textbf{EXTRACT-MIN}(Q)$
$\quad 6\quad \quad S = S \cup \{u\}$
$\quad 7\quad \quad \textbf{for each vertex } v \in G.Adj[u]$
$\quad 8\quad \quad\quad \textbf{RELAX}(u,v,w)$
Correct Solutions:
$(A).$
$Q=\left\{\overset{\boxed{0}}{\text{A}},\overset{\boxed{\infty}}{\text{B}}, \overset{\boxed{\infty}}{\text{C}}, \overset{\boxed{\infty}}{\text{D}}, \overset{\boxed{\infty}}{\text{E}}, \overset{\boxed{\infty}}{\text{F}} \right\}$
- First we visit $\text{A}$ as it is the one with smallest distance $0$
- Relax operation updates distances to $\text{B,C,F}$ as $6,90,70$ respectively
$Q=\left\{\overset{\boxed{6}}{\text{B}}, \overset{\boxed{90}}{\text{C}}, \overset{\boxed{\infty}}{\text{D}}, \overset{\boxed{\infty}}{\text{E}}, \overset{\boxed{70}}{\text{F}} \right\}$
- $\text{B}$ is next visited as its distance is now $6$
- Relax operation updates distance to $\text{D}$ as $41+6=47$
$Q=\left\{ \overset{\boxed{90}}{\text{C}}, \overset{\boxed{47}}{\text{D}}, \overset{\boxed{\infty}}{\text{E}}, \overset{\boxed{70}}{\text{F}} \right\}$
- $\text{D}$ is next visited as its distance is now $47$
- Relax operation updates distance to $\text{C}$ as $47+12=59$
$Q=\left\{ \overset{\boxed{59}}{\text{C}}, \overset{\boxed{\infty}}{\text{E}}, \overset{\boxed{70}}{\text{F}} \right\}$
- $\text{C}$ is next visited as its distance is now $59$
- Relax operation updates distance to $\text{F}$ as $59+10=69$
$Q=\left\{ \overset{\boxed{\infty}}{\text{E}}, \overset{\boxed{69}}{\text{F}} \right\}$
- $\text{F}$ is next visited as its distance is now $69$
- Relax operation updates distance to $\text{E}$ as $69+15=84$
$Q=\left\{\overset{\boxed{84}}{\text{E}}\right\}$
- Finally $\text{E}$ is visited.
So, the sequence of node visits are $\text{A}, \text{B}, \text{D}, \text{C}, \text{F}, \text{E}$
$(B).$ Sequence of vertices in the shortest path from $\text{A}$ to $\text{E}$: $\text{A}- \text{B}- \text{D}-\text{C}- \text{F}- \text{E}$
$(C).$ Cost of the shortest path from $\text{A}$ to $\text{E} = 84.$