List all shortest paths between two vertices in a graph

[Beth Claire]

Hi,

Given an undirected graph G, and two vertices u and v of G, I want to list all paths from u to v with a length of d_G(u,v).  The built-in function shortest_simple_paths, despite its name, seems to list all simple paths from u to v.  One option is to filter the output of shortest_simple_paths by length, e.g.

list(filter(lambda x: len(x)== 1+G.distance(u,v)),G.shortest_simple_paths(u,v)))

However, this is extremely inefficient, since it tells sage to generate all simple paths and then discards most of them.  Is there a better way to get this information?

Thanks,

Beth

[Jean-Florent Raymond]

Hello,

The function shortest_simple_paths returns an iterator with paths sorted
by increasing length. Therefore if you only want paths of minimum
length, you can iterate over the result of shortest_simple_paths and
stop as soon as you encounter a longer path. That way you do not iterate
over all the (possibly many) irrelevant longer paths and, depending on
how shortest_simple_paths is implemented, you might even avoid to
compute them.

Something like that:

def shortest_paths_really(G, u, v):
"""Return all the shortest simple paths between u and v"""

uv_paths = G.shortest_simple_paths(u, v)
first_path = next(uv_paths) # a shortest path
dist = len(first_path)
yield first_path
for path in uv_paths:
if len(path) > dist:
# no need to go further: paths are too long for now on
return
yield path

It is not obvious that doing so is much faster than your solution: it
depends on the implementation of shortest_simple_paths, which I did not
look.
You can convince yourself that it saves some time at least by looking at
a graph where two vertices have few shortest paths and many longer paths
connecting them. For instance in graphs.CircularLadderGraph(n) there are
only two shortest paths connecting vertices 1 and n but exponentially
many of longer length.

sage: n = 10
sage: G = graphs.CircularLadderGraph(n)
sage: u, v = 1, n
sage: %timeit list(shortest_paths_really(G, u, v))
35.9 µs ± 159 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
sage: %timeit list(filter(lambda x: len(x) == 1+G.distance(u, v),
G.shortest_simple_paths(u, v)))
66.6 ms ± 180 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)


Jean-Florent.

Le 24/08/2021 à 01:39, Beth Claire a écrit :
> Hi,
> Given an undirected graph G, and two vertices u and v of G, I want to list
> all paths from u to v with a length of d_G(u,v). The built-in function
> shortest_simple_paths

> <https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.shortest_simple_paths>,
> despite its name, seems to list *all* simple paths from u to v. One option

[Beth Claire]

Thanks, that does exactly what I needed!  It is significantly faster and uses significantly less memory.

--Beth