Is there an algorithm to find all the shortest paths between two nodes?

Question

Given a directed graph, Dijkstra or Bellman-Ford can tell you the shortest path between two nodes.

What if there are two (or n) paths that are shortest, is there an algorithm that will tell you all such paths?

Edit:

I have just thought up a possible solution. Could you just do a Bellman-Ford but when relaxing edges, if (distance[u] + w == distance[v]) then add u to the set of predecessors of v? Does this work?

Answer 1

For the $k$ shortest paths, there are algorithms; see for instance here.

Enumerating all shortest paths is, however, an inherently costly thing; there may be superexponentially many such paths.

Answer 2

Building a shared struture to make explicit enumeration optional, but easy.

I think there are several ways to interpret your question, like other questions about algorithms giving all solutions to some problem. This may be the case here as you ask for all solutions, but not specifically for an enumeration of these solutions, which you can easily get however from the approach given below.

To take a well known example, when parsing Context-Free languages, you may be interested in getting just one parse tree, or in getting all parses. The number of parse trees can actually be infinite, or exponential when you exclude derivation loops (non-terminals deriving on themselves). You might even want to know only that there is such a parse-tree, i.e. be interested only in recognition, but let us ignore that.

Now, one possibility is to enumerate all parse trees, which may be infinite or exponential, even with the best enumeration cost amortization techniques.

Another possibility is to produce a structure (called a shared parse-forest in the case of parsing) that can generate any parse-tree, with a cost linear in the size of the parse-tree being produced. This is actually what is done by most general CF parsers. In the case of Context-Free languages, this structure can be produced with cubic time and space complexity, even when the number of parses is infinite.

Hence, while enumerating all solutions to a problem may have a very high cost, it may be possible to produce at relatively low cost a structure that can easily enumerate all solutions. Such a structure may be a convenient representation if you actually intend further processing to select the most appropriate solutions according to further criteria.

Another possibility is to analyze the structure to see whether enumeration is tractable or not, before attempting to do it.

In the question asked, Raphael's answer tells you that the number of minimal paths may be exponential. So finding all minimal paths may be a good candidate for such a shared structure solution approach. Actually, I believe it is generally applicable to dynamic programming algorithms (possibly with some restrictions), so it should apply to Dijkstra's algorithm. Let $c(N,N')$ denote the length of the shortest path from $N$ to $N'$.

Basically, the idea is that, if a node $N$ is on a minimal path from source $S$ to target $T$, then any other path from $S$ to $N$ placing $N$ at the same distance from $S$ can be used to build a minimal path from source $S$ to target $T$. The same is true for $N$ and $T$.

A way to proceed is to compute the minimal distance from $S$ to all other nodes. Then you initialise a set $U$ of useful nodes with the node $T$, a set $E$ of useful edges as empty, and a set $V$ of visited nodes as empty.

Now for each node $N$ in $U$, you consider each node $N'$ connected to $N$ that is at a shorter distance from $S$. If $c(S,N')+c(N',N)=c(S,N)$ then you add $N'$ to $U$ (unless it is already in $U\cup V$) and you add a directed edge $(N',N)$ to $E$. Otherwise you do nothing. When all adjacent nodes $N'$ have been considered, the node $N$ is tranferred from the useful set $U$ to the visited set $V$, and you loop, looking at another node from $U$.

You stop when $U$ is empty, which eventually occurs, since no node is added to $U$ a second time.

The shared structure is a graph composed of all nodes in $V$ and all directed edges in $E$. It necessarily contains $S$ and $T$. The set of minimal solution is precisely the set of directed paths from $S$ to $T$ in that graph. They are easily followed since they are directed. Whether you enumerate those paths, or do anything else with them, is another story. Note that, up to the fact that its edges are directed, this graph is smaller than (or at worse equal to) the initial graph being analyzed, so that it is tractable.

Let $v$ and $e$ be respectively the number of nodes and edges. Each edge of the original graph is considered at most twice, and when it is processed the node $N'$ at the upstream end may have to be searched in $U\cup V$ at a cost $O(\log v)$. This gives a total extra cost of $O(e\log v)$, in addition to the initial computation of distances with Dijkstra's algorithm.

There are probably better ways of doing this, but that is the solution that came to me. Hopefully there are no bugs. I do think there is a more general way to describe such techniques, but my memory is what it is.