networkx 多路径 python

Question

我正在使用 networkx 库获取给定图中的所有最短路径，以尝试模拟等价多路径（就像 OSPF 所做的那样）：

例如，我想得到（给定下图）：

H.add_edge('R1','R2',weight=5)

H.add_edge('R1','R3',weight=5)

H.add_edge('R4','R2',weight=5)

H.add_edge('R4','R3',weight=5)

这个输出：

[['R1', 'R2', 'R4'], ['R1', 'R3', 'R4']]

这是可能的： [p for p in nx.all_shortest_paths(H,source='R1',target='R4')]

但是，如果我将边 R4-R3 中的权重更改为 10 ，all_shortest_paths 函数仍会显示所有路径。我的问题是：是否有任何函数可以根据权重显示所有最短路径或仅显示最短路径？

此致。

Answer 1

all_shortest_paths函数不考虑重量。但是，在这种情况下，可以通过将每条最短路径中的边的权重相加并选择最大值来获得您想要的结果。

初始化图形：

import networkx as nx

G = nx.Graph()
G.add_weighted_edges_from([('R1', 'R2', 5), ('R1', 'R3', 5), ('R4', 'R2', 5), ('R4', 'R3', 10)])

shortest_paths = np.array(list(nx.all_shortest_paths(G, source='R1', target='R4')))

使用列表理解计算路径中每条边的权重：

path_weights = np.array([sum([G.get_edge_data(path[edge], path[edge + 1])['weight'] for edge in range(len(path) - 1)]) for path in shortest_paths])

然后 select 来自 shortest_paths 的具有最大总权重的路径：

shortest_paths[path_weights == path_weights.max()]

Answer 2

由于您可以指定多个不同的属性用作权重，all_shortest_paths 不知道您要使用什么标签。所以默认情况下它只查看边数并忽略您创建的任何权重。它有一个可选参数，允许您提供权重。看看documentation。它由 all_shortest_paths(G, source, target, weight=None) 调用。所以你需要定义权重。

你的情况：

[p for p in nx.all_shortest_paths(H,source='R1',target='R4', weight = 'weight')]

将提供您想要的输出。

networkx 多路径 python

networkx multipath python

python

networkx