如何更快地计算给定节点的最短路径长度？

Question

我试图通过这段代码找到给定节点的最大距离。

import networkx as nx

G= nx.read_gpickle("Database/Pickle/test.gpickle")

word = ['a', 'b', 'c', 'd', 'e', 'g', 'h', 't', 'i', 'j', 'k']
maxdistance = 0

for source in range(len(word)):
    for target in range(source+1, len(word)):

        distance = nx.dijkstra_path_length(G, word[source], word[target], weight='cost')
        if maxdistance < distance:
            maxdistance = distance

print(maxdistance)

我认为找到每对的最短路径需要一点时间，所以有没有更快找到距离的方法。

Answer 1

有一个函数可以找到从源节点到任何其他节点的距离。您可以为每个源节点调用该函数。函数 returns 距离字典。 Select 单词列表中的目标，并找到其中最大的：

maxdistance = 0
word = set(word) # Sets are faster than lists
for source in word:
    distances = nx.single_source_shortest_path_length(G, source)
    maxdistance = max(maxdistance,
                      max(v for k,v in distances.items() if k in word)

如果word是图中所有节点的集合，求出图的直径：

maxdistance = nx.diameter(G)

如何更快地计算给定节点的最短路径长度？

How to calculate shortest path lenght of given node faster?

python

networkx

shortest-path