Dijkstra

城市间的票价便宜的路线图。 
⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤
⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡
∞
∞
∞∞ ∞ ∞
055252510 550102025 25100102040 2010015 252015050 102540500
 用矩阵 n na × （n为顶点个数）存放各边权的邻接矩阵，行向量 pb、 1 index 、 2 index 、 d 分别用来存放P 标号信息、标号顶点顺序、标号顶点索引、短通路的值。其中分 量 
⎩ ⎨ ⎧
=
顶点未标号当第
顶点已标号当第 i i
ipb
0 1 )( ； )(2 iindex 存放始点到第i点短通路中第i顶点前一顶点的序号；  )( id 存放由始点到第i点短通路的值。 求第一个城市到其它城市的短路径的 Matlab 程序如下： clc,clear a=zeros(6); a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10; a(2,3)=15;a(2,4)=20;a(2,6)=25; a(3,4)=10;a(3,5)=20; a(4,5)=10;a(4,6)=25; a(5,6)=55; a=a+a'; a(find(a==0))=inf; pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a)); d(1:length(a))=inf;d(1)=0;temp=1; while sum(pb)<length(a)    tb=find(pb==0);    d(tb)=min(d(tb),d(temp)+a(temp,tb));    tmpb=find(d(tb)==min(d(tb)));    temp=tb(tmpb(1));    pb(temp)=1;    index1=[index1,temp];    temp2=find(d(index1)==d(temp)-a(temp,index1));    index2(temp)=index1(temp2(1)); end d, index1, index2 
 
    我们编写的从起点sb到终点db通用的Dijkstra标号算法程序如下： function [mydistance,mypath]=mydijkstra(a,sb,db); % 输入：a—邻接矩阵(aij)是指i到j之间的距离，可以是有向的 % sb—起点的标号, db—终点的标号 % 输出：mydistance—短路的距离, mypath—短路的路径 n=size(a,1); visited(1:n) = 0; distance(1:n) = inf;    % 保存起点到各顶点的短距离 
 -77- 
distance(sb) = 0; parent(1:n) = 0; for i = 1: n-1      temp=distance;      id1=find(visited==1); %查找已经标号的点      temp(id1)=inf;  %已标号点的距离换成无穷      [t, u] = min(temp);  %找标号值小的顶点       visited(u) = 1;       %标记已经标号的顶点      id2=find(visited==0); %查找未标号的顶点      for v = id2                     if  a(u, v) + distance(u) < distance(v)              distance(v) = distance(u) + a(u, v);  %修改标号值               parent(v) = u;                                              end                  end end mypath = []; if parent(db) ~= 0   %如果存在路!     t = db; mypath = [db];     while t ~= sb         p = parent(t);         mypath = [p mypath];         t = p;           end end mydistance = distance(db); return