Question

网格中如何求任意两点间的最短路径 matlab算法

Answer 1

function [L,Z]=dijkstra(W,S,T)
%用 Dijkstra 算法求最短路径
% 算法
% 1. 对每个点I指定一个离点S的距离初始值L(I). 在始点S的值为零, 即L(S)=0，其它点的值为Inf.
% 2. 所有的点标记为未走访的. 置始点S为当前点C.
% 3. 对于当前点C, 考虑它的所有未走访的相邻点J, 并更新J的距离值为
% L(J)=min(L(J), L(C)+W(C,J))
% 4. 把当前点C标记为走访过的点. 走访过的点C的距离L(C)就是点S到C的最短距离, 而且以后不再检查走访过得点了.
% 5. 如果所有的点都是走访过的点, 完成. 不然, 把未走访的点中具有最小距离值的点作为下一个当前点C, 转
N=length(W(:,1));%顶点数
W(find(W==0))=inf;
L=Inf*ones(1,N);
L(S)=0;%L赋初值，在S点为0，其它点为Inf
C=S; %当前点为始点S
Q=1:N;% 未走访的顶点集
Z=S*ones(1,N);
Z(S)=0;% Z赋初值,因始点 S 无父亲点,故把 S 点的Z值改为0
for K=1:N % 更新 L 和 Z 的循环
Q=setdiff(Q,C); %Matlab自带函数，显示Q中除了C之外的点集，即当前点 C 未走访的点集
[L(Q),ind]=min([L(Q);L(C)+W(C,Q)]);%当前点C已走访了所有的相邻的未走访的点，找出与C相邻的距离最短的点，记录最短距离和结点的索引值，更新 L
%如果L(Q)
Z(Q(find(ind==2)))=C; %更新Z, 找出Q中索引值为2的结点，将其父亲结点更新为C,至此可以确定C已是走访过的点了
if T&C==T %若 C 点是终点 T, 不用再计算到其它未走访的点的最短路径.先判断C==T，再判断&
L=L(T); %最短路径长度；
road=T;%最短路径终点；
while T~=S%追溯最短路径上的点
T=Z(T); %从终点往前寻找其父亲结点
road=[road,T]; %从终点开始倒序记录最短路径上的结点
end
Z=road(length(road):-1:1); %颠倒次序；
return;
end;
[null, mC]=min(L(Q));
if null==Inf
% disp('到值是Inf的点的路不通！');
Z(find(L==Inf))=nan; %NaN或者nan都是“非数”的意思，“0/0”、“∞/∞”、“0*∞”都会产生这种结果
return;
else
C=Q(mC);% 把未走访的点集Q中与始点距离最近的点作为新的当前点C;
end
end
end