Throw an error if multiple shortest paths are found

Question

Given an undirected weighted graph, a start, and an end point. You need to find the shortest path to that end point, but throw an error if multiple shortest paths are found. How would we do the error part? Is there a way to check if multiple shortest paths to a destination node exist?

My idea is that when we pop out of the priority queue in dijkstra's algorithm, at that time if the node is the destination node, then we check if in this priority queue, another element exists for the same destination node. During the relaxation, instead of only pushing to the queue if the distance is less than, we can push if the distance is less than or equal to. But I am not sure about it.

EDIT - Its a weighted undirected graph

Answer 1

One way to do this is by creating a shortest path DAG. Whenever you relax some edge from node A to node B with cost C (assuming the current shortest distance from source to each node is stored in array dist), if dist[A] + C is greater than dist[B] then do nothing, if dist[A] + C is equal to dist[B], then we can reach B in a shortest path using a different route than before, so we add A to the list of nodes that can reach B in its shortest path (let's call this array pars), so we add A to pars of B, and finally if dist[A] + C is less than dist[B], then we update dist[B] and clear the previous values from pars[B], and add A to pars[B].

The resulting graph is guaranteed to be a DAG if all edge weights are strictly greater than 0. Then you can count the number of paths to the destination node using some easy dynamic programming methods, process node in a topological order, then the number of paths of each node is the sum of number of paths of nodes that reach it (nodes in pars[node]).

Hopefully this was useful and clear.