最短路径算法 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 3...
算法描述:
输入图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
本文档为【最短路径算法 matlab程序】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483