带边限的图遍历：多源多汇最大流求解问题求助

我们有一个包含三种节点的图：普通节点（normal）、源节点（source）、目标节点（destination）。源节点会产生固定上限的流体，经邻边和普通节点流向目标节点，每条边有最大流量限制，目标节点有处理容量上限，需要计算流入目标节点的总流体量。

举个示例场景：0号、1号是源节点，输出上限分别为3和9；2号、3号是目标节点，处理容量分别为5和3；4号是普通节点。预期总流入量为6，但用Edmonds-Karp算法实现后结果错误：

• 初始版本代码输出12，远高于预期；
• 更新版本代码输出7，仍不符合预期。

初始版本代码 #

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include <unordered_map>

using namespace std;

int bfs(const unordered_map<int, unordered_map<int, int>>& residual_graph, int source, int sink, vector<int>& parent) {
    vector<bool> visited(residual_graph.size(), false);
    queue<int> q;

    q.push(source);
    visited[source] = true;
    parent[source] = -1;

    while (!q.empty()) {
        int current = q.front();
        q.pop();
        for (const auto& neighbor : residual_graph.at(current)) {
            int neighbor_node = neighbor.first;
            int capacity = neighbor.second;

            if (!visited[neighbor_node] && capacity > 0) {
                q.push(neighbor_node);
                parent[neighbor_node] = current;
                visited[neighbor_node] = true;
                if (neighbor_node == sink) {
                    return true;
                }
            }
        }
    }

    return false;
}

int edmonds_karp(unordered_map<int, unordered_map<int, int>>& graph, int source, int sink) {
    unordered_map<int, unordered_map<int, int>> residual_graph = graph;
    vector<int> parent(graph.size());
    int max_flow = 0;

    while (bfs(residual_graph, source, sink, parent)) {
        int path_flow = numeric_limits<int>::max();

        for (int v = sink; v != source; v = parent[v]) {
            int u = parent[v];
            path_flow = min(path_flow, residual_graph[u][v]);
        }

        for (int v = sink; v != source; v = parent[v]) {
            int u = parent[v];
            residual_graph[u][v] -= path_flow;
            residual_graph[v][u] += path_flow;
        }

        max_flow += path_flow;
    }

    return max_flow;
}

int main() {
    unordered_map<int, unordered_map<int, int>> graph = {
        {0, {{1, 3}, {2, 9}}},
        {1, {{3, 3}}},
        {2, {{4, 4}, {3, 5}}},
        {3, {{4, 2}}},
        {4, {}},
    };

    // Assuming 0 and 1 are the source nodes and 2 and 3 are the destination nodes
    int source = 0;
    int sink = 2;
    int max_flow1 = edmonds_karp(graph, source, sink);

    source = 1;
    sink = 3;
    int max_flow2 = edmonds_karp(graph, source, sink);

    cout << "Total fluid into destination nodes: " << (max_flow1 + max_flow2) << endl;

    return 0;
}

更新版本代码 #

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include <unordered_map>

using namespace std;

int bfs(const unordered_map<int, unordered_map<int, int>>& residual_graph, int source, int sink, vector<int>& parent) {
    vector<bool> visited(residual_graph.size(), false);
    queue<int> q;

    q.push(source);
    visited[source] = true;
    parent[source] = -1;

    while (!q.empty()) {
        int current = q.front();
        q.pop();
        for (const auto& neighbor : residual_graph.at(current)) {
            int neighbor_node = neighbor.first;
            int capacity = neighbor.second;

            if (!visited[neighbor_node] && capacity > 0) {
                q.push(neighbor_node);
                parent[neighbor_node] = current;
                visited[neighbor_node] = true;
                if (neighbor_node == sink) {
                    return true;
                }
            }
        }
    }

    return false;
}

int edmonds_karp(unordered_map<int, unordered_map<int, int>>& graph, int source, int sink) {
    unordered_map<int, unordered_map<int, int>> residual_graph = graph;
    vector<int> parent(graph.size());
    int max_flow = 0;

    while (bfs(residual_graph, source, sink, parent)) {
        int path_flow = numeric_limits<int>::max();

        for (int v = sink; v != source; v = parent[v]) {
            int u = parent[v];
            path_flow = min(path_flow, residual_graph[u][v]);
        }

        for (int v = sink; v != source; v = parent[v]) {
            int u = parent[v];
            residual_graph[u][v] -= path_flow;
            residual_graph[v][u] += path_flow;
        }

        max_flow += path_flow;
    }

    return max_flow;
}

int main() {
    unordered_map<int, unordered_map<int, int>> graph = {
        {0, {{1, 3}, {2, 9}}},
        {1, {{3, 3}}},
        {2, {{4, 4}, {3, 5}}},
        {3, {{4, 2}, {6, 3}}},
        {4, {{6, 4}}},
        {5, {{0, 12}, {1, 3}}},
        {6, {}},
    };

    int source = 5;
    int sink = 6;
    int total_flow = edmonds_karp(graph, source, sink);

    cout << "Total fluid into destination nodes: " << total_flow << endl;

    return 0;
}

问题根源 #

1. 初始版本错误：分开计算单源单汇的流量再相加，忽略了不同源汇之间的流量竞争（比如同一条边会被多次计算可用容量），导致结果偏大。
2. 更新版本错误：虽然引入了超级源和超级汇，但错误设置了超级源到源节点的容量（比如给0号节点设了12，远超其实际输出上限3），且未正确建模目标节点的处理容量，导致结果不准确。

正确处理步骤 #

多源多汇的最大流问题，标准解法是通过超级源点和超级汇点将问题转化为单源单汇问题：

• 创建超级源点，向每个实际源节点连一条边，边的容量等于对应源节点的输出上限；
• 创建超级汇点，让每个实际目标节点向超级汇点连一条边，边的容量等于对应目标节点的处理容量；
• 对新构建的图运行Edmonds-Karp算法，计算超级源到超级汇的最大流，即为流入目标节点的总流体量。

正确实现代码 #

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include <unordered_map>

using namespace std;

bool bfs(const unordered_map<int, unordered_map<int, int>>& residual_graph, int source, int sink, vector<int>& parent, const vector<int>& all_nodes) {
    // 使用unordered_map存储访问状态，适配不连续的节点编号
    unordered_map<int, bool> visited;
    for (int node : all_nodes) {
        visited[node] = false;
    }
    queue<int> q;

    q.push(source);
    visited[source] = true;
    parent[source] = -1;

    while (!q.empty()) {
        int current = q.front();
        q.pop();
        // 跳过没有邻边的节点
        if (residual_graph.find(current) == residual_graph.end()) {
            continue;
        }
        for (const auto& neighbor : residual_graph.at(current)) {
            int neighbor_node = neighbor.first;
            int capacity = neighbor.second;

            if (!visited[neighbor_node] && capacity > 0) {
                q.push(neighbor_node);
                parent[neighbor_node] = current;
                visited[neighbor_node] = true;
                if (neighbor_node == sink) {
                    return true;
                }
            }
        }
    }

    return false;
}

int edmonds_karp(unordered_map<int, unordered_map<int, int>>& graph, int source, int sink, const vector<int>& all_nodes) {
    unordered_map<int, unordered_map<int, int>> residual_graph = graph;
    // 预分配足够大的parent数组，适配节点编号范围
    vector<int> parent(100);
    int max_flow = 0;

    while (bfs(residual_graph, source, sink, parent, all_nodes)) {
        int path_flow = numeric_limits<int>::max();

        // 计算当前增广路的最小剩余容量
        for (int v = sink; v != source; v = parent[v]) {
            int u = parent[v];
            path_flow = min(path_flow, residual_graph[u][v]);
        }

        // 更新残差网络
        for (int v = sink; v != source; v = parent[v]) {
            int u = parent[v];
            residual_graph[u][v] -= path_flow;
            residual_graph[v][u] += path_flow;
        }

        max_flow += path_flow;
    }

    return max_flow;
}

int main() {
    // 原始图的边容量定义
    unordered_map<int, unordered_map<int, int>> graph = {
        {0, {{1, 3}, {2, 9}}},
        {1, {{3, 3}}},
        {2, {{4, 4}, {3, 5}}},
        {3, {{4, 2}}},
        {4, {}},
    };

    // 源节点及其输出上限
    unordered_map<int, int> sources = {{0, 3}, {1, 9}};
    // 目标节点及其处理容量
    unordered_map<int, int> destinations = {{2, 5}, {3, 3}};

    // 定义超级源和超级汇的编号（选未使用的编号）
    const int SUPER_SOURCE = 10;
    const int SUPER_SINK = 11;

    // 超级源连接所有源节点
    for (const auto& src_pair : sources) {
        graph[SUPER_SOURCE][src_pair.first] = src_pair.second;
    }

    // 所有目标节点连接到超级汇
    for (const auto& dest_pair : destinations) {
        graph[dest_pair.first][SUPER_SINK] = dest_pair.second;
    }

    // 收集所有节点，用于BFS初始化访问状态
    vector<int> all_nodes = {0, 1, 2, 3, 4, SUPER_SOURCE, SUPER_SINK};

    // 计算最大流
    int total_flow = edmonds_karp(graph, SUPER_SOURCE, SUPER_SINK, all_nodes);

    cout << "Total fluid into destination nodes: " << total_flow << endl;

    return 0;
}

代码说明 #

• 超级节点建模：正确将源节点的输出上限、目标节点的处理容量转化为边的容量，符合最大流模型的要求；
• BFS适配：使用unordered_map存储访问状态，避免节点编号不连续导致的数组越界问题；
• 残差网络更新：标准的Edmonds-Karp增广路更新逻辑，确保流量计算准确。

运行该代码会输出预期结果6。

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