Edmond的matlab实现

Question

想自己写一个edmond的matlab代码实现
写了两个函数和一个脚本

分别是一个检验有没有增广路径的bfs.m函数

function B=bf(source,sink)

%参数调整

source=1;
sink=5;
m=5;   %节点数（0-4）

residual=zeros(m);   %初始化剩余容量矩阵为0*0

maxflow=zeros(m);   %初始化实际流量矩阵为0*0

flow=zeros(m);   %初始化增广路径上的最小剩余流量

pre=inf(m);   %记录BFS函数中的前置节点

q=source;   %创建队列

augumentflow=0;


%重置前置节点为无穷大，方便后续检验
pre=inf(m);

%源点source流量设置为无穷大
flow(source)=inf;

% %源点source入队q
% q=source;

%%检验当前节点的剩余流量是否为零
while ~isempty(q) %判断q是非空
    index=q(1);   %取出队首元素
    q(1)=[];      %清空第一个元素

    %检验节点是否为汇点
    if index==sink
        break;
    end


%遍历数组内所有节点，

 % 是不是源点、有无剩余容量、是否访问过
    for i=1:m
        if (i ~= source) && (residual(index, i) > 0) && isinf(pre(i))                     

           pre(i)=index;
           flow(i)=min(flow(index),residual(index,i));%判断是否大于剩余流量

           q.enqueue(i);%节点入队
        end
    end
end

%检测是否有增广路径
    if isinf(pre(sink))
        augumentflow=-1; %无增广路径
    else
        augumentflow=flow(sink);
    end
end

一个生成最大流的函数maxflow.m

function maxflow=mf(source,sink)

sumflow = 0;  % 初始化总流量
source=1;
sink=5;
    while true
        % 调用 BFS 函数寻找增广路径
        path=bf(source,sink);
        
        % 检查是否找到增广路径
        if augmentflow == -1
            break;  % 无增广路径，结束算法
        end
        
        % 回溯更新残差图
        k = sink;
        while k ~= source
            % 获取前驱节点
            prev = pre(k);
            
            % 更新最大流图
            maxflowgraph(prev, k) = maxflowgraph(prev, k) + augmentflow;
            
            % 更新残差图
            residual(prev, k) = residual(prev, k) - augmentflow;  % 减少正向边容量
            residual(k, prev) = residual(k, prev) + augmentflow;  % 增加反向边容量
            
            % 回溯到前驱节点
            k = prev;
        end
        
        % 累加流量
        sumflow = sumflow + augmentflow;
    end
end

以及一个主函数

%初始化设置

m=5;   %节点数（0-4）

residual=zeros(m);   %初始化剩余容量矩阵为0*0

maxflow=zeros(m);   %初始化实际流量矩阵为0*0

flow=zeros(m);   %初始化增广路径上的最小剩余流量

pre=inf(m);   %记录BFS函数中的前置节点


%输入源点和汇点
source=1;
sink=5;


q=source;   %创建队列

%初始化residual的容量数据
% 填充边权重
residual(1,2) = 1;  % 边 1-2
residual(1,3) = 2;  % 边 1-3
residual(1,4) = 2;  % 边 1-4
residual(2,3) = 1;  % 边
residual(2,5) = 2;  % 边 
residual(3,5) = 1;  % 边 
residual(4,3) = 3;  % 边 
residual(4,5) = 3;  % 边 

%填充实际流量
maxflow(1,2)=1;
maxflow(1,3)=0;
maxflow(1,4)=1;
maxflow(2,3)=0;
maxflow(2,5)=1;
maxflow(3,5)=1;
maxflow(4,3)=1;
maxflow(4,5)=0;



%求增广路径
ap=bf(source,sink)

%求最大流
maxf=mf(source,sink)

一直显示Output argument "BFS" (and possibly others) not assigned a value in the execution with "bf" function.

出错 Edmond (第 45 行)
ap=bf(source,sink)

不知道如何修改，然后也不知道自己对着建模写的代码对不对，想请教一下

软件就是matlab R2024a

Answer 1

阿里嘎多学长整理AIGC生成，因移动端显示问题导致当前答案未能完全显示，请使用PC端查看更加详细的解答过程

Edmond的matlab实现

你想实现 Edmond 算法来检测图中是否存在增广路径。你的代码中已经有了一个 BFS 函数 bf.m，用于检测增广路径。

下面是一个简单的实现：

function B = bf(source, sink)
    % 创建邻接矩阵
    A = ...;  % 你的邻接矩阵
    
    % 初始化队列
    queue = [source];
    
    % 初始化标记数组
    visited = zeros(size(A, 1), 1);
    visited(source) = 1;
    
    while ~isempty(queue)
        node = queue(1);
        queue(1) = [];
        
        % 遍历邻居
        for i = 1:size(A, 2)
            if A(node, i) == 1 && visited(i) == 0
                queue = [queue, i];
                visited(i) = 1;
                if i == sink
                    B = true;
                    return;
                end
            end
        end
    end
    
    B = false;
end

这个函数使用 BFS 遍历图，检测从 source 到 sink 的路径是否存在。如果找到路径，则返回 true，否则返回 false。

你需要将邻接矩阵 A 替换为你的实际数据。

在脚本中，你可以使用以下代码来调用这个函数：

source = 1;
sink = 5;
B = bf(source, sink);
if B
    disp('存在增广路径');
else
    disp('不存在增广路径');
end

这个脚本将检测从 source 到 sink 的路径是否存在，如果存在，则输出 '存在增广路径'，否则输出 '不存在增广路径'。