1. function Dijkstra(Graph, source):

    2

    3      create vertex set Q

    4

    5      for each vertex v in Graph:             // Initialization

    6          dist[v] ← INFINITY                  // Unknown distance from source to v

    7          prev[v] ← UNDEFINED                 // Previous node in optimal path from source

    8          add v to Q                          // All nodes initially in Q (unvisited nodes)

    9

    10      dist[source] ← 0                        // Distance from source to source

    11

    12      while Q is not empty:

    13          u ← vertex in Q with min dist[u]    // Source node will be selected first

    14          remove u from Q

    15

    16          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 found

    19                  dist[v] ← alt

    20                  prev[v] ← u

    21

    22      return dist[], prev[]

  2.  

    程序运行在matlab 7.0正常,1为出发节点,有向图的结构如下:

    最短路径算法dijkstra的matlab实现-LMLPHP
  3.  

    这里是我写的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;%将过渡节点加入S

    U(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));

    end

    end

    ite=ite+1;

    end

    %保存到每个节点的最短路径,每行对应每个节点的路径和最短距离,其实就是将S逆序输出

    path(1,1)=1;

    for node=2:MAXNUM

    location=find(S==node);

    path(node,1)=node;

    i=2;

    for s=location:-1:2

    if(dij(S(s-1),S(s))~=MAXINT)

    path(node,i)=S(s-1);

    i=i+1;

    end

    end

    path(node,i)=dist(node);

    end

    %TODO:程序中用到了find()方法,这是一个bug,find可能会返回不止一个值,取其中任意一个就行。

    参考----http://www.wutianqi.com/?p=1890

    或者

    https://blog.csdn.net/cxllyg/article/details/7604812

05-07 15:18