Description

Dijkstra's algorithm is to find and to store shortest paths in a kind of rooted spanning tree. We can denote the result by its edges set T subeE. In Dijkstra's algorithm, we divide vertices to $2$ groups, visited group $V^{\text{'}}$ and unvisited group $U.$

If we want to move a vertex $v_i$inU to $V^{\text{'}},$ we should apply our operation by a bridge edge $e_b=(s_b,v_i,w_b)inE$ and $s_{b}in{V}^{\text{'}}.$

$V^{\text{'}}$larr$\{s\},$Ularr$\frac{V}{\frac{?}{?}}{V}^{\text{'}},$Tlarr$\{(s,s,0)\}.$

Find the minimum bridge edge $e_b$ between $V^{\text{'}}$ and $U.$

Find bridged node $\frac{e_r}{i}nT$ that $t_r=s_b$ with minimal $w_b+w_r.$

$4$ Make an edge $e_b^{\text{'}}=(s_b,t_b,w_b+w_r).$

Update information $V^{\text{'}}larr{V}^{\text{'}}U\{t_b\},U=\frac{U}{\frac{?}{?}}\{t_b\},$TlarrT$\{e_b^{\text{'}},\}.$

Repeat step $2$ to step $5$ until $U=\frac{O}{?}.$

Questions

$1$ Analyze the time complexity when implement step $2$ by sequential searching whole adjacency list.

$2$ Analyze the time complexity when implement step $2$ by a priority queue that maintained the bridge edges.

$2\mathrm{.}1$ Implement the priority queue by double$-$linked list.

$2\mathrm{.}2$ Implement the priority queue by Min$-$heap.

$3$ Design an algorithm to reconstruct the path from spanning tree $T($the result$).$

$4$ How to find the unreachable $($have no path from $s)$ set?

Can you describe the answers. And please use cpp programs for the implementations of the algorithms