It is alleged that the standard BFS can be extended to output all possible shortest paths between two given vertices in a directed unweighted graph (without loops? it does not seem to matter whether there are…); see, for instance, this code and this task. While this ordinary traversal algorithm is uni-directional, there does exist a bi-directional variant of it, which is claimed to be faster in many cases. However, the so-called bi-directional BFS appears to be able to find only one shortest path, at least according to the NetworkX's Python implementation bidirectional_shortest_path and bidirectional_dijkstra (where Dijkstra's algorithm with all edges of weight one degenerates into BFS). (Note that the two implementations are not limited to undirected graphs.) A natural problem is: can the bi-directional breadth-first search algorithm be modified so that it is capable of returning all the shortest paths between two particular vertices in an unweighted digraph as well?

It is alleged that the standard BFS can be extended to output all possible shortest paths between two given vertices in a directed unweighted graph (without loops? it does not seem to matter whether there are…); see, for instance, this code and this task. While this ordinary traversal algorithm is uni-directional, there does exist a bi-directional variant of it, which is claimed to be faster in many cases. However, the so-called bi-directional BFS appears to be able to find only one shortest path, at least according to the NetworkX's Python implementation bidirectional_shortest_path and bidirectional_dijkstra (where Dijkstra's algorithm with all edges of weight one degenerates into BFS). (Note that the two implementations are not limited to undirected graphs.) A natural problem is: can the bi-directional breadth-first search algorithm be modified so that it is capable of returning all the shortest paths between two particular vertices in an unweighted digraph as well?

• algorithm
• graph-theory
• shortest-path
• path-finding
• bidirectional-search

• 1 Sure it can be extended, have you tried it? Basically process the queue in batches with paths of the same length; then when finding a shortest path, complete the current batch instead of stopping immediately. – Bergi Commented Mar 6 at 10:23
• Double BFS seems like a suboptimal approach to the problem of enumerating all shortest paths in a DAG. I'd suggest you take another approach: prove that the subset of shortest paths forms a consistent sub-DAG, build this sub-DAG (using dynamic programming, that part remains cheap) and then enumerate all the paths on this obtained DAG (that part may produce an output of exponential size w.r.t the input). – m.raynal Commented Mar 6 at 10:27
• @Bergi I am not sure what the "correct" termination criterion is in this case; actually, I find that even for the primitive bi-directional BFS algorithm, people still have controversy over it: link 0, link 1, link 2, etc. – user688486 Commented Mar 6 at 12:00
• As @Bergi said, the correct termination criterion is, rather than stopping when the current node w reaches the first previously-discovered node as in standard bi-directional BFS, to continue until all nodes on that level (i.e. all nodes with the same depth as w) have been processed as they may contribute to more paths of the same length. – beaker Commented Mar 6 at 16:12
• 2 Thanks for the links, that one was quite interesting! But yeah, like tapichu wrote in their answer in your first link, bidirectional search must "alternate the forward and backward […] searches [layer] by layer and not by node", or as @beaker put it, process all nodes on the same level together. Regardless whether you do that to find any shortest path or all shortest paths. – Bergi Commented Mar 6 at 22:26

1 Answer 1

(1) Theoretically, yes.

Let the shortest path between u and v have length d. A bidirectional BFS essentially finds all vertices at distance d/2 from u and all vertices at distance d-d/2 from v, and these two sets have a non-empty intersection S. When we care about finding all possible paths, each vertex also stores all possible previous vertices on the path.

When we have this stored, we can enumerate all shortest paths between u and v as follows. Enumerate all vertices of S. For each vertex w in S, concatenate (Cartesian product) every path from u to w with every path from w to v. The path halves can be restored starting from w in both cases. This will give every shortest path exactly once.

(2) Implementation-wise, you may have to get your hands dirty, because this does not seem to be a common problem to solve.

(3) The number of shortest paths between a pair of vertices can well be exponential. In this case, the speed of finding all shortest paths will be dominated by the speed with which the algorithm outputs a single path. It won't matter then whether you used one-directional or two-directional BFS. This choice matters only when you know there are very few such paths.