怎样用matlab编程实现Dijkstra算法

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

运行matlab程序，新建一个script文件（File-New-script，或者使用工具栏上的按钮New script），在d出的Editor窗口的编辑区域输入你的文件内容（matlab命令）,然后在Editor的菜单栏中找到 Debug菜单下的run（或者直接按F5键），点击它运行你的程序，如果你不是在默认的matlab工作文件夹下工作，会d出提示窗口提示你是否需要将script文件所在目录加入工作目录列表（你所说斗嫌的搜索路径）或设置为Matlab的当前工作目录，根据你的需要选择就可以耐滚了。 Matlab之类的软件需要大胆试用，慢慢就熟悉昌销余了，还要善于使用Help，Help和身边的高手是提高软件使用水平的不二法门。当然还要有持之以恒的决心和毅力。 祝成功！

---