How to find the number of different shortest paths between two vertices, in directed graph and with linear-time?

Question

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:

1. It is a directed graph
2. 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.
3. between v and w, so both from v to w and from w to v should be counted.
4. linear-time.
5. The graph is not weighted.

---

From the points above, I have the following thoughts:

1. 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.
2. I maintain a count for the number of shortest paths
3. I would like to use BFS from v first and also maintain a global level information
4. I increase the global level by one each time then BFS reaches a new level
5. I also maintain the shortest level info for shortest path to w
6. The first time I meet w while traveling, I assign the global level to the shortest level and count++;
7. as long as the global level equals to the shortest level, I increase count each time I met w again.
8. if the global level becomes bigger than the shortest level, I terminate the travelling, because I am looking for shortest path not path.
9. 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?

Answer 1

Here are some ideas on this.

• There can only be multiple shortest paths from v->w through node x, either if there are multiple paths into x through the same vertice or if x is encountered multiple time at the same DFS level.

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.

• We do not even need to know the level, instead we can get the final number once we encounter the final node.

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. 

Answer 2

Your algorithm breaks on a graph like

  *   *   *   1  / \ / \ / \ / \ v   *   *   *   w  \ / \ / \ / \ /   *   *   *   2 

with all edges directed left to right. It counts two paths, one through 1 and the other through 2, but both 1 and 2 can be reached from v by eight different shortest paths, for a total of sixteen.