计算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 的典型选择包括：

Bellman–Ford algorithm，应运行在 O(VE)，
Dijkstra's algorithm，在没有优化的情况下运行在 O(V^2)，O(Elog(v)) 甚至 O(E+Vlog(E/V)log(V)) 如果优化良好。

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

对于您所遇到的全对最短路径问题，建议使用Floyd–Warshall algorithm，它使用动态规划来达到O(V^3)

的时间成本

已编辑：

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

Answer 2

我前段时间在 python 中为给定的图表实现了未优化的 Dijkstra's algorithm：

def define_undirected_G(): 
   m = 10 #nodes
   G = [set() for _ in range(m)]  #create a set for each node 
                                  #and save the adjacent nodes inside these sets 
   G[0] |= {1,2}
   G[1] |= {0,2,3,4}
   G[2] |= {0,1,4,6,7}
   G[3] |= {1,4}
   G[4] |= {1,2,3,5}
   G[5] |= {4}
return G

def dijkstra(G,s): 
       m = len(G) 
       d = [None]*m  #Shortest paths from s to all nodes in G
       d[s] = 0      #Path cost=0 for the startnode
       Q = {u for u in range(m)}   #Q = All nodes u in G
       while Q: # Selection of node with min d-value
           (_,v) = min({(d[u],u) for u in Q if d[u]!= None})
           Q.remove(v) 
           for u in G[v]: #Check Update for all adjacent nodes
               alt = d[v] + G[v][u]   #Greedy-selection-rule            
               if d[u]==None or alt < d[u]:   #Update
                   d[u] = alt 
       return d

如果你想要一个集合 S 包含来自 G 中所有节点的所有最短路径，那么只需计算 G 中 s 的 dijkstra(G,s) 并将结果添加到 S。

注意：优化会联合查找数据结构和的变化在 G[v] 中，因为不需要检查已经更新并从未触及的节点集 Q 中删除的相邻节点，因为贪婪算法是贪婪的。

希望对您有所帮助。

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

Calculating the shortest path between any two vertices u,v in G

python

igraph