姓名：商晴庆班级：学号：班内序号：
实验三 Dijkstra算法的matlab实现
一、程序及注释
function y=dijkstra(x)
disp('************【D算法】以第五章课后习题5.10为例******************'); stop=1;
while(stop)
disp('给定的测试初始距离矩阵为：');
w1=[0.0 9.2 1.1 3.5 100 100
1.3 0.0 4.7 100 7.2 100
2.5 100 0.0 100 1.8 100
100 100 5.3 2.4 0.0 7.5
100 6.4 2.2 8.9 0.0 5.1
7.7 100 2.7 100 2.1 0.0]
w=input('您可以直接输入“w1”选择给定的测试矩阵，或者任意输入一个邻接权值矩阵进行测试w=: ');
[n,n]=size(w);
tic;
%初始化回溯路由
for i=1:n
for j=1:n
if w(i,j)~=100&&w(i,j)~=0
parent(i,j)=i; %初始化回溯路由矩阵
else
parent(i,j)=0;
end
end
end
D=w;%初始距离矩阵
for st=1:n
visit=ones(1,n);visit(st)=0;%把节点分为两个集合，已选节点标注为0,未选节点标注为1
%path=[];
%从起点出发，找最短距离的下一个点，每次不会重复原来的轨迹，设置visit判断节点是否已经加入
for i=1:n-1
temp=[];
for j=1:n
if visit(j)
temp=[temp D(st,j)];
else
temp=[temp 100];
end
end
[value,index]=min(temp);%value是temp中最小值，index是最小值的序号 visit(index)=0;%把最小值加入到已选节点集合
%更新。

如果经过index节点，从起点到每个节点的路径长度更小，则更新，记录前趋节点，方便后面回溯循迹
for k=1:n
if D(st,k)>D(st,index)+w(index,k)
D(st,k)=D(st,index)+w(index,k);
parent(st,k)=index;
end
end
end
end
t=toc;
disp('所得距离矩阵为：');
disp(D);
disp('所得回溯路由矩阵为：');
disp(parent);
disp(['算法运行时间为：',num2str(t)]);
disp('************************************************************** **');
disp('*************计算任意端点间最短距离和路由
*************************');
wc=D;
i=input('请输入起点： ');
while (i<1 || i>n)
disp('!起点不存在，请输入正确起点');
i=input('请输入起点： ');
end
j=input('请输入终点： ');
while (j<1 || j>n )
disp('！终点不存在，请输入正确终点');
j=input('请输入终点： ');
end
if wc(i,j)==100
disp('！这两点间不可到达');
else
path=[];
distance=D(i,j);
%回溯法寻找路径
t=j;
while(t~=i&&t>0)
path=[t,path];
p=parent(i,t);
t=p;
end
path=[i path];
end
disp(['这两点之间的最短距离为：',num2str(distance)]); %显示最短距离 disp(['所经过的路由为：',num2str(path)]); %显示经过路由
plot(path,'-bp');
title('路由示意图');
set(gca,'xtick',[1:1:n]); %设置x轴
set(gca,'ytick',[1:1:n]); %设置y轴
xlabel('第x跳路由');
ylabel('端点Vy');
axis([1,n,1,n]);
s=input('是否继续？Y/N ','s');
if s=='N'||s=='n'
stop=0;
else
stop=1;
end
End
二、运行结果
以课后习题5.10为例进行演示：
可以看到v2到v4的最短距离为4.8 路由为v2—v1—v4，仿真结果正确。