http://www./2009/09/compare-dijkstra-shortest-path-algorithm-matlab-code/

整整一天，我都在網(wǎng)絡上尋找Dijkstra算法的matlab代碼。我找到了許多，然而，它們?nèi)慷疾荒軡M足我的需要。

后來我只好參考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[]

作為教訓，我總結一下網(wǎng)絡上能找到的大多數(shù)dijkstra算法的matlab代碼的優(yōu)劣。

1.“Dijkstra最短路算法通用Matlab程序”

這套代碼可以說是國內(nèi)傳播最廣的dijkstra算法的matla實現(xiàn)，可以在許多網(wǎng)站找到，例如這里：

http://www./bbs/t3095/

它的輸入是賦權鄰接矩陣和起始點，輸出是起始點到各點的距離和最短路樹。代碼在這里。

然而！它是錯的！

用這套代碼可以得出起始點到各點的距離，然而算法得出的最短路樹完全是錯的，甚至用示例數(shù)據(jù)得到的最短路樹都根本不可理解。算法根本就沒按正確的dijksta算法的思路走。

2.Dijkstra 算法 matlab程序

這套算法也流傳甚廣，鏈接在這里：

http://www./Article/jsjjjs/biafh/200504/735.html

這套算法很簡短，功能也很簡單。它的輸入是賦權鄰接矩陣，輸出是起始點到各點的距離和最短路樹。使用示例數(shù)據(jù)可以得到正確的結果。缺點是它僅能算出從點1到其他各點的距離。

代碼在這里。

后來我又發(fā)現(xiàn)了第二個缺點：這算法也是錯的。從根本上就是錯的，只是恰好能把示例數(shù)據(jù)算對而已。

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 閱讀