• 学问, 技术

    发表于 九月 2nd, 2009

    作者 戈城

    标签

    , ,

    整整一天,我都在网络上寻找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代码的优劣。

    1.“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

      分享到:

    10,710 阅读
    上一篇«


    分享到饭否   

    本日志发表于星期三, 九月 2nd, 2009 at 11:45,属于分类学问技术
    你可以通过RSS 2.0对这篇日志进行回复。
    你可以回复日志, 或者从自己的页面引用
  • 13 评论

    看看有啥想说的。

  • 发表评论

    告诉我你在想什么。

  • 用户名:

    Email (required):

    网址:

    评论: