http://www.rexcel.us/2009/09/compare-dijkstra-shortest-path-algorithm-matlab-code/
整整一天,我都在网络上寻找Dijkstra算法的matlab代码。我找到了许多,然而,它们全部都不能满足我的需要。
后来我只好参考wiki给出的正确的dijkstra算法,自己写了个代码。wiki给出的算法在此:
http://en.wikipedia.org/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代码的优劣。
这套代码可以说是国内传播最广的dijkstra算法的matla实现,可以在许多网站找到,例如这里:
http://www.labfans.com/bbs/t3095/
它的输入是赋权邻接矩阵和起始点,输出是起始点到各点的距离和最短路树。代码在这里。
然而!它是错的!
用这套代码可以得出起始点到各点的距离,然而算法得出的最短路树完全是错的,甚至用示例数据得到的最短路树都根本不可理解。算法根本就没按正确的dijksta算法的思路走。
2.Dijkstra 算法 matlab程序
这套算法也流传甚广,链接在这里:
http://www.9414.net/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
联系客服