使用 NetworkX 计算 python 中的图权重

Question

我正在使用 networkx 计算有向加权图中两个顶点之间的最短距离（根据权重）。我认为 dijkstra_path_length 算法在这里使用是正确的，但我不明白我必须将什么作为权重的默认参数来获得我想要的结果。

import networkx as nx
G = nx.MultiDiGraph()
G.add_nodes_from(['A', 'B', 'C', 'D', 'E'])
G.add_edge('A', 'B', 5)
G.add_edge('B', 'C', 4)
G.add_edge('C', 'D', 8)
G.add_edge('D', 'C', 8)
G.add_edge('D', 'E', 6)
G.add_edge('A', 'D', 5)
G.add_edge('C', 'E', 2)
G.add_edge('E', 'B', 3)
G.add_edge('A', 'E', 7)

这是我输入的图表。我必须计算从 A 到 C 的最短路径（根据权重）（权重为 9 的 A-B-C），但无论我做什么，我得到的唯一答案是 2（边数，就好像图没有权重） .正确答案应该是9.

Answer 1

从您的代码中删除这一行

G.add_nodes_from(['A', 'B', 'C', 'D', 'E'])

Answer 2

问题是你必须写 "weight" 这个词才能将它分配给一条边。您正在为边缘添加标签，但没有添加权重。

当您计算节点 A 和 C 之间的距离时，下一个代码可以打印 9。

import networkx as nx
G = nx.MultiDiGraph()
G.add_nodes_from(['A', 'B', 'C', 'D', 'E'])

G.add_edge('A', 'B', weight=5)
G.add_edge('B', 'C', weight=4)
G.add_edge('C', 'D', weight=8)
G.add_edge('D', 'C', weight=8)
G.add_edge('D', 'E', weight=6)
G.add_edge('A', 'D', weight=5)
G.add_edge('C', 'E', weight=2)
G.add_edge('E', 'B', weight=3)
G.add_edge('A', 'E', weight=7)

print nx.dijkstra_path_length(G, source = 'A', target = 'C')

Answer 3

也许你可以尝试使用 nx.shortest_path()

使用 NetworkX 计算 python 中的图权重

calculating graph weight in python with NetworkX

python

graph

dijkstra

networkx