最短路径算法dijkstra的matlab实现

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=[1];%已分配节点

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))<dist(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可能会返回不止一个值，取其中任意一个就行。      

参考----http://www.wutianqi.com/?p=1890

或者

https://blog.csdn.net/cxllyg/article/details/7604812