| 学习榜样 | 古今学习模式与中外人才培养 | 基础学习 | 语言学习 | 人间美文 | 学习能力 | 学习工具 | 学习理论 | 科研美图 |
您当前的位置:首页 > 快乐学习 > 语言学习

最短路径法matlab程序

时间:2014-05-23 09:22:59  来源:  作者:

算法描述:

输入图G,源点v0,输出源点到各点的最短距离D

中间变量v0保存当前已经处理到的顶点集合,v1保存剩余的集合

1.初始化v1,D

2.计算v0到v1各点的最短距离,保存到D

for each i in v0;D(j)=min[D(j),G(v0(1),i)+G(i,j)] ,where j in v1

3.将D中最小的那一项加入到v0,并且从v1删除这一项。

4.转到2,直到v0包含所有顶点。

%dijsk最短路径算法

clear,clc

G=[

inf inf 10 inf 30 100;

inf inf 5 inf inf inf;

inf 5 inf 50 inf inf;

inf inf inf inf inf 10;

inf inf inf 20 inf 60;

inf inf inf inf inf inf;

]; %邻接矩阵

N=size(G,1); %顶点数

v0=1; %源点

v1=ones(1,N); %除去原点后的集合

v1(v0)=0;

%计算和源点最近的点

D=G(v0,:);

while 1

D2=D;

for i=1:N

if v1(i)==0

D2(i)=inf;

end

end

D2

[Dmin id]=min(D2);

if isinf(Dmin),error,end

 

v0=[v0 id] %将最近的点加入v0集合,并从v1集合中删除

v1(id)=0;

 

if size(v0,2)==N,break;end

%计算v0(1)到v1各点的最近距离

fprintf('计算v0(1)到v1各点的最近距离\n');v0,v1

id=0;

for j=1:N %计算到j的最近距离

if v1(j)

for i=1:N

if ~v1(i) %i在vo中

D(j)=min(D(j),D(i)+G(i,j));

end

D(j)=min(D(j),G(v0(1),i)+G(i,j));

end

end

end

fprintf('最近距离\n');D

if isinf(Dmin),error,end

end

v0

 

%>> v0

%v0 =

% 1 3 5 4 6

 

%n表示节点数,A表示弧权矩阵

function [I]=MinTree(n,A)

 

k=1; %记录A中不同正数的个数

for(i=1:n-1)for(j=i+1:n) %此循环是查找A中所有不同的正数

if(A(i,j)>0)x(k)=A(i,j); %数组x记录A中不同的正数

kk=1; %临时变量

for(s=1:k-1)if(x(k)==x(s))kk=0;break;end;end %排除相同的正数

k=k+kk;end;end;end

k=k-1 %显示A中所有不同正数的个数

for(i=1:k-1)for(j=i+1:k) %将x中不同的正数从小到大排序

if(x(j)<x(i))xx=x(j);x(j)=x(i);x(i)=xx;end;end;end

T(n,n)=0; %将矩阵T中所有的元素赋值为0

q=0; %记录加入到树T中的边数

for(s=1:k)if(q==n)break;end %获得最小生成树T,算法终止

for(i=1:n-1)for(j=i+1:n)if (A(i,j)==x(s))T(i,j)=x(s);T(j,i)=x(s); %加入边到树T中

TT=T; %临时记录T

while(1)pd=1; %砍掉TT中所有的树枝

for(y=1:n)kk=0;

for(z=1:n)if(TT(y,z)>0)kk=kk+1;zz=z;end;end %寻找TT中的树枝

if(kk==1)TT(y,zz)=0;TT(zz,y)=0;pd=0;end;end %砍掉TT中的树枝

if(pd)break;end;end %已砍掉了TT中所有的树枝

pd=0; %判断TT中是否有圈

for(y=1:n-1)for(z=y+1:n)if(TT(y,z)>0)pd=1;break;end;end;end

if(pd)T(i,j)=0;T(j,i)=0; %假如TT中有圈

else q=q+1;end;end;end;end;end

T %显示近似最小生成树T,程序结束

来顶一下
返回首页
返回首页
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表
推荐资讯
相关文章
栏目更新
栏目热门