所有使用graph_tool的最短路径 [英] All shortest paths using graph_tool

问题描述

我想知道graph_tool中是否有内置函数可用于查找从节点s到节点t的所有最短路径。如果没有，有什么办法可以在某种程度上使用shortest_distance（）（在模块graph_tool.topology中）或shortest_path（）（在模块graph_tool.topology中）或任何其他内置函数）来计算所有最短路径，而不是只有其中一个（我正在处理一个有大约50万个节点的图）。

解决方案

图形工具中没有这样的功能。请注意，通常情况下，在大图上查找所有最短路径可能是不可行的，因为最短路径的数量会随着图的大小而增加。

---

更新： all_shortest_paths（）函数最近已被添加到库中， ：

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

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).

解决方案

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

这篇关于所有使用graph_tool的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！