如何在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

请注意，属性的名称不一定是length，它可以有其他名称，如weight、len或任何您喜欢的名称。