如何在Networkx中指定边长以计算最短距离？

Question

我有一个节点和边的列表,但我希望有些边长为2而不是1.因此,当使用内置算法计算节点之间的距离时,它返回

例如,如果我有(1,2),(2*,3),(4*,5)作为节点之间的边,其中带星号的节点之间的距离长度为2,(1,2之间的距离) )应为1,(2,3)应为2而不是1,然后(1,5)之间的距离应为5而不是3.

添加节点我尝试G.add_edge(4,5,length=2)但nx.shortest_path_length(G,source=4,target=5))仍返回1而不是2.如何指定边长？

Answer 1

您需要length在边缘附加属性,然后在找到最短路径时指定要按这些长度加权:

# Had to add an edge from 3 to 4 to your example edges
#   or there's no path from 1 to 5
edges = [(1, 2, 1), (2, 3, 2), (3, 4, 1), (4, 5, 2)]

G = networkx.Graph()

for start, end, length in edges:
    # You can attach any attributes you want when adding the edge
    G.add_edge(start, end, length=length)

networkx.shortest_path_length(G, 1, 5, weight='length')
Out[8]: 6