|
http://www./2009/09/compare-dijkstra-shortest-path-algorithm-matlab-code/ 整整一天，我都在網絡上尋找Dijkstra算法的matlab代碼。我找到了許多，然而，它們全部都不能滿足我的需要。
后來我只好參考wiki給出的正確的dijkstra算法，自己寫了個代碼。wiki給出的算法在此：
http://en./wiki/Dijkstra%27s_algorithm
摘錄如下。
1 function Dijkstra(Graph, source):
2 for each vertex v in Graph: // Initializations
3 dist[v] := infinity // Unknown distance function from source to v
4 previous[v] := undefined // Previous node in optimal path from source
5 dist[source] := 0 // Distance from source to source
6 Q := the set of all nodes in Graph
// All nodes in the graph are unoptimized – thus are in Q
7 while Q is not empty: // The main loop
8 u := vertex in Q with smallest dist[]
9 if dist[u] = infinity:
10 break // all remaining vertices are inaccessible
11 remove u from Q
12 for each neighbor v of u: // where v has not yet been removed from Q.
13 alt := dist[u] + dist_between(u, v)
14 if alt < dist[v]: // Relax (u,v,a)
15 dist[v] := alt
16 previous[v] := u
17 return previous[]
作為教訓，我總結一下網絡上能找到的大多數dijkstra算法的matlab代碼的優劣。
1.“Dijkstra最短路算法通用Matlab程序”
這套代碼可以說是國內傳播最廣的dijkstra算法的matla實現，可以在許多網站找到，例如這里：
http://www./bbs/t3095/
它的輸入是賦權鄰接矩陣和起始點，輸出是起始點到各點的距離和最短路樹。代碼在這里。
然而！它是錯的！
用這套代碼可以得出起始點到各點的距離，然而算法得出的最短路樹完全是錯的，甚至用示例數據得到的最短路樹都根本不可理解。算法根本就沒按正確的dijksta算法的思路走。
2.Dijkstra 算法 matlab程序
這套算法也流傳甚廣，鏈接在這里：
http://www./Article/jsjjjs/biafh/200504/735.html
這套算法很簡短，功能也很簡單。它的輸入是賦權鄰接矩陣，輸出是起始點到各點的距離和最短路樹。使用示例數據可以得到正確的結果。缺點是它僅能算出從點1到其他各點的距離。
代碼在這里。
后來我又發現了第二個缺點：這算法也是錯的。從根本上就是錯的，只是恰好能把示例數據算對而已。
3~4.來自mathworks的各種dijkstra代碼
它們應該都是對的，然而太復雜，不適合我的應用；它們各自具有其應用范圍，我沒有依次嘗試，就放在這里而已。
代碼A只能提供從某點到某點的距離，然而不提供從某點到其它任意點的最短路樹。
代碼B能夠提供從某點到其它任意點的最短路樹，但是它是基于地圖的，需要提供每個點的坐標。
5.正確的，可以給出從某點到其它任意點的最短路樹的dijkstra算法代碼
我寫的，應該沒問題了。
輸入是賦權鄰接矩陣和起始點，輸出起始點到其他各點的距離和最短路樹。
代碼在此。
function [d,pre]=dijkstra(D,s)
[m,n]=size(D);
d=inf.*ones(1,m);
d(1,s)=0;
ok=zeros(1,m);
pre=zeros(1,m);
while length(find(d==1))
for k=1:m
if ok(k)==0&&minD>d(k)
minD=d(k);y=k;
end
end
if minD==inf
break;
end
ok(y)=1;
for i=1:m
if D(y,i)~=inf
alt=d(y)+D(y,i);
if alt
d(i)=alt;
pre(i)=y;
end
end
end
end
5,521 閱讀
本日志發表于星期三, 九月 2nd, 2009 at 11:45，屬于分類 學問和 技術。
你可以通過 RSS 2.0對這篇日志進行回復。
你可以 回復日志, 或者從自己的頁面 引用。
|
