迪克斯特拉算法

haibin969571154

%最短路问题(迪克斯特拉算法)
clear;
clc;
/ a5 k0 l0 p- n1 j9 cM=10000;
4 h2 e6 p) I) }8 L; A, m3 A" va(1,:)=[0,50,M,40,25,10];
! C" @9 ^: O, ya(2,:)=[zeros(1,2),15,20,M,25];
& w% l! ]1 t! w$ U$ `a(3,:)=[zeros(1,3),10,20,M];
a(4,:)=[zeros(1,4),10,25];
/ f6 N; X, b" |& `& Pa(5,:)=[zeros(1,5),55];
# O; `) a( O% e. Aa(6,:)=zeros(1,6);
a=a+a';
%length函数返回的是矩阵中行数和列数中较大的长度
, A* \; D) n. B' V3 }1 vpb(1:length(a))=0;%生成一个一行多列的0矩阵
pb(1)=1; %第一个数赋值为1
index1=1;
! F; \, i% G" ?& L; _- m& Qindex2=ones(1,length(a));%生成一个一行多列的1矩阵
d(1:length(a))=M; d(1)=0; temp=1;
%sum函数为各行之和
while sum(pb)<length(a)
# {, X6 J3 y- W7 f- v  tb=find(pb==0);%find函数返回的是pb矩阵中数值为0的坐标(2,3,4,5,6....)
0 T1 J2 w5 a1 z% I. I4 d8 I  `/ y. H  d(tb)=min(d(tb),d(temp)+a(temp,tb));
  tmpb=find(d(tb)==min(d(tb)));
( j9 K/ ~+ a; M, E/ B+ b  temp=tb(tmpb(1));
/ F1 c  S  a8 @  pb(temp)=1;
  index1=[index1,temp];
$ r) h4 `( L( }5 Y; Q% v  index=index1(find(d(index1)==d(temp)-a(temp,index1)));
  if length(index)>=2
    index=index(1);
2 N6 j: S9 e: J0 ^* Q  end
  index2(temp)=index;
2 I! l0 {3 W2 X6 g- e- [$ ]end
d,index1,index2
迪杰斯特拉算法用于求解一个有向图（也可以是无向图，无向图是有向图的一种特例）的一个点（称之为原点）到其余各点（称之为周边点）的最短路径问题。算法构思很是巧妙（我这么认为），简直达到了“无心插柳柳成荫”的境界。算法本身并不是按照我们的思维习惯——求解从原点到第一个点的最短路径，再到第二个点的最短路径，直至最后求解完成到第n个点的最短路径，而是求解从原点出发的各有向路径的从小到大的排列（如果这个有向图中有环1-2-3-1算法岂不是永无终结之日了？？！！），但是算法最终确实得到了从原点到图中其余各点的最短路径，可以说这是个副产品，对于算法的终结条件也应该以求得了原点到图中其余各点的最短路径为宜。清楚了算法的这种巧妙构思后，理解算法本身就不是难题了。
       算法把一个图（G）中的点划分成了若干部分：
       1）：原点（v）；
       2）：所有周边点（C）；
% c2 ?% [4 x2 d8 \, c       另外有一个辅助集合S，从v到S中的点的最短路径已经求得。S的最初状态是空集。
) Q: L) k0 P" ^  x5 S4 u: k       这样就可以进一步划分图（G）：
- w, D0 o  e! u/ B! ~# y" N3 A       1）：原点（v）；
       2）：已求出v至其最短路径的周边点（S）；
       3）：尚未求出v至其最短路径的周边点（Other=C-S）；
# ]2 A6 d+ H  c2 u+ O  C* ~9 n( T7 _       算法的主体思想：
           A、找到v——Other所有路径中的的最短路径vd=v——d（Other的一个元素）；
) k  s" c; @! b9 Q0 AB、找到v——S——Other所有路径中的的最短路径vi=v——i（Other的一个元素）；
+ c2 p/ @9 k3 K; G' G( jC、比较vd和vi如果vd<=vi则将d加入S且从Other中删除，否则将i加入S且从Other中删除。
重复以上步骤直至Other为空集。

我们求得的最短路径是升序排列的，那为什么下一条最短路径就存在于v——
- \0 x% G+ ^; W5 j" M
0 X; f% y4 Z# j  f3 E

紫辰

程序没有错啊。你再看看吧
/ w! R, \9 s. S0 q# U/ Q

linmatsas

回复 紫辰 的帖子


    我是说好像……人家在贴源程序吧…………

wajm_011

看看

salad6

试试运气啦~~~~~~~~~~~

queniao

不错不错,我喜欢看  

snrl

楼主，你写得实在是太好了。我惟一能做的，就只有把这个帖子顶上去这件事了

chshfxfx

顶顶更健康，越顶吃的越香。

icm

顶顶更健康，越顶吃的越香。

libin1984

哦～～