MATLAB 7.0
先阅读http://www.wutianqi.com/?p=1890的博客
你需要先理解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) 910 dist[source] ← 0 // Distance from source to source11 12 while Q is not empty:13 u ← vertex in Q with min dist[u] // Source node will be selected first14 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 found19 dist[v] ← alt 20 prev[v] ← u 2122 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;%将过渡节点加入SU(find(U==m))=[];%将过渡节点从U中删除%比较1经过m与不经过m到未分配节点的距离，dist中的距离更新为较小者for u=1:length(U) if(dist(m)+dij(m,U(u))
算法时间复杂度未必最小
程序不保证不含任何bug，此乃作者本人的代码共享，使用请添加引用。