Here is the exercise:
Let v and w be two vertices in a directed graph G = (V, E). Design a linear-time algorithm to find the number of different shortest paths (not necessarily vertex disjoint) between v and w. Note: the edges in G are unweighted
For this excise, I summarise as follows:
From the points above, I have the following thoughts:
count
for the number of shortest pathsglobal level
informationglobal level
by one each time then BFS reaches a new levelshortest level
info for shortest path to wglobal level
to the shortest level
and count++
; global level
equals to the shortest level
, I increase count
each time I met w again.global level
becomes bigger than the shortest level
, I terminate the travelling, because I am looking for shortest path not path.Is my algorithm correct? If I do v to w and then w to v, is that still considered as linear-time?
Here are some ideas on this.
Proof: If there are multiple paths entering x
through the same vertex there are obviously multiple ways through x
. This is simple. Now let us assume there is only one way into x
through each vertex going into x
(at maximum).
If x has been encountered before, none of the current paths can contribute to another shortest path. Since x has been encountered before, all paths that can follow will be at least one longer than the previous shortest path. Hence none of these paths can contribute to the sum.
This means however we encounter each node at most once and are done. So a normal BFS is just fine.
This can be compiled into a very simple algorithm, which is mainly just BFS.
- Mark nodes as visited as usual with BFS.
- Instead of adding just nodes to the queue in the DFS add nodes plus number of incoming paths.
- If a node that has been visited should be added ignore it.
- If you find a node again, which is currently in the queue, do not add it again, instead add the counts together.
- Propagate the counts on the queue when adding new nodes.
- when you encounter the final, the number that is stored with it, is the number of possible paths.