最大流,最小费最大流问题 python
徐少华 算法设计与分析 P145
解题思路
解题算法
最小费用最大流: 解法 I
步骤一:利用最大流算法, 将网络的流量调整到最大流
步骤二: 构建伴随网络流f的增流网络 D_f
步骤三: 在增流网络 D_f 中, 查找关于费用的负回路, 令 \(θ=minc_ij^' (c_ij^' 为负回路中各弧的容量)\), 若不存在负回路, 则说明当前网络流已经是最小费用流, 结束算法
步骤四: 针对负回路对应网络D中的圈, 若该圈是增流圈, 则把增流圈方向上与负回路方向一 致的所有弧的流量加上 θ , 把增流圈方向上与负回路方向相反的所有弧的流量减去 θ ; 若该圈不是增流圈, 则转到步骤二
流程图
代码实现
import itertools
class Node:
def __init__(self, name):
"""
:param name:节点的名字
"""
self.name = name
self.next_nodes = set()
self.prev_nodes = set()
self.tag = None
def add_next_node(self, next_node):
"""
添加后向节点
:param next_node:
:return:
"""
self.next_nodes.add(next_node)
def add_prev_node(self, prev_node):
"""
添加前向节点
:param prev_node:
:return:
"""
self.prev_nodes.add(prev_node)
def update_tag(self, tag):
self.tag = tag
def del_tag(self):
self.tag = None
def __str__(self):
str_node = f"{self.name} "f"\t tag:{self.tag} "f"\t next_node:{[i.name for i in self.next_nodes]} "f"\t prev_node:{[j.name for j in self.prev_nodes]} "
return str_node
class Graph:
def __init__(self, nodes, edges):
self.nodes = dict()
for i in nodes:
self.nodes[i] = Node(i)
self.edges = dict()
for i in edges:
start = i[0]
end = i[1]
weight = i[2]
self.edges[(i[0], i[1])] = Edge(start, end, weight)
self.nodes[start].add_next_node(self.nodes[end])
self.nodes[end].add_prev_node(self.nodes[start])
else:
# 查找首尾节点
for i in self.nodes.values():
if i.prev_nodes == set():
self.head_node = i
if i.next_nodes == set():
self.tail_node = i
def get_node_names(self):
return list(self.nodes.keys())
def get_edge_names(self):
return list(self.edges.keys())
def get_nodes(self):
return list(self.nodes.values())
def get_costs(self):
return sum(i.weight[1] * i.weight[2] for i in self.edges.values())
def __str__(self):
nodes_str = "Nodes:" + str([i.name for i in self.nodes.values()])
edges_str = "Edges:\n\t" + "\n\t".join([str(i) for i in self.edges.values()])
return nodes_str + "\n" + edges_str
def clean_node_tag(self):
# 清除所有节点的标号
for i in self.nodes.keys():
self.nodes[i].update_tag(None)
def update_flow(self, neg_loop, theta):
for i in range(len(neg_loop)):
start = neg_loop[i - 1].name
end = neg_loop[i].name
key = (start, end)
if key in self.edges:
# 正向弧
weight = list(self.edges[key].weight)
weight[1] += theta
else:
key = tuple(reversed(key))
weight = list(self.edges[key].weight)
weight[1] -= theta
self.edges[key].weight = tuple(weight)
def is_add_loop(self, neg_loop):
# 判断负回路是否是增流圈
for i in range(len(neg_loop)):
start = neg_loop[i - 1].name
end = neg_loop[i].name
key = (start, end)
if key in self.edges:
# 正向弧
weight = list(self.edges[key].weight)
if not weight[0] > weight[1]:
return False
else:
key = tuple(reversed(key))
weight = list(self.edges[key].weight)
if weight[1] == 0:
return False
else:
return True
def find_loop(self):
# 寻找回路
# 构成(负)回路至少两3个点
for i in range(3, len(self.nodes) + 1):
for j in itertools.permutations(self.nodes.values(), i):
if is_loop(j):
yield j
def find_neg_loop(self):
"""
寻找负回路
:return: 【迭代器】 一个负回路
"""
mat = []
for i in self.find_loop():
val = 0
min_theta = inf
for j in range(len(i)):
weight = self.edges[(i[j - 1].name, i[j].name)].weight
val += weight[1]
min_theta = min(min_theta, weight[0])
if val < 0:
l = set([j.name for j in i])
if l not in mat:
mat.append(l)
yield i, min_theta
def find_chain(self):
"""
查找所有链(链的起始点为起点,结束点为收点,路径但忽略方向)
:param self:
:return:
"""
head_node = self.head_node
tail_node = self.tail_node
def gen_full_chain(u, u_tag_path):
full_chain = [self.head_node]
full_chain.extend(u)
full_chain.append(self.tail_node)
u_tag_path.append(True)
return full_chain, u_tag_path
nodes_ex = self.get_nodes()
nodes_ex.remove(head_node)
nodes_ex.remove(tail_node)
all_path_u = []
for i in range(1, len(nodes_ex)):
all_path_u.extend(list(itertools.permutations(nodes_ex, i)))
all_chain_u = all_path_u
# real_chain = []
for i in all_chain_u:
if i[0] not in head_node.next_nodes or i[-1] not in tail_node.prev_nodes:
# 构不成一条链
continue
tag_path = [True]
# 标注在图上的方向,是正向还是反向
if len(i) == 1:
# 只有一个中间节点的情况
# real_chain.append(i)
yield gen_full_chain(i, tag_path)
continue
for j in range(1, len(i)):
if i[j] in i[j - 1].next_nodes:
# 前项弧
tag_path.append(True)
elif i[j] in i[j - 1].prev_nodes:
tag_path.append(False)
# 后向弧
else:
break
else:
# real_chain.append(i)
yield gen_full_chain(i, tag_path)
# return real_chain
def find_expanded_chain(self):
"""
查找一条增广链
:param self: 图
:return:
"""
chains = self.find_chain() # 返回迭代器
for chain, chain_direction in chains:
for j in range(len(chain_direction)):
k = (chain[j].name, chain[j + 1].name)
if chain_direction[j]:
# 前项弧,容量小于容量
weight = self.edges[k].weight
if not weight[0] > weight[1]:
break
else:
# 后项弧,流量大于0
k = tuple(reversed(k))
weight = self.edges[k].weight
if not weight[1] > 0:
break
else:
return chain, chain_direction
else:
return False, False
def max_flow_by_tag(self, show_detail=False):
"""
标号法寻找最大流
:param show_detail:
:param self:
:return: 无返回值,引用传递g
"""
while True:
# 寻找增广链
chain, chain_direction = self.find_expanded_chain()
if chain:
# 对增广链进行标号
chain[0].update_tag(tag=("0", inf, True))
min_theta = inf
for j in range(len(chain_direction)):
k = (chain[j].name, chain[j + 1].name)
if chain_direction[j]:
# 前项弧标号 v_prev,容量-流量,true
weight = self.edges[k].weight
dig = weight[0] - weight[1]
else:
# 后项弧标号 v_prev,流量,False
k = tuple(reversed(k))
weight = self.edges[k].weight
dig = weight[1]
min_theta = min(dig, min_theta)
tag = (chain[j].name, dig, False)
chain[j + 1].update_tag(tag)
# 调整流量
for j in range(len(chain_direction)):
k = (chain[j].name, chain[j + 1].name)
if chain_direction[j]:
# 前项弧增大流量,加上 Θ
weight = self.edges[k].weight
new_weight = (weight[0], weight[1] + min_theta, weight[2])
else:
# 后项弧减小流量,减去 Θ
k = tuple(reversed(k))
weight = self.edges[k].weight
new_weight = (weight[0], weight[1] - min_theta, weight[2])
self.edges[k].update_weight(new_weight)
self.clean_node_tag()
if show_detail:
print("调整流量后的图:")
print(self)
else:
break
def flow_augment(self):
"""
构建增流网络
:return:
"""
nodes = self.get_node_names()
# 先把点复制出来
edges = []
# 检查边是否是零流弧、饱和弧、非饱和弧
for i in self.get_edge_names():
weight = self.edges[i].weight
if weight[1] == 0:
# 零流弧,构建同向弧
new_weight = (weight[0], weight[2])
edges.append((i[0], i[1], new_weight))
elif weight[0] == weight[1]:
# 饱和弧,构建反向弧
new_weight = (weight[1], -weight[2])
edges.append((i[1], i[0], new_weight))
else:
# 不饱和弧,同时构建同向弧和反向弧
# 同向弧
new_weight1 = (weight[0] - weight[1], weight[2])
edges.append((i[0], i[1], new_weight1))
# 反向弧
new_weight2 = (weight[1], -weight[2])
edges.append((i[1], i[0], new_weight2))
return Graph(nodes=nodes, edges=edges)
inf = 999999
class Edge:
def __init__(self, start, end, weight):
"""
:param start: 起始点
:param end: 终点
:param weight: 权重
"""
self.start = start
self.end = end
self.weight = weight
def update_weight(self, weight):
"""
更新权重
:param weight:
:return:
"""
self.weight = weight
def __str__(self):
return str(self.start) + " -" + str(list(self.weight)) + "-> " + str(self.end)
def is_loop(lis):
if lis[0] not in lis[-1].next_nodes:
return False
for i in range(1, len(lis)):
if lis[i] not in lis[i - 1].next_nodes:
return False
else:
return True
# 生成图
g1 = Graph(nodes=['vs', 'v1', 'v2', 'v3', 'vt'],
edges=[('vs', 'v1', (10, 0, 4)),
('vs', 'v2', (8, 0, 1)),
('v2', 'v1', (5, 0, 2)),
('v1', 'vt', (7, 0, 1)),
('v2', 'v3', (10, 0, 3)),
('v1', 'v3', (2, 0, 6)),
('v3', 'vt', (4, 0, 2))])
# 调整到最大流
g1.max_flow_by_tag()
while True:
# 构建增流网络
df = g1.flow_augment()
print("增流网络:\n", df)
neg_loops = [(neg_loop, theta) for neg_loop, theta in df.find_neg_loop()]
if len(neg_loops) > 0:
neg_loop, theta = neg_loops[0]
if g1.is_add_loop(neg_loop):
# 是增流圈
g1.update_flow(neg_loop=neg_loop, theta=theta)
print("更新后的图:\n", df)
else:
break
print(g1)
print("最小花费", g1.get_costs())
输出
增流网络:
Nodes:['vs', 'v1', 'v2', 'v3', 'vt']
Edges:
vs -[1, 4]-> v1
v1 -[9, -4]-> vs
vs -[6, 1]-> v2
v2 -[2, -1]-> vs
v2 -[5, 2]-> v1
vt -[7, -1]-> v1
v2 -[8, 3]-> v3
v3 -[2, -3]-> v2
v3 -[2, -6]-> v1
vt -[4, -2]-> v3
更新后的图:
Nodes:['vs', 'v1', 'v2', 'v3', 'vt']
Edges:
vs -[1, 4]-> v1
v1 -[9, -4]-> vs
vs -[6, 1]-> v2
v2 -[2, -1]-> vs
v2 -[5, 2]-> v1
vt -[7, -1]-> v1
v2 -[8, 3]-> v3
v3 -[2, -3]-> v2
v3 -[2, -6]-> v1
vt -[4, -2]-> v3
增流网络:
Nodes:['vs', 'v1', 'v2', 'v3', 'vt']
Edges:
vs -[6, 4]-> v1
v1 -[4, -4]-> vs
vs -[1, 1]-> v2
v2 -[7, -1]-> vs
v1 -[5, -2]-> v2
vt -[7, -1]-> v1
v2 -[8, 3]-> v3
v3 -[2, -3]-> v2
v3 -[2, -6]-> v1
vt -[4, -2]-> v3
更新后的图:
Nodes:['vs', 'v1', 'v2', 'v3', 'vt']
Edges:
vs -[6, 4]-> v1
v1 -[4, -4]-> vs
vs -[1, 1]-> v2
v2 -[7, -1]-> vs
v1 -[5, -2]-> v2
vt -[7, -1]-> v1
v2 -[8, 3]-> v3
v3 -[2, -3]-> v2
v3 -[2, -6]-> v1
vt -[4, -2]-> v3
增流网络:
Nodes:['vs', 'v1', 'v2', 'v3', 'vt']
Edges:
vs -[6, 4]-> v1
v1 -[4, -4]-> vs
vs -[1, 1]-> v2
v2 -[7, -1]-> vs
v2 -[2, 2]-> v1
v1 -[3, -2]-> v2
vt -[7, -1]-> v1
v2 -[6, 3]-> v3
v3 -[4, -3]-> v2
v1 -[2, 6]-> v3
vt -[4, -2]-> v3
更新后的图:
Nodes:['vs', 'v1', 'v2', 'v3', 'vt']
Edges:
vs -[6, 4]-> v1
v1 -[4, -4]-> vs
vs -[1, 1]-> v2
v2 -[7, -1]-> vs
v2 -[2, 2]-> v1
v1 -[3, -2]-> v2
vt -[7, -1]-> v1
v2 -[6, 3]-> v3
v3 -[4, -3]-> v2
v1 -[2, 6]-> v3
vt -[4, -2]-> v3
增流网络:
Nodes:['vs', 'v1', 'v2', 'v3', 'vt']
Edges:
vs -[7, 4]-> v1
v1 -[3, -4]-> vs
v2 -[8, -1]-> vs
v2 -[1, 2]-> v1
v1 -[4, -2]-> v2
vt -[7, -1]-> v1
v2 -[6, 3]-> v3
v3 -[4, -3]-> v2
v1 -[2, 6]-> v3
vt -[4, -2]-> v3
Nodes:['vs', 'v1', 'v2', 'v3', 'vt']
Edges:
vs -[10, 3, 4]-> v1
vs -[8, 8, 1]-> v2
v2 -[5, 4, 2]-> v1
v1 -[7, 7, 1]-> vt
v2 -[10, 4, 3]-> v3
v1 -[2, 0, 6]-> v3
v3 -[4, 4, 2]-> vt
最小花费 55
标签:最大,weight,python,self,v1,v2,v3,小费,nodes
From: https://www.cnblogs.com/boran/p/16948902.html