Я хочу переслать оставшиеся сети от Форда Фулкерсона, ⇐ Python

[Anonymous]

С помощью этого кода ниже я получу результат.
Общий поток через все двери после первого запуска: 110.
Общий поток — 110. Оставшийся поток для отправки: 10
Но общий поток, который мне нужно отправить, составляет 120. Итак, я хочу отправить оставшиеся 10, но почему-то второй запуск не запускается. Какое условие мне следует изменить, чтобы это сделать? Я думаю, что способ поиска пути неправильный или неправильная обработка остаточного графа. В идеале последние 10 хотелось бы отправить через D01 -> D02 -> D04
Спасибо,
def build_graph(nodes, edges):
node_index = {node: i for i, node in enumerate(nodes)}
n = len(nodes)
graph = [[0] * n for _ in range(n)]
for room_a, room_b, capacity in edges:
graph[node_index[room_a]][node_index[room_b]] = capacity
return graph, node_index

def bfs(residual_graph, source, sink, parent):
visited = [False] * len(residual_graph)
queue = [source]
visited[source] = True
while queue:
u = queue.pop(0)
for v in range(len(residual_graph)):
if not visited[v] and residual_graph[v] > 0:
queue.append(v)
visited[v] = True
parent[v] = u
if v == sink:
return True
return False

def edmonds_karp(graph, source, sink):
residual_graph = [row[:] for row in graph]
parent = [-1] * len(graph)
max_flow = 0
search_count = 0
door_flows = [[0] * len(graph) for _ in range(len(graph))]
while bfs(residual_graph, source, sink, parent):
search_count += 1
path_flow = float('Inf')
s = sink
while s != source:
path_flow = min(path_flow, residual_graph[parent])
s = parent
max_flow += path_flow
v = sink
while v != source:
u = parent[v]
residual_graph[v] -= path_flow
residual_graph[v] += path_flow
door_flows[v] += path_flow
v = parent[v]
return max_flow, search_count, door_flows

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"\nTotal flow through all doors after first run: {actual_total_flow}")
if actual_total_flow < target_flow:
remaining_flow = target_flow - actual_total_flow
print(f"Total flow is {actual_total_flow}. Remaining flow to send: {remaining_flow}")

# Input data directly in the code
nodes = ["M01", "M02", "M03", "M04", "M05", "EXIT"]
edges = [
("M01", "M02", 15),
("M02", "M03", 15),
("M01", "M03", 25),
("M03", "EXIT", 15),
("M03", "M04", 15),
("M03", "M05", 5),
("M01", "M04", 15),
("M04", "M05", 25),
("M05", "EXIT", 25),
]
source = "M01"
target_flow = 120

# Build the graph and run the algorithm
graph, node_index = build_graph(nodes, edges)
source_index = node_index[source]
sink_index = node_index["EXIT"]
final_flow(graph, source_index, sink_index, target_flow, edges, node_index)


Подробнее здесь: https://stackoverflow.com/questions/792 ... -fulkerson