如何找到边缘容量满足需求的最短路径

Question

G是一个具有边容量的无向图。对于任意给定的input(SourceNode, TargetNode, demand)，如何找到路径中所有边都应满足capacity >= demand的所有路径。

我知道networkx有netowrk_simplex()或min_cost_flow()可以实现类似的功能，但它返回的路径是流的形式，而不是我想要的简单路径。

例如：

G = nx.Graph()
G.add_edge("a", "b", capacity=4)
G.add_edge("a", "c", capacity=10)
G.add_edge("b", "d", capacity=9)
G.add_edge("c", "d", capacity=5)

我想实现这个：

path = path(G, source, target, demand=5)
path
"[a,c,d]"

路径[a，b，d]不满足，因为边缘(a，b(容量4小于需求5。

如果有多个路径满足需求，则函数可以返回路径列表。

谢谢。

Answer 1

我认为解决这一问题的最简单方法是删除所有不符合标准的边，然后运行最短路径分析。

然而，我们可以使用"；受限视图"；对现有图形进行分析：

def path(graph, source, target, demand):
H = nx.restricted_view(
graph,
[], 
tuple((x, y) for x, y, attr in graph.edges(data = True) if attr['capacity'] < demand))
return [path for path in nx.all_shortest_paths(H, source, target, demand)]

restricted_view方法采用图的名称以及要删除的节点和边的可迭代项(我认为只允许边的元组(。由于没有删除任何节点，因此传入一个空列表[]

tuple生成器表达式使用x, y, attr表示节点属性的第一个节点、第二个节点和字典，并返回一组满足给定标准的边，然后在受限视图中删除这些边。

return语句包含列表理解，因为all_shortest_paths方法默认返回生成器对象。

根据您的标准进行测试：

desired_paths = path(G, 'a', 'd', 5)
print(desired_paths)
>>>[['a','c','d']]

为了进行额外的测试，我添加了两个边('a','e')和('e','d')，并确认输出随后变为[['a','c','d'],['a','e','d']]。