python - 使用 graph_tool 的所有最短路径

Question

我想知道 graph_tool 中是否有一个内置函数可用于查找从节点 s 到节点 t 的所有最短路径。

如果没有，有什么方法可以使用 shortest_distance() （在模块 graph_tool.topology 中）或 shortest_path() （在模块 graph_tool.topology 中）以某种方式（或任何其他内置函数）来计算所有最短路径只有其中一个，有效（我正在使用一个大约有 50 万个节点的图）。

Answer 1

图形工具中没有这样的功能。请注意，通常在大图上找到所有最短路径可能是不可行的，因为最短路径的数量将随着图的大小组合增长。

---

更新：该all_shortest_paths()函数最近已添加到库中，它完全符合要求：

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