Question

Question: Often there are multiple shortest paths between two nodes of a graph. Give a linear-time algorithm for the following task.

Input: Undirected graph G = (V , E )with unit edge lengths; nodes$\mathbf{u}\mathbf{,}\mathbf{v}\mathbf{\in }\mathbf{V}$

Output: The number of distinct shortest paths from utov.

Short answer

The multiple shortest paths between two nodes of a graph is given in the algorithm described.

Step-by-step solution

Step-1: Breadth-first search(BFS)

Breadth-first search(BFS) is a graph traversal method that begins at the root node and traverses the graph to all of the adjacent nodes. Then it chooses the closest node and investigates all of the nodes that have yet to be explored. Any node in the graph can be considered the root node when employing BFS for traversal.

Step-2: Algorithm

To find the distinct shortest path BFS can be used.

Input: is the number of nodes in the given graph

S is the source node or vertex

D is the destination node or vertex

G is the graph

Output: Returns the distinct shortest paths,

$$\begin{gathered} \mathrm{distance}\left[\right]\leftarrow \infty ; \\ \mathrm{path}\left[\right]\leftarrow 0; \\ \mathrm{queue}\leftarrow \left\{\right\}; \\ \mathrm{queue}.\mathrm{add}\left(\mathrm{s}\right); \\ \mathrm{distance}\left[\mathrm{S}\right]\leftarrow 0; \\ \mathrm{path}\left[\mathrm{S}\right]\leftarrow 1; \\ \mathrm{while}\neg \mathrm{queue}.\mathrm{empty}\left(\right)\mathrm{do} \\ \mathrm{current}\leftarrow \mathrm{queue}.\mathrm{front}\left(\right); \\ \mathrm{queue}.\mathrm{pop}\left(\right); \\ \mathrm{foreachchild}\in \mathrm{G}\left[\mathrm{current}\right]\mathrm{do} \\ \mathrm{ifvisited}\left[\mathrm{child}\right]=\mathrm{false} \\ \mathrm{queue}.\mathrm{add}\left(\mathrm{child}\right); \\ \mathrm{visited}\left[\mathrm{child}\right]\leftarrow \mathrm{true} \\ \mathrm{end} \\ \mathrm{ifdistance}\left[\mathrm{child}\right]>\mathrm{distance}\left[\mathrm{current}\right]+1\mathrm{then} \\ \mathrm{distance}\left[\mathrm{child}\right]\leftarrow \mathrm{distance}\left[\mathrm{current}\right]+1; \\ \mathrm{path}\left[\mathrm{child}\right]\neg \mathrm{path}\left(\mathrm{current}\right); \\ \mathrm{end} \\ \mathrm{elseif} \\ \mathrm{distance}\left[\mathrm{child}\right]=\mathrm{distance}\left[\mathrm{current}\right]+1; \\ \mathrm{path}\left[\mathrm{child}\right]\neg \mathrm{path}\left[\mathrm{child}\right]+\mathrm{path}\left[\mathrm{current}\right]; \\ \mathrm{endif} \\ \mathrm{endfor} \\ \mathrm{endwhile} \end{gathered}$$

In the given algorithm:

distance: where distance[u] denotes the length of the shortest path between the source and destination nodes.

path: The number of shortest paths from the source node to the node u is represented by path[u].

The distance value for all nodes is infinity at first, with the exception of the source node, which is equal to 0 (the length of the shortest path from a node to itself is always equal to boldsymbol0). In addition, the pathways value for all nodes is 0 except for the source node, which has a value of 1 . (a node has a single shortest path to itself).

The BFS algorithm is then used to traverse the graph. There are two option:

1. If distance[child]$\leftarrow$distance[current]+1;, it signifies that there is a shorter path from the source node to the child node than the one we currently have. As a result, itreduce the child node's distance value to the current node's distance plus one. In addition, the pathways value for the child node will be modified to match the current node's paths value.

2. If distance[child]$\leftarrow$distance[current]+1; all shortest paths from the source node to the current node are added to the number of shortest paths of the child node. The reason for this is that after adding the edge that connects current to its child, they will have the same length as the shortest path of the child node. As a result, it will leave the child node's distance value unchanged. However, multiply the child node's pathways value by the current node's paths value.

Finally, the D node's pathways value will include the number of shortest paths between the source and destination nodes. In addition, the D node's distance value will be the length of the shortest path from S to D.