【老生谈算法】最短路径算法-matlab程序.doc
版权申诉
5星 · 超过95%的资源 196 浏览量
2022-07-02
18:09:22
上传
评论
收藏 31KB DOC 举报 
算法描述：
输入图 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 各点的最近距离');v0,v1
id=0;
for j=1:N %计算到 j 的最近距离
if v1(j)
资源评论
KSP呵呵哈2022-08-18超赞的资源，感谢资源主分享，大家一起进步！
uvexwz2022-10-23资源有很好的参考价值，总算找到了自己需要的资源啦。
聪聪想吃汤圆2022-11-12内容与描述一致，超赞的资源，值得借鉴的内容很多，支持！
