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:
- It is a directed graph
- It asks for the number of different shortest paths. First, the paths should be shortest, then there might be more than one such shortest paths whose length are the same.
- between v and w, so both from v to w and from w to v should be counted.
- linear-time.
- The graph is not weighted.
From the points above, I have the following thoughts:
- I don't need to use Dijkstra’s Algorithm because the graph is not weighted and we are try to find all shortest paths, not just single one.
- I maintain a
count
for the number of shortest paths - I would like to use BFS from v first and also maintain a
global level
information - I increase the
global level
by one each time then BFS reaches a new level - I also maintain the
shortest level
info for shortest path to w - The first time I meet w while traveling, I assign the
global level
to theshortest level
andcount++
; - as long as the
global level
equals to theshortest level
, I increasecount
each time I met w again. - if the
global level
becomes bigger than theshortest level
, I terminate the travelling, because I am looking for shortest path not path. - Then I do 2 - 8 again for w to v
Is my algorithm correct? If I do v to w and then w to v, is that still considered as linear-time?