最短路径算法dijkstra的matlab实现

最短路径算法dijkstra的matlab实现

最短路径算法dijkstra的matlab程序。

你需要先理解dijkstra的算法原理。伪代码描述可参考维基baike：

function Dijkstra(Graph, source):

2

3 create vertex set Q

4

5 for each vertex v in Graph: // Initialization

6 dist[v] ← INFINITY // Unknown distance from source to v

7 prev[v] ← UNDEFINED // Previous node in optimal path from source

8 add v to Q // All nodes initially in Q (unvisited nodes)

9

10 dist[source] ← 0 // Distance from source to source

11

12 while Q is not empty:

13 u ← vertex in Q with min dist[u] // Source node will be selected first

14 remove u from Q

15

16 for each neighbor v of u: // where v is still in Q.

17 alt ← dist[u] + length(u, v)

18 if alt < dist[v]: // A shorter path to v has been found

19 dist[v] ← alt

20 prev[v] ← u

21

22 return dist[], prev[]

程序运行在matlab 7.0正常，1为出发节点，有向图的结构如下：

这里是我写的matlab程序。

%初始化

MAXNUM=5;

MAXINT=32767;

dij=MAXINT*ones(MAXNUM,MAXNUM);

dij(1,2)=10;

dij(1,4)=30;

dij(1,5)=100;

dij(2,3)=50;

dij(3,5)=10;

dij(4,3)=20;

dij(4,5)=60;

dij(1,1)=0;

dij(2,2)=0;

dij(3,3)=0;

dij(4,4)=0;

dij(5,5)=0;

V=1:MAXNUM;%全部节点

S=;%已分配节点

m=1;%过渡节点

ite=2;

U=2:MAXNUM;%未分配的节点

%重复，直到U为空

%将U中的节点不断添加到S中，同时记录过渡节点和最短路径

dist=dij(1,:);%节点1到其它节点的初始距离值，每次迭代更新一次

dist1=dist;

while(length(U)>0)

dist1(dist1==min(dist1))=[]; %已分配的节点对应的距离从dist1中删除

m=find(dist==min(dist1));%记录dist1当前的最小值在dist中的下标

S(ite)=m;%将过渡节点加入S

U(find(U==m))=[];%将过渡节点从U中删除

%比较1经过m与不经过m到未分配节点的距离，dist中的距离更新为较小者

for u=1:length(U)

if(dist(m)+dij(m,U(u))

dist1(find(dist1==dist(U(u))))=dist(m)+dij(m,U(u));%dist1中的值同步更新

dist(U(u))=dist(m)+dij(m,U(u));

end

end

ite=ite+1;

end

%保存到每个节点的最短路径,每行对应每个节点的路径和最短距离，其实就是将S逆序输出

path(1,1)=1;

for node=2:MAXNUM

location=find(S==node);

path(node,1)=node;

i=2;

for s=location:-1:2

if(dij(S(s-1),S(s))~=MAXINT)

path(node,i)=S(s-1);

i=i+1;

end

end

path(node,i)=dist(node);

end

%TODO:程序中用到了find()方法，这是一个bug,find可能会返回不止一个值，取其中任意一个就行。