使用graph_tool找到所有最短路径

Question

我在想，graph_tool里有没有什么内置的函数可以用来找到从节点s到节点t的所有最短路径。

如果没有，那有没有办法可以用shortest_distance()（在graph_tool.topology模块里）或者shortest_path()（在graph_tool.topology模块里）之类的函数，或者其他的内置函数，来高效地计算出所有的最短路径，而不仅仅是其中一条呢？（我正在处理一个大约有五十万个节点的图。）

Answer 1

在graph-tool这个库里没有这样的功能。一般来说，在一个大图上找到所有最短路径可能是不可行的，因为随着图的大小增加，最短路径的数量会以组合的方式增长。

---

更新：最近这个库新增了一个all_shortest_paths()函数，正好可以完成所需的功能：

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