迪克斯特拉算法

haibin969571154

%最短路问题(迪克斯特拉算法)
* ~$ A  N' X7 w$ p8 u% x- Tclear;
clc;
M=10000;
a(1,:)=[0,50,M,40,25,10];
& U$ E" ?' z5 N4 K4 ua(2,:)=[zeros(1,2),15,20,M,25];
( D: H) V( n/ X5 X+ Wa(3,:)=[zeros(1,3),10,20,M];
* n  T! z& G; A" Na(4,:)=[zeros(1,4),10,25];
1 g; n0 W# @9 ^; |a(5,:)=[zeros(1,5),55];
- Q4 r/ Z) d5 ^a(6,:)=zeros(1,6);
a=a+a';
%length函数返回的是矩阵中行数和列数中较大的长度
) |0 j" i; @+ q3 wpb(1:length(a))=0;%生成一个一行多列的0矩阵
pb(1)=1; %第一个数赋值为1
1 D' |& B. s  L% R8 D+ m$ lindex1=1;
7 x& u5 e& r+ ~9 i' gindex2=ones(1,length(a));%生成一个一行多列的1矩阵
d(1:length(a))=M; d(1)=0; temp=1;
+ p/ D7 n. U6 g0 u7 c2 t%sum函数为各行之和
while sum(pb)<length(a)
  tb=find(pb==0);%find函数返回的是pb矩阵中数值为0的坐标(2,3,4,5,6....)
  d(tb)=min(d(tb),d(temp)+a(temp,tb));
! L2 |, c& d# C( _3 j0 D  tmpb=find(d(tb)==min(d(tb)));
+ p9 S2 C  `& S; I  temp=tb(tmpb(1));
) C8 B* m/ Z1 V: V! T3 m1 Z  pb(temp)=1;
  index1=[index1,temp];
$ H. k+ a8 A$ ]- |  index=index1(find(d(index1)==d(temp)-a(temp,index1)));
  if length(index)>=2
    index=index(1);
% ?1 W% g0 n' H: F5 |  end
9 ~5 z$ p1 y1 k/ E  index2(temp)=index;
end
d,index1,index2
. A7 Z. ]  E9 o迪杰斯特拉算法用于求解一个有向图（也可以是无向图，无向图是有向图的一种特例）的一个点（称之为原点）到其余各点（称之为周边点）的最短路径问题。算法构思很是巧妙（我这么认为），简直达到了“无心插柳柳成荫”的境界。算法本身并不是按照我们的思维习惯——求解从原点到第一个点的最短路径，再到第二个点的最短路径，直至最后求解完成到第n个点的最短路径，而是求解从原点出发的各有向路径的从小到大的排列（如果这个有向图中有环1-2-3-1算法岂不是永无终结之日了？？！！），但是算法最终确实得到了从原点到图中其余各点的最短路径，可以说这是个副产品，对于算法的终结条件也应该以求得了原点到图中其余各点的最短路径为宜。清楚了算法的这种巧妙构思后，理解算法本身就不是难题了。
       算法把一个图（G）中的点划分成了若干部分：
       1）：原点（v）；
       2）：所有周边点（C）；
       另外有一个辅助集合S，从v到S中的点的最短路径已经求得。S的最初状态是空集。
" {0 F# v, p; C% m1 X- g; z; o$ }       这样就可以进一步划分图（G）：
       1）：原点（v）；
       2）：已求出v至其最短路径的周边点（S）；
       3）：尚未求出v至其最短路径的周边点（Other=C-S）；
       算法的主体思想：
           A、找到v——Other所有路径中的的最短路径vd=v——d（Other的一个元素）；
, P9 B7 T% |  K7 L& M- |/ ~B、找到v——S——Other所有路径中的的最短路径vi=v——i（Other的一个元素）；
C、比较vd和vi如果vd<=vi则将d加入S且从Other中删除，否则将i加入S且从Other中删除。
4 Q- q2 }# m9 l. S' @& G重复以上步骤直至Other为空集。

我们求得的最短路径是升序排列的，那为什么下一条最短路径就存在于v——

: o7 j) E+ }* |  Q& ?( q

yi_lip

确实用matlab 写简洁，但是比其他的理解起来难一点。

623976603

精辟!!!!!!!!!

sqirrel

受用~~~~~~~~~~~··

HNzhangjie

d,index1,index2
; Y2 t4 V+ c. \* v! ?8 j7 c# s问，求出来的分别是什么

Paul_Sing

看看~~

WenqiSun

代码写的很简洁，顶顶~~

gaobuzheng

tanai

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