发布时间 : 星期三 文章MATLAB程序大全 - 图文更新完毕开始阅读ee93ef4b03d276a20029bd64783e0912a3167c3b
☆★☆★☆
end
Mi=min(path(:,3)); %寻找增广路径中最小的那条边 for i=1:k
A(path(i,1),path(i,2))=A(path(i,1),path(i,2))-Mi; %增广路径中每条路径减去最小的边
maxflow(path(i,1),path(i,2))=maxflow(path(i,1),path(i,2))+Mi; %最大流，原网络包含这个网络，我只能这样表示了
end %使用新的图A进入下一循环，从新开始找增广路径 end
figure;
netplot(maxflow,1)
9.单元最短路径
图的相关算法也算是自己的一个软肋了，当年没选修图论也是一大遗憾。
图像处理中，也有使用图论算法作为基础的相关算法，比如图割，这个算法就需要求最大流、最小割。所以熟悉一下图论算法对于图像处理还是很有帮助的。
Dijkstra和Bellman-Ford类似，都是解决单源最短路径问题，不同的是这个方法只能解决边为非负的问题，实现的好的Dijkstra算法运行时间要快于Bellman-ford。 算法步骤如下：
1.首先设置队列，所有节点入列，源节点值为0，其他节点值为无穷。 2.然后在队列中找值最小的节点并出列。 3.计算出列的节点所有后继节点的距离。
4.松弛方法，如果新计算的距离小于上次计算的距离，那么更新距离，即将后继节点值设为较小的距离，并将后继节点的前趋设为当前的出列节点。
5.对剩余的节点队列继续找最小值并出列，不断循环2、3、4步直到队列中没有节点了。 步骤是上面没错，不过我程序中没有完全按照上述的步骤实现。不同的地方在于我没有做出列操作，而是通过标记节点的形式实现的。
运行结果如下，图（是图不是图片）是算法导论367页上的：
☆★☆★☆
matlab代码如下，netplot和compresstable2matrix和上一篇使用的一样： main.m
clear all;close all;clc
%初始化邻接压缩表，1 2 10 表示从节点1到节点2，边的权重为10 b=[1 2 10;1 4 5;2 3 1; 2 4 2; 3 5 4;4 2 3; 4 3 9; 4 5 2;5 1 7; 5 3 6];
m=max(max(b(:,1:2))); %压缩表中最大值就是邻接矩阵的宽与高 A=compresstable2matrix(b); %从邻接压缩表构造图的矩阵表示 netplot(A,1) %形象表示
S=inf(1,m); %从开始的源点到每一个节点的距离 S(1)=0; %源点到自己的距离为0
pa=zeros(1,m); %存储每个节点的前驱，在松弛过程中赋值
☆★☆★☆
pa(1)=1; %源点的前趋是自己
visit=zeros(1,m); %标记某个节点是否访问过了
index=1; %从index节点开始搜索
%判断是否对所有节点都找的最短路径了。可能会有源点没有路径到目标节点的情况，那就无限循环了
while sum(visit)~=m %没有出队列操作，不过通过visit来等价的表示了
visit(index)=1; %标记第index节点为已入列的节点 [S pa]=relax(S,pa,A,visit,index,m); %松弛，如果两个节点间有更短的距离，则用更短的距离
index=extract_min(S,visit,index,m); %使用已访问的最小的节点作为下一次搜索的开始节点 end
%最终我们需要的就是这两个值
S %源点到其他每一点的距离 pa %其他每一节点的前趋
%算法到此结束，下面只是为了形象的表示而写的。 re=[]; for i=2:m
re=[re;pa(i) i A(pa(i),i)]; end
A=compresstable2matrix(re); %从邻接压缩表构造图的矩阵表示 figure;
netplot(A,1) %形象表示
relax.m
%边缘松弛，使用更短的距离作为节点的值 function [S pa]=relax(S,pa,A,visit,index,m)
i=index; for j=1:m
if A(i,j)~=inf && visit(j)~=1 %搜索没有标记过的节点
if S(j)>S(i)+A(i,j) %将较小的值赋给正在搜寻的节点 S(j)=S(i)+A(i,j); pa(j)=i; end
end end
☆★☆★☆
end
extract_min.m
%提取队列中尚未标记的最小的值的序号 function index=extract_min(S,visit,index,m)
Mi=inf; for j=1:m
if visit(j)~=1 if S(j) 10.单元最短路径 该算法可以用来解决一般（边的权值为负）的单源最短路径问题，而dijkstra只能解决权值非负的情况。 此算法使用松弛技术，对每一个顶点，逐步减少源到该顶点的路径的估计值，直到达到最短的路径。 算法运算结果：