算法描述：通過為每個節點保留目前為止所找到的從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