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?

Solution 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.

Solution 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.

Solution 3

As qrqrq shows, your algorithm fails on some graphs, but the idea of BFS is good. Instead, maintain an array z of size |V| which you initialize to zero; keep the number of shortest paths to a discovered vertex i at distance less than level in z[i]. Also maintain an array d of size |V| such that d[i] is the distance from v to vertex i if that distance is less than level. Initialize level to 0, d[v] to 0, and z[v] to 1 (there is a single path of length 0 from v to v), and set all other entries of d to -1 and of z to 0.

Now whenever you encounter an edge from i to j in your BFS, then:

• If d[j] = -1, then set d[j] := level and z[j] := z[i].
• If d[j] = level, then set z[j] := z[j] + z[i].
• Otherwise, do nothing.

The reason is that for every shortest path from v to i, there is one shortest path from v to j. This will give the number of shortest paths from v to each vertex in linear time. Now do the same again but starting from w.

Solution 4

This algorithm looks correct to me.

BFS, as you know, is a linear time (O(N)) search because the time T required to complete it is, at worst, T = C + a * N, where N is the number of nodes and C, a are any fixed constants.

In your case, performing the search twice - first from v to w, and then from w to v - is (at worst) 2T, or 2C + 2a * N, which also satisfies the linear time requirement O(N) if you define a new C' = 2C, and a new a' = 2a, because both C' and a' are also fixed constants.

Solution 5

int edgeCb( graphPT g, int x, int y )
{
    if ( dist[ y ] > dist[ x ] + 1 ) {
        dist[ y ] = dist[ x ] + 1; // New way
        ways[ y ] = ways[ x ]; // As many ways as it's parent can be reached
    } else if ( dist[ y ] == dist[ x ] + 1 ) {
        ways[ y ] += ways[ x ]; // Another way
    } else {
        // We already found a way and that is the best
        assert( dist[ y ] < g->nv );
    }
    return 1;
}

Above code is giving me proper results for all kind of graphs mentioned in this post. Basically it is a edge callback for the BFS traversal.

dist[ start ] = 0; ways[ start ] = 1;

for rest all vertices dist[ x ] = numberOfVertices; // This is beyond the max possible disatance

BFS( g, start );

If ways[ end ] is not zero then that represents the number of ways and dist[ end ] represents the shortest distance.

Incase ways[ end ] == 0 means end can't be reached from start.

Please let me know if there are any loop holes in this.

View more solutions