All shortest paths using graph_tool

问题:

I was wondering if there is a built in function in graph_tool that can be used to find all shortest paths from node s to node t.

If not, is there any way that I can use shortest_distance() (in module graph_tool.topology), or shortest_path() (in module graph_tool.topology) somehow (or any other built-in function)to compute all the shortest path instead of only one of them, efficiently (I am working with a graph that has around half a million nodes).

回答1:

There is no such function in graph-tool. Note that in general finding all shortest paths on a large graph will probably be unfeasible, since the number of shortest paths will grow combinatorially with the size of the graph.

---

UPDATE: The all_shortest_paths() function has been recently added to the library, which does precisely what is requested:

https://graph-tool.skewed.de/static/doc/topology.html#graph_tool.topology.all_shortest_paths