Question

怎样用matlab编程实现Dijkstra算法

Answer 1

Dijkstra算法是寻找最短路径的一种搜索算法，由荷兰科学家提出。
算法描述：通过为每个节点保留目前为止所找到的从s到e的最短路径。为了记录最佳路径轨迹，记录路径上每个节点的前趋，通过回溯法找出最短路径轨迹。

在网上搜索一些版本的Matlab实现方法，感觉都有些毛病。经过修改，得到比较好的效果。

[cpp] view plain copy
function [ distance path] = Dijk( W,st,e )
%DIJK Summary of this function goes here
% W 权值矩阵 st 搜索的起点 e 搜索的终点
n=length(W);%节点数
D = W(st,:);
visit= ones(1:n); visit(st)=0;
parent = zeros(1,n);%记录每个节点的上一个节点

path =[];

for i=1:n-1
temp = [];
%从起点出发，找最短距离的下一个点，每次不会重复原来的轨迹，设置visit判断节点是否访问
for j=1:n
if visit(j)
temp =[temp D(j)];
else
temp =[temp inf];
end

end

[value,index] = min(temp);

visit(index) = 0;

%更新 如果经过index节点，从起点到每个节点的路径长度更小，则更新，记录前趋节点，方便后面回溯循迹
for k=1:n
if D(k)>D(index)+W(index,k)
D(k) = D(index)+W(index,k);
parent(k) = index;
end
end

end

distance = D(e);%最短距离
%回溯法 从尾部往前寻找搜索路径
t = e;
while t~=st && t>0
path =[t,path];
p=parent(t);t=p;
end
path =[st,path];%最短路径

end

测试：
测试用例1

[cpp] view plain copy
W=[0 50 inf 40 25 10
50 0 15 20 inf 25
inf 15 0 10 20 inf
40 20 10 0 10 25
25 inf 20 10 0 55
10 25 inf 25 55 0];
[cpp] view plain copy

[cpp] view plain copy
[distance,path]=Dijk(W,1,4);
>> distance

distance =

35

>> path

path =

1 6 4

从节点1到节点4最短距离路径为1-->6-->4, 最短距离为35