我正在使用NetworkX来解决具有多个源和接收器的最大流量问题。我发现了一个在 NetworkX 中运行良好的函数,max_cost_flow
但我遇到的问题是它要求净需求为零,换句话说,任何接收器都不应低于它的需要,否则会引发错误。
我可以使用什么(或如何修改此算法)来允许它计算最佳可能流量,而不一定满足所有条件?
根据 kraskevich 的建议:
import networkx as nx
def convert(graph):
allNodes = graph.nodes()
newSource = len(allNodes) + 1
newSink = len(allNodes) + 2
graph.add_node(newSource)
graph.add_node(newSink)
for currentNode in allNodes:
demand = graph.node[currentNode]['demand']
if demand < 0 :
graph.add_edge(newSource, currentNode, weight=0, capacity=demand)
if demand > 0:
graph.add_edge(newSink, currentNode, weight=0, capacity=demand)
return graph
g = nx.DiGraph()
g.add_node(1, demand = 1)
g.add_node(2, demand = -2)
g.add_node(3, demand = 2)
g.add_node(4, demand = -4)
g.add_edge(1, 2, weight=4, capacity=100)
g.add_edge(1, 4, weight=3, capacity=100)
g.add_edge(3, 2, weight=5, capacity=100)
g.add_edge(3, 4, weight=2, capacity=100)
g.add_edge(3, 1, weight=1)
newGraph = convert(g)
print(nx.max_flow_min_cost(g, newGraph.nodes()[-2],newGraph.nodes()[-1]))