最短路径算法Dijkstra归纳

1、Dijkstra算法解释本文引用三篇文章：分别是 谢光新-Dijkstra算法，ZX770424- Dijkstra 算法，中华儿女英雄-Dijkstra 算法有兴趣的朋友请引用原文，由于分类很不相同难以查找，此处仅作汇总谢光新的文章浅显易懂，无需深入的数学功力，每一步都有图示，很适合初学 者了解。ZX770424 将每一步过程，都用图示方式和公式代码伪代码对应也有助于，代码的理解。中华儿女英雄 从大面上总结了 Dijkstra 的思想，并将演路图描叙出来了。 起到 总结的效果。希望这篇汇总有助于大家对 Dijkstra算法的理解。Dijkstra算法是典型最短路算法，用于计算一个节点到其他所

2、有节点的最短路径。主要特点是以起始点为中心向夕卜层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。简介Dijkstra(迪杰斯特拉)算法是典型的单源 最短路径 算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra 算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论,运筹学等等。Dijkstra 一般的表述通常有两种方式， 一种用永久和临时标号方式，一种是用OPEN,CLOSE表的方式，这里均采用永久和临时标号的方式。注意

3、该算法要求图中不存在负权边。算法描述(这里描述的是从节点1开始到各点的 dijkstra算法，其中Wa->b表示a->b的边的权值，d(i)即为最短路径值)1.置集合S二2,3,n,数组d(1)=0, d(i)=W1->i(1,i之间存在边)or +无穷大(1.i之间不存在边)2 .在S中，令d(j)=mind(i),i 属于S，令S=S-j，若S为空集则算法结束，否则转 33 . 对全部i属于S,如果存在边j->i ,那么置d(i)=mind(i), d(j)+Wj->i，转2Dijkstra 算法思想为：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两

4、组，第一组为已求出最短路径的顶点集合(用S表示，初始时S中只有一个源点，以后每求得一条最短路径就将 加入到集合 S中，直到全部顶点都加入到S中，算法就结束了)，第二组为其余未确定最短路径的顶点集合(用 U表示)，按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点 v到S中各顶点的最短路径长度不大于从源点v至U U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从 v到此顶点只包括 S中的顶点为中间顶点的当前最短路径长度。算法具体步骤（1 ）初始时，S只包含源点，即 S二，v的距离为0。U包含

5、除v外的其他顶点，U中顶点u 距离为边上的权（若 v与U有边）或）（若U不是v的出边邻接点）。（2 ）从U中选取一个距离 v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。（3 ）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u （ u U ）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。（4）重复步骤（2）和（3）直到所有顶点都包含在S中。复杂度分析Dijkstra 算法的时间复杂度为0（n A2）空间复杂度取决于存储方式，邻接矩阵为O（ nT）Dijkstra 算法迪杰斯特拉（Dijks

6、t2）笄法是单源琐点惊短略径求解算江木例以"结点（1匕结点）为计算源.有向图与邻接矩阵:有向网络123451f010g30too2g050g3O>0»104«200605O08-OO80邻接矩阵算法的动态执行情况表格中的项目说明:1.循环:执fir咒法的次数/2、源二通过运算厉，当前己綾加入的结点is K+1：本次运算新加入的结点口4、冃的结点开销：从源结点到冃的结点最优路徉的开銷5、甬耶结点；所冇结血按風最优路彳#逆冋到W结点的上个结点#精环K+1目的第点开帝丽匏结点17.34S123斗5初始化1*0103010001011步 1:运算过程：i| J HP

7、1 1'.'.l' Kt. 1 V3. '' rjVI "J f'l V3,从也到込口的个结点是¥1卿収境哗V3无袪将谢”哉祝告灯【VI。从有向團屮可以看出VI4白 已吿知给VL必銀通过V2>怛是V2 还没有进入中*即当前数振库中 没到达VI的相关信息炳以叫将视为 到询不可达，填m血韬环目的錯点开销前驱结点123斗512345初始化1010max30100010111L2I2010603010001211翊2：得加入节虐晝V2, VI, V4 V5 从冇向图中看肌从VI略直可直桎 至哒的结戊分别是VT V4, VS.VI

8、 V2,开销:1071 j'lj V4+ h ffi： 30VI到V5*开销土 100 将JI销簞小的弟点却入到源中.JM1入罔的i_L知书点士 VI, V2 由于已经将V2加入和亟中所 U此时VI戟可以通过V2別达 V3获知从VI和达V*的稱朴为:VI -> V2 V3 7KH： 60 將开销由rnat坟写为60 此时VI叮以到达V3.尘路触 序塾VI今2今V3从VI逆捋.则g的前驱是 曲所以将以前o«r(r段写 为y循环K+1目叫皓点开销前第结点1234512345初始化1010max3010001a111(U)2010603D1D00111121-2.440105

9、03010001411轉加入节心土 V3. V4, V5加入洁的已知节盘:VI. V2. V4Ml匕经槪级入。刚以本次押除对*2蜩2中.viflva的路绘知伯计畀.当前可迖钮跻有：VI -? V2 -> V3，幵稍为 60。Hi肖：曲此抚由于加入了所以VI到VI -* V4,幵*乩 30V3闊晞轻为VI -> V5 H简：100VI -> V7 -* V3,开捎为 F0.VI -> V2->VS+ 刃制：60/1 V4 -> V3，开巒为 5S將Xtfl圮小的站心加入到源屮3将曲舒史新为开阳更小的路民从VitlJitVS的最优路 卷已经被更新为:VI V4

10、V3V3!勺沁呕为皿搐此 处佯宦梦为亠矿歩驟4；循环源K+1目的结点开悄前奧姑点1234512345初始化1010max301000101113】20106030100012112仏石叫40105030100141131JA330105030&001413讣加入节点：心V5目前图屮的所有苛Ht畀的路楼: 壮m.卄讨：V4r->V1.'- 30VI V5. ”刖卜 100VI V2 V3.升柄 G0VI今”4今V3、开钿50Vl V2-> V3-> V5，开悄；60 勺丄今W >归今V5.丿I悄：60 務幵销最小的酷点加人到源中.加I上斤的已知节点土 VI

11、, V2. V4 比無前kVlf'JVS的毬珞烁 此次加入了 V3.存在更忧蹄锤 VI V4 -> V3 -> V5 刃销：60 史拓丿I销*60.最优路牡改变.更新 为最优踣轻的前鼎士戏5：ts环遁K+l目的第点开销前縣辭点1234£12345初始化010mex3010C0i01111.22D1060北100012112(1X4)401050301000i411312-433010503(60014141JA3.55010503060ni41持加入节点：V5加入V5当前到详的密睛有】VI >VST !| 桶：100VI ->V4->V5，Jl

12、lfl： 90VI ->V4 ->V3 -> V5，/HH： 60优地+1磐为so的最短路的算法-一Dijkstra算法在图仟中，给圮苦和t两个顶4从制到t可以冇多条路彳#从这名条略中找出长度嚴 小的路，这样的路称为从百到t的最短路。设每条孤的长度均为非负值*卜面的算法是由狄克期待拉(Dijtra, 195«提出的，英想法是：设已知图中最接近 于顶点s旳m个顶点以及从顶点出到这些加点中每一个顶点的最您路(从s到其本口的最短 路是零路，即没冇弧的路，HKJ&为0人对顶点£和这川个顶点看色。然民 最接近丁飞 的第血I牛顶点W如卜求之：匕对于毎一个未着色

13、的呗点V,枝虑所冇已着色顶点X,把弧g y)接在从s到x的最 短路后面.这样就得到从s乳y的m条不同路。从这圍条路中选出最短的路，它就是从s 到y的最短路理曲的y点就址最接近T s的豹时1个顶点凋为所冇弧的长度祁绘非负佻 所以从只到最接近于s的第时1个顶点的最扳路必然!H使用已着色的顶点作曲中间顶点。从m-0卄始，将这个过桎重复进行卜去，宜至求得从5 f( t的星短路为止。算法；狄克斯特拉最短路算法第1步开始*所冇弧和顶点都未着匕 对每个顶点x指加 个数 H d&)表示从百到， 的最短路的长度(中间顶点均已着色人开始时，令d(s)-D, d(Q8 对所有好几、表 示已着色的昂后 个顶点

14、，对始点用着色令厂头第2步対于釘个未着色顶点禺 遗新芒义d(Q如卜1d(x)min d(x) d (y)+a(y, x)公式剤丁所冇耒着色顶点血 如肛小二8,则算法缪仁 因为此时从却到任一未若色的顶点祁没 冇踰 否虬 対H冇d(x)M小值的朱看色顶点k进行着色也同吋耙弧(厂卫着色指向顶 点乂的弧只冇条彼肴色九令y二壮第3步 如果顶点t已前色，如焼浓终此 这时已找到一条从占到I的憬勿路如果t未着 色则转笫2步，注意：已看色的狐不能构成 个圈而是构成一个根左s的WttJIS，此树形图称为显愆路树 形郑若X是最短路稠形图中的任一顶点，则从S到X的唯一的一条路绘从S到X的最短路. 这个算法可以看成是根

15、在顶点s的树形图的生懺过禅。一旦到达顶点S生长过程就停|上。 例：给沱冇向團釦卜图所示，用狄克斯特拉养注找出从*剑L的虽短路從讯2步y-sd(a)=mir I d(a)t d (s)+a(s, a) I=min «, 0+4 = 1d(b)-iriin d(b) t d (s)+a(s, b)=min°°± 0+71 _7d(c)=win d(c), d (s) +a(st r) |=mi n («>* 0+3 =3d(d)=min ( d(d), d(s) +h(s, d)=mi n 3, (1+e =8d (t)=min d(t),

16、d(s)+a(s, t)=min *>, 0 卜 8)=«由于d(<:)<5是呆小值，所以对c点着色.并对确d(c)的弧&匚)希色。见图枝)。第3顶点I木看色，返冋第2 5Ka)第2步y=cd(a) win I cf (a). cf (r)+a (c, a) *=uinf4,3+ =4d(h)nnin d(h) t d(c)+n(rt b)=minf7t3«*=7d(d) f d(d), d(r)+nG'p d)-mi ii 3+3 -6d(t) =min( d(t), d(c)+aCe, t)-min («, 3+oa =w&g

17、t;由于dfa=4是最小值,所以对顶点拭着色.井对确id<a)的弧a)着色。见閤b駡弟3步顶点1未看色.返何第2歩.b)第2步ypd(b) =min d(t»), TO 十&仏Ij"-min 17,4+3-7d(d)=min d(d), d(a) +a (o, d)：=min& 4+2)-6d(t)=inin ( d(t), d(a) +a(a, t)=min (w. 4 =«?d(d)=fl是颯小值,对M着色,确宦Kd)的弧青胸条(即(cd)和(a.d),可枉选其中的 余对其着色，我們选(C1d)4见图cA第3步顶点t未着性，返冋第2步；第

18、2步尸dd(b) =uia d(b)r d(d)-*a(d, b)二Enin (7,6+°° -7d(t)=inin d(t)j d(d)+a(dft)二mi n g, 6+2 -8d(b)=7是最小值.对点b着色,对确定d(b)的弧ah)着色。见图dh 第3步 顶点t未*色，返冋第2步.第2涉/=bd(t)=nin d(t), d(b)+o(b, i)=minBf 7+2 =8对点l丛弧t)着色.锻终的最短路树形图由弧c) (s, h)(d) (s, h)和(d. t) 细成*见e)Dijkstra算法的基本思想是:设U的节点就构造SPFPHl占，址根节点为e 任条谨略"丿）的长頂为百. 毎个节点到Jt的般矩路屋长度怙计为定义所育廿点的卑合hA.宦义集合PAt 井设定集ft P的忸始值为P斗母0况算法迭代的过悭中如杲已经变成一今确迢值，则将j标诂为固宦点，并猖英加 入年合I 在訐也的耶一眇迭代中.在尸以外的节点中必定足选择与口的节点氏曲近的 廿点加入到严中.算法的具悴步骤如下：芒< ）P二旧*比=乩°卅="代j丘P t若）和&不是相邻