最短路径六个点MATLAB程序,最短路径法matlab程序

最短路径六个点MATLAB程序,最短路径法matlab程序

最短路径法matlab程序

算法描述：

输入图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)

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,程序结束