Dijsk最短路径算法(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