最短路径算法dijkstra的matlab程序。
工具/原料
MATLAB7.0
先阅读http://www.wutianqi.com/?p=1890的博客
方法/步骤
1、你需要先理解dijkstra的算法骒貉缭塄原理。伪代码描述可参考维基baike：functionDijkstra(Graph,source):23createvertexsetQ45惺绅寨瞀foreachvertexvinGraph://Initialization6dist[v]←INFINITY//Unknowndistancefromsourcetov7prev[v]←UNDEFINED//Previousnodeinoptimalpathfromsource8addvtoQ//AllnodesinitiallyinQ(unvisitednodes)910dist[source]←0//Distancefromsourcetosource1112whileQisnotempty:13u←vertexinQwithmindist[u]//Sourcenodewillbeselectedfirst14removeufromQ1516foreachneighborvofu://wherevisstillinQ.17alt←dist[u]+length(u,v)18ifalt<dist[v]://Ashorterpathtovhasbeenfound19dist[v]←alt20prev[v]←u2122returndist[],prev[]
2、程序运行在matlab7.0正常，1为出发节点，有向图的结构如下：
3、这里是我写的matl瞢铍库祢ab程序。%初始化MAXNUM=5;MAXINT=32767;dij=MAXIN皈其拄攥T*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;%将过渡节点加入SU(find(U==m))=[];%将过渡节点从U中删除%比较1经过m与不经过m到未分配节点的距离，dist中的距离更新为较小者foru=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));endendite=ite+1;end%保存到每个节点的最短路径,每行对应每个节点的路径和最短距离，其实就是将S逆序输出path(1,1)=1;fornode=2:MAXNUMlocation=find(S==node);path(node,1)=node;i=2;fors=location:-1:2if(dij(S(s-1),S(s))~=MAXINT)path(node,i)=S(s-1);i=i+1;endendpath(node,i)=dist(node);end%TODO:程序中用到了find()方法，这是一个bug,find可能会返回不止一个值，取其中任意一个就行。