用Dijkstra算法求最短路径的MATLAB程序

你对图论的知识有了解吧~W是关联矩阵，s和t分别是起始点和终止节点的序号。返回的d为最短的加权路径长度,p为最优路径节点的序号向量。注意，这里W矩阵为0的点权值已经自动设为无穷大了。请参考《高等应用数学问题的 MATLAB一书》。我吧程序赋给你。

你做一个M函数用吧。

function [d,path]=dijkstra(W,s,t)

[n,m]=size(W)ix=(W==0)W(ix)=inf

if n~=m,error('Square W required')end

visited(1:n)=0dist(1:n)=infparent(1:n)=0dist(s)=0d=inf

for i=1:(n-1),%求出每个节点与起始点的关系

ix=(visited==0)vec(1:n)=infvec(ix)=dist(ix)

[a,u]=min(vec)visited(u)=1

for v=1:n,if (W(u,v)+dist(u)<dist(v)),

dist(v)=dist(u)+W(u,v)parent(v)=u

endendend

if parent(t)~=0,path=td=dist(t)%回溯最短路径

while t~=s,p=parent(t)path=[p path]t=pend

end

希望对你有用

是否可以解决您的问题？

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

开始，运行（或者直接按Win+R），输入notepad

将下面两行百分号之间的内容复制进去，再保存成dijkstra.m，注意保存路径（最好保存到Matlab的工作路径中）

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function [d,DD]=dijkstra(D,s)

%Dijkstra最短路算法Matlab程序用于求从起始点s到其它各点的最短路

%D为赋权邻接矩阵

%d为s到其它各点最短路径的长度

%DD记载了最短路径生成树

[m,n]=size(D)

d=inf.*ones(1,m)

d(1,s)=0

dd=zeros(1,m)

dd(1,s)=1

y=s

DD=zeros(m,m)

DD(y,y)=1

counter=1

while length(find(dd==1))<m

for i=1:m

if dd(i)==0

d(i)=min(d(i),d(y)+D(y,i))

end

end

ddd=inf

for i=1:m

if dd(i)==0&&d(i)<ddd

ddd=d(i)

end

end

yy=find(d==ddd)

counter=counter+1

DD(y,yy(1,1))=counter

DD(yy(1,1),y)=counter

y=yy(1,1)

dd(1,y)=1

end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

然后在matlab命令窗口中，生成D和s

然后调用：[d,DD]=dijkstra(D,s)

---