图论学习的整理笔记
图论学习整理
图论程序整理出来
程序中图可以用邻接矩阵
Dijkstra 算法
Floyd 算法
Kruskal 算法
Prim 算法
算法类型：最短路，网络流，二分图算法。
解释：
最短路问题：（Dijkstra ，Floyd 算法）
最小生成树问题：连接多个节点费用最低（Prim ，Kruskal 算法） 图的匹配问题：（匈牙利算法）
遍历性问题
最大流问题
运输问题：完成运输问题，并寻求运输费用最小方案
Matlab 程序：
n=8;A=[0 2 8 1 Inf Inf Inf Inf
2 0 6 Inf 1 Inf Inf Inf
8 6 0 7 5 1 2 Inf
1 Inf 7 0 Inf Inf 9 Inf
Inf 1 5 Inf 0 3 Inf 8
Inf Inf 1 Inf 3 0 4 6
Inf Inf 2 9 Inf 4 0 3
Inf Inf Inf Inf 8 6 3 0]; % MATLAB 中, Inf 表示∞
D=A; %赋初值
for (i=1:n)for (j=1:n)R(i,j)=j;end ; end %赋路径初值
for (k=1:n)for (i=1:n)for (j=1:n)if (D(i,k)+D(k,j)
R(i,j)=k;end ; end ; end %更新rij
k %显示迭代步数
D %显示每步迭代后的路长
R %显示每步迭代后的路径
pd=0;for i=1:n %含有负权时
if (D(i,i)
if (pd)break ; end %存在一条负回路, 终止程序
end %程序结束
求最小费用最大流matlab 代码
n=5;C=[0 15 16 0 0
0 0 0 13 14
0 11 0 17 0
0 0 0 0 8
0 0 0 0 0]; %弧容量
b=[0 4 1 0 0
0 0 0 6 1
0 2 0 3 0
0 0 0 0 2
0 0 0 0 0]; %弧上单位流量的费用
wf=0;wf0=Inf; %wf 表示最大流量, wf0 表示预定的流量值
for (i=1:n)for (j=1:n)f(i,j)=0;end ; end %取初始可行流f 为零流
while (1)
for (i=1:n)for (j=1:n)if (j~=i)a(i,j)=Inf;end ; end ; end %构造有向赋权图
for (i=1:n)for (j=1:n)if (C(i,j)>0&f(i,j)==0)a(i,j)=b(i,j);
elseif (C(i,j)>0&f(i,j)==C(i,j))a(j,i)=-b(i,j);
elseif (C(i,j)>0)a(i,j)=b(i,j);a(j,i)=-b(i,j);end ; end ; end
for (i=2:n)p(i)=Inf;s(i)=i;end %用Ford 算法求最短路, 赋初值
for (k=1:n)pd=1; %求有向赋权图中vs 到vt 的最短路
for (i=2:n)for (j=1:n)if (p(i)>p(j)+a(j,i))p(i)=p(j)+a(j,i);s(i)=j;pd=0;end ; end ; end
if (pd)break ; end ; end %求最短路的Ford 算法结束
if (p(n)==Inf)break ; end %不存在vs 到vt 的最短路, 算法终止. 注意在求最小费用最大流时构造有 dvt=Inf;t=n; %进入调整过程, dvt 表示调整量
while (1) %计算调整量
if (a(s(t),t)>0)dvtt=C(s(t),t)-f(s(t),t); %前向弧调整量
elseif (a(s(t),t)
if (dvt>dvtt)dvt=dvtt;end
if (s(t)==1)break ; end %当t 的标号为vs 时, 终止计算调整量
t=s(t);end %继续调整前一段弧上的流f
pd=0;if (wf+dvt>=wf0)dvt=wf0-wf;pd=1;end %如果最大流量大于或等于预定的流量值
t=n;while (1) %调整过程
if (a(s(t),t)>0)f(s(t),t)=f(s(t),t)+dvt; %前向弧调整
elseif (a(s(t),t)
if (s(t)==1)break ; end %当t 的标号为vs 时, 终止调整过程
t=s(t);end
if (pd)break ; end %如果最大流量达到预定的流量值
wf=0; for (j=1:n)wf=wf+f(1,j);end ; end %计算最大流量
zwf=0;for (i=1:n)for (j=1:n)zwf=zwf+b(i,j)*f(i,j);end ; end %计算最小费用