我想找到在图中任意两个顶点之间包含最短路径的集合S. 以下代码可以正常工作,但是我不确定是否有更高效的代码具有相同的功能.
I want to find the set S that contains the shortest path between any two vertices in a graph. The following code is working fine, but I am not sure if there is a more efficient code that does the same functionality.
def getShortestPaths(g): shortestPaths = [] #iterate all pair of nodes for x in itertoolsbinations(g.vs["label"], 2): path = len(g.get_shortest_paths(v=x[0],to=x[1])[0]) - 1 shortestPaths.append(path) return shortestPaths推荐答案
当前代码的效率取决于g.get_shortest_paths的实现.通常,g.get_shortest_paths的选择包括:
The efficiency of your current code depends on the implementation of g.get_shortest_paths. Typically choices of g.get_shortest_paths include:
- Bellman-Ford算法,该算法应在O(VE)上运行,
- Dijkstra的算法,该算法无需优化即可在O(V^2)上运行,O(Elog(v))甚至优化后的O(E+Vlog(E/V)log(V)).
- Bellman–Ford algorithm, which shall run at O(VE),
- Dijkstra's algorithm, which shall run at O(V^2) without optimization, O(Elog(v)) or even O(E+Vlog(E/V)log(V)) if well-optimized.
自迭代以来,代码的时间成本应为g.get_shortest_paths乘O(V^2)的成本.
And the time cost of your code shall be the cost of g.get_shortest_paths times O(V^2) since the iteration.
对于您所遇到的所有对最短路径问题,弗洛伊德–沃舍尔建议使用算法,该算法使用动态编程来达到O(V^3)
For all-pairs-shortest-path problem in your case, Floyd–Warshall algorithm is suggested which uses dynamic programming to reach a time cost of O(V^3)
已编辑
上面使用的符号:E表示边的数量,V表示图形中的顶点数量.
Notations used above: E for number of edges, and V for number of vertices in the graph.
更多推荐
计算G中任意两个顶点u,v之间的最短路径
发布评论