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

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

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

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)