计算G中任意两个顶点u，v之间的最短路径 [英] Calculating the shortest path between any two vertices u,v in G

问题描述

我想找到在图中任意两个顶点之间包含最短路径的集合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 itertools.combinations(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之间的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！