Ford Fulkerson/Edmonds-Karp算法剩余流量重发问题排查

核心问题1：流量概念混淆 #

你看到的首次运行后所有通道总流量：110是所有边的流量之和，并非从源点M01到汇点EXIT的实际疏散总流量。代码中的max_flow变量才是真正的源汇总流量，它代表每分钟能从M01疏散到EXIT的学生数。

actual_total_flow的计算方式是把每条边的流量累加，比如一条路径M01→M02→M03→EXIT的流量为15，这条路径会被计算3次（三个边各计15），因此这个数值远大于实际的源汇流量，不能用来判断是否达到目标流量。

核心问题2：期望路径不存在 #

你提到的D01->D02->D04（对应代码中的M01->M02->M04）路径在当前图中没有对应的边。查看你的edges列表，只有M02→M03的边，没有M02→M04的边，算法自然无法找到这条路径。

核心问题3：最大流上限不足 #

当前图的源点M01所有出边的总容量为15+25+15=55，这意味着无论如何调整，最大源汇流量不可能超过55，你期望的120是无法达到的，除非修改图的结构来提升流量上限。

具体修改步骤 #

1. 修正流量判断逻辑
   在final_flow函数中，用max_flow替代actual_total_flow来判断是否达到目标流量：

   def final_flow(graph, source, sink, target_flow, edges, node_index):
       max_flow, search_count, door_flows = edmonds_karp(graph, source, sink)
       print(f"Maximum evacuation flow (students per minute): {max_flow}")
       print(f"Number of searches (BFS executions): {search_count}")
       actual_total_flow = sum(door_flows[node_index[room_a]][node_index[room_b]] for room_a, room_b, _ in edges)
       print(f"Total flow through all doors after first run: {actual_total_flow}")
       # 修改判断条件为max_flow
       if max_flow < target_flow:
           remaining_flow = target_flow - max_flow
           print(f"Total flow is {max_flow}. Remaining flow to send: {remaining_flow}")
   

2. 添加期望路径的边
   如果M02→M04是实际存在的路径，在edges列表中添加这条边（容量根据需求设置）：

   edges = [
       ("M01", "M02", 15),
       ("M02", "M03", 15),
       ("M02", "M04", 10),  # 新增这条边，对应你期望的路径
       ("M01", "M03", 25),
       ("M03", "EXIT", 15),
       ("M03", "M04", 15),
       ("M03", "M05", 5),
       ("M01", "M04", 15),
       ("M04", "M05", 25),
       ("M05", "EXIT", 25),
   ]
   

3. 提升最大流上限（若需达到120）
   要让源汇流量达到120，需要大幅调整图的容量，例如：

   • 增加M01的出边容量，比如将M01→M02、M01→M03、M01→M04的容量分别提升到40、40、40
   • 增加中间路径的容量，比如M02→M04、M04→M05、M05→EXIT的容量提升到40
   • 新增M04→EXIT的边并设置足够容量，分流M04的流量直接到汇点

内容的提问来源于stack exchange，提问作者StAndrews