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不知道要使用哪个标签。因此，在默认情况下，它只会查看边的数目，而忽略了所创建的任何权重。它有一个可选的参数，允许您提供权重。看一看文档。这是由all_shortest_paths(G, source, target, weight=None)调用的。所以你需要定义重量。

就你而言：

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

将提供所需的输出。

Answer 2

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])

然后从具有最大总权重的shortest_paths中选择路径：

shortest_paths[path_weights == path_weights.max()]