Question

Shortest paths are not always unique: sometimes there are two or more different paths with the minimum possible length. Show how to solve the following problem in $\mathit{O}\mathbf{\left(}\mathbf{\right(}\mathbf{\left|}\mathit{V}\mathbf{\right|}\mathbf{+}\mathbf{\left|}\mathit{E}\mathbf{\right|}\mathbf{)}\mathbf{}\mathbf{}\mathit{l}\mathit{o}\mathit{g}\mathbf{|}\mathit{V}\mathbf{|}\mathbf{}\mathbf{)}$time.

Input:An undirected graph $\mathbf{}\mathit{G}\mathbf{=}\mathbf{(}\mathit{V}\mathbf{,}\mathit{E}\mathbf{)}$;edge lengths ${\mathit{l}}_{\mathbf{e}}\mathbf{>}\mathbf{0}$; starting vertex $\mathit{s}\mathbf{\in }\mathit{V}$.

Output:A Boolean array for each node u , the entry $\mathit{u}\mathit{s}\mathit{p}\mathbf{\left[}\mathit{u}\mathbf{\right]}$should be $\mathit{t}\mathit{r}\mathit{u}\mathit{e}$ if and only if there is a unique shortest path s to u (Note:$\mathit{u}\mathit{s}\mathit{p}\mathbf{\left[}\mathit{s}\mathbf{\right]}\mathbf{=}\mathit{t}\mathit{r}\mathit{u}\mathit{e}$)

Short answer

The given problem can be solved by modifying the Dijkstra’s algorithm as follows:

for all edges $(u,v)\in E$

if $dist\left(v\right)>dist\left(u\right)+l(u,v)$

$dist\left(v\right)=dist\left(u\right)+l(u,v)$

$usp\left(v\right)=usp\left(u\right)$

else if $dist\left(v\right)=dist\left(u\right)+l(u,v)$

$usp\left(v\right)=false$

Step-by-step solution

Explain the given information

Consider the undirected graph G(V,E), edge length is denoted by $I_e$and the starting vertex is $s\in V$ . The shortest paths are not always unique, sometimes there are two or more different paths with the minimum possible length.

Solve the given problem.

Consider the undirected graph $G\left(V,E\right)$, edge length is denoted by $I_e$and the starting vertex is $s\in V$.

To get the Boolean array that has the $usp\left[u\right]$entry if and only if there is unique shortest path s to u .

The problem can be solved by modifying the Dijkstra’s algorithm as follows:

$$\begin{gathered} Input:AnundirectedgraphG=(V,E);edgelengths{l}_e>0; \\ startingvertexs\in V. \\ Output:ABooleanarrayusp[.]:foreachnodeu,theentry \\ usp\left[u\right]shouldbeifandonlyifthereisauniqueshortest \\ pathstou(Note:usp[s]=true) \\ foralledges(u,v)\in E: \\ ifdist\left(v\right)>dist\left(u\right)+l(u,v) \\ dist\left(v\right)=dist\left(u\right)+l(u,v) \\ usp\left(v\right)=usp\left(u\right) \\ elseifdist\left(v\right)=dist\left(u\right)+l(u,v) \\ usp\left(v\right)=false \end{gathered}$$

Therefore, the give problem has been solved by the modified Dijkstra’s algorithm.