我有一个从S到T的有向图
我想找出路线(S,A,C,E,T)和它的容量之和(1+2+3+1=7),所以这个和是最大的。
我试过networkx.algorithms.flow.fordúfulkerson,但我不知道如何得到从S到t的单向方向
我的环境:
示例.py
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import matplotlib.pylab as p
import networkx as nx
if __name__ == '__main__':
DG = nx.DiGraph()
DG.add_edge('S', 'a', capacity=1)
DG.add_edge('a', 'b', capacity=1)
DG.add_edge('a', 'c', capacity=2)
DG.add_edge('b', 'd', capacity=1)
DG.add_edge('b', 'e', capacity=2)
DG.add_edge('c', 'e', capacity=3)
DG.add_edge('c', 'f', capacity=2)
DG.add_edge('d', 'T', capacity=1)
DG.add_edge('e', 'T', capacity=1)
DG.add_edge('f', 'T', capacity=1)
result = nx.algorithms.flow.ford_fulkerson(DG, 'S', 'T')
print(result.size(weight='capacity')) # 15.0, but I want 7.
pos = nx.spectral_layout(DG)
nx.draw(DG, pos)
nx.draw_networkx_labels(DG, pos)
nx.draw_networkx_edge_labels(DG, pos)
p.show()
# This shows a partly bidirectional graph, which is not what I want.
pos = nx.spectral_layout(result)
nx.draw(result, pos)
nx.draw_networkx_labels(result, pos)
nx.draw_networkx_edge_labels(result, pos)
p.show()
负重对约翰逊有效。在您的情况下,修改为:
要找到最长的路径,请使用
结果为:
johnson: ['S', 'a', 'c', 'e', 'T']
我的环境:
Networkx 1.11 docs for johnson
我想我找到了解决办法。
对于Dijkstra算法,使用负重通常不起作用。 将显示此错误
ValueError: ('Contradictory paths found:', 'negative weights?')
。应区分“最长路径”和“最大和路径”问题。
这里的答案是:使用all_simple_paths的How to find path with highest sum in a weighted networkx graph?。
注意,在函数
all_simple_paths(G, source, target, cutoff=None)
中,使用cutoff
参数(整数)可以帮助将搜索深度从source
限制到target
。它还控制我们要找到的路径的长度。相关问题 更多 >
编程相关推荐