Shortest paths are not always unique sometimes there are two

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 O ((|V | + |E|) log(|V |)) time. Input: An undirected graph G = (V, E); edge lengths `e > 0; starting vertex s ? V ; ending vertex t ? V . Output: True if there is a unique shortest path from s to t and false if there are more than one different shortest paths from s to t.

Solution

idea to solve this:

Suppose there are two different shortest paths from s to u . These two paths can either share the same last edge or not. If they do, this can be detected by modifying Dijkstra’s to detect if a node has been added to the known region previously with the same distance.
If not there must be two different shortest paths to u ’s parent, which can be detected by propagating (for every edge ( a , b ) ) usp ( a ) to usp ( b ) if DECREASEKEY ( H , v )

psuedp code for dijkstra\'s algorithm:

The array usp[ · ] is initialized to true in the initialization loop

while H is not empty do
u = DELETEMIN( H )
for all ( u , v ) E do
if dist ( v ) > dist ( u ) + l ( u , v ) then
dist ( v ) = dist ( u ) + l ( u , v )
DECREASEKEY(H, v)
usp [ v ] = usp [ u ]
else if dist ( v ) = dist ( u ) + l ( u , v ) then
usp [ v ] = false

correctness proof:

By Dijkstra’s proof of correctness, this algorithm will identify the shortest paths from the source u to the other vertices.
For uniqueness, we consider some vertex v . Let p denote the shortest path determined by Dijkstra’s algorithm. If there are multiple shortest paths, then take another path p 0 = p and it will either share the same nal edge ( w , v ) (for some vertex w ) as p , or they have different nal edges from p .
In the former case, there must be multiple shortest paths from u to w . Using an inductive argument, which supposes that usp is already set correctly for all vertices that are closer than v , this will be detected in the rst conditional statement when the algorithm explores from w and updates the distance to v by taking edge ( w , v ) , as it will detect that there are multiple shortest paths to w . In the latter case, if the last edges of the two shortest paths are ( w 1 , v ) and ( w 2 , v ) , then since edge lengths l e > 0, both w 1 and w 2 must be visited before v , thus the algorithm will detect the existence of multiple shortest paths with the second conditional statement. The base case is true because there is a unique shortest path from the source s to itself