计算G中任意两个顶点u,v之间的最短路径

Question

我想找到包含图中任意两个顶点之间的最短路径的集合 S。以下代码工作正常，但我不确定是否有更有效的代码可以执行相同的功能。

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

Answer 1

当前代码的效率取决于g.get_shortest_paths. 通常的选择g.get_shortest_paths包括：

\n\n

\n
• Bellman\xe2\x80\x93Ford 算法，应在 运行O(VE)，
\n
• Dijkstra 算法O(V^2)，即使优化良好，O(Elog(v))也应在没有优化的情况下运行O(E+Vlog(E/V)log(V))。
\n

\n\n

代码的时间成本应该是迭代以来的g.get_shortest_paths时间成本。O(V^2)

\n\n

对于您的情况中的所有对最短路径问题，建议使用Floyd\xe2\x80\x93Warshall 算法，该算法使用动态规划来达到时间成本O(V^3)

\n\n

编辑：

\n\n

上面使用的符号：E表示图中的边数和V顶点数。

\n