ISPA算法求最大流python实现

以下是使用 ISPA 算法求解最大流的 Python 代码实现：

from collections import deque

def bfs(graph, s, t, parent):
    visited = [False] * len(graph)
    queue = deque()
    queue.append(s)
    visited[s] = True
    while queue:
        u = queue.popleft()
        for ind, val in enumerate(graph[u]):
            if not visited[ind] and val > 0:
                queue.append(ind)
                visited[ind] = True
                parent[ind] = u
    return visited[t]

def ispa(graph, source, sink):
    n = len(graph)
    parent = [-1] * n
    max_flow = 0
    while bfs(graph, source, sink, parent):
        path_flow = float("Inf")
        s = sink
        while s != source:
            path_flow = min(path_flow, graph[parent[s]][s])
            s = parent[s]
        max_flow += path_flow
        v = sink
        while v != source:
            u = parent[v]
            graph[u][v] -= path_flow
            graph[v][u] += path_flow
            v = parent[v]
    return max_flow

其中，`graph` 是一个二维列表，表示网络流图。`source` 表示源点，`sink` 表示汇点。函数首先利用 BFS 找到从源点到汇点的一条路径，然后遍历这条路径，找到路径上的最小流量，更新图上的边权值和最大流量。最后返回最大流量即可。

使用示例：

graph = [[0, 16, 13, 0, 0, 0],
         [0, 0, 10, 12, 0, 0],
         [0, 4, 0, 0, 14, 0],
         [0, 0, 9, 0, 0, 20],
         [0, 0, 0, 7, 0, 4],
         [0, 0, 0, 0, 0, 0]]

source = 0
sink = 5

max_flow = ispa(graph, source, sink)

print("Max Flow:", max_flow)

输出结果：

Max Flow: 23