最短路徑演算法dijkstra的matlab實現
最短路徑演算法dijkstra的matlab程式。
操作方法
（01）你需要先理解dijkstra的演算法原理。虛擬碼描述可參考維基baike：function Dijkstra(Graph, source):23 create vertex set Q45 for each vertex v in Graph: // Initialization6 dist[v] ← INFINITY // Unknown distance from source to v7 prev[v] ← UNDEFINED // Previous node in optimal path from source8 add v to Q // All nodes initially in Q (unvisited nodes)910 dist[source] ← 0 // Distance from source to source1112 while Q is not empty:13 u ← vertex in Q with min dist[u] // Source node will be selected first14 remove u from Q1516 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] ← alt20 prev[v] ← u2122 return dist[], prev[]
（02）程式執行在matlab 7.0正常，1為出發節點，有向圖的結構如下：
（03）這裡是我寫的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))<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;for node=2:MAXNUMlocation=find(S==node);path(node,1)=node;i=2;for s=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可能會返回不止一個值，取其中任意一個就行。
特別提示
演算法時間複雜度未必最小
程式不保證不含任何bug，此乃作者本人的程式碼共享，使用請新增引用。
