最短路径算法—dijkstra总结

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

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

3、方式。注意该算法要求图中不存在负权边。算法描述(这里描述的是从节点1开始到各点的 dijkstra算法，其中 Wa->b表示a->b的边的权值，d即为最短路径值)1. 置集合S=2,3，n,数组d(1)=0, d(i尸W1->i(1,i之间存在边)or +无穷大之间不存在边)2. 在S中，令d(j)=mind,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中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从 v到此顶点只包括 S中的顶点为中间顶点的当前最短路径长度。 算法具体步骤(1)初始时，S只包含源点，即S= v的距离为0。U包含除v外的其他顶点， U中顶点

5、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算法的时间复杂度为0mA2)空间复杂度取决于存储方式，邻接矩阵为0(nA2)迪杰斯特拉（Dijkstra）算法是单源顶点最短路径求解算法。木例以VI结点（1”结点

6、）为计算源。有向图与邻接矩阵:有向网络邻接矩阵121 r oio2 8o3 O0004 88345g 3010050 B 80«1020060880算法的动态执行情况表格中的项目说明:1、循环：执行算法的次数。2、源：通过运算后，当前已被加入的结点©3、K+1：本次运兑新加入的结点。4、目的结点开销：从源结点到目的结点最优路件的开销45、前卵结点：所力.结点按照最优路径，逆回到VI结点的上一个结点。运算过程：步骤1:步骤2：步骤3：步骤4：步骤5：循环源-1目的结点开销前项结点1234512345初始化1010max30100010111(1,220106030100012

7、112“2用40105030100014113(L2.43130105030600141341.243.5)501050306001413持加入节点：75 加入V5当前到V5的彷路TF：VI今V5,开俏:100V1)V4)V5, JTfil： 90VI -»V4->V3->V5.开箱：60 优堆开梢为60的链路.最短路的算法一Dijkstra莫.法在图G中，给定s和I两个顶点。从s到I可以有多条路径,从这多条路中找出长度最 小的路，这样的路称为从s到t的最短跖。设每条弧的长度均为非负值。下面的第法是由狄克斯特拉(Dijkslra, 1959)提出的，其想法是：设已知图中最

8、接近 顶点s的m个顶点以及从顶点s到这些顶点中每一个顶点的最短路(从s到其本身的最短 路是零路，即没有.弧的路，KK度为0).对顶点s和这m个顶点着色。然后，最接近于s ©的笫mH个顶点可如卜求之：对于每一个未着色的顶点y,考虑所TT已着色顶点x,把弧(x, y)接在从s到x的最 短路后面，这样就得到从"到y的m条不同路。从这皿条路中选出最短的路，它就是从s 到y的最短路。相应的y点就是最接近于s的第mH个顶点。因为所有孤的长度都是非负值, 所以从。到最接近于s的笫m+1个顶点的最短路必然只使用己着色的顶点作为中间顶点。从nr()升始，符这个过程重复进行卜去，直至求得从s到

9、t的最短路为止。算法；狄克斯特拉班短路匏法第1步开始，所有弧和顶点都未着色0对每个顶点x指定一个数d(x), d(x)表示从s到x 的最短路的K度(中间顶点均已着色开始时，令d(s)-0, d(x)=g (对所仃xKs)。y表 示己着色的最后一个顶点。对始点s着色,令yr。第2步对于每个未着色顶Hx,重新定义d(x)如下：d(x)=min( d(x). d (y)+a(y, x)公式对于所有犬着色顶点x，如d(x)=8,则算法定止。因为此时从s到任一未着色的顶点都没 有路。否则，对具有d(x)最小值的未着色顶点k进行着色。同时把弧(y, x)着色(指向顶 点x的弧只有一条被着色)。令y=xo第

10、3步如果顶点t已着色，则算法终上。这时已找到一条从s到t的最短路。如果t未看 色，则转第2步。注意；已着色的弧不能构成一个圈，而是构成一个根在s的树形图，此树形图称为最短路树 形图。若X姑最短路树形图中的任一顶点，则从S到X的唯一的一条路是从S到X的最短路. 这个算法可以看成是根在顶点S的树形图的生K过程。一月到达顶点t,生K过程就停止。 例：给定不向图如下图所示，用狄克斯特拉算法找出从S到I的最短路径。第1步d(a)=min d(a), d(s)+a(s, a) 1=min (o°, 0+4) =4d(b)-ir)in d (b), d(s)+a(s, b)=min00, 0+7=

11、7d(r) =min ( d(c), d (s)+a(s, c)=min(8, 0+3) =3d(d) =min d(d), d(s) +a(s, d)=min 00, 0+8)=8d(t)=min d(t), d(s)+a(s, t)=min (oo, 0»co)=o0由丁 d(c)=3是最小值，所以对c点着色,并对确定d(c)的弧(s,c)着色。见图a)。第3步顶点I未着色，返回第2步，1a)第2步y=dd(a)=minl d(a), d(c)+a(c,a)二 min 4.3+8)二 4d(b)=nin d(b), d(c)+a(c,b)Fin (7. 3+8二7d(d)nin(

12、 d(d)9 d(c) *a(c, d)二min 8, 3+3 =6d(t)=min d(t), d(c)+a(c, t)=min(8,3+8 =co由于d(a)=4是最小优，所以对顶点a着色.并对确定d(a)的孤着色.见图h).第3步 顶点工未着色，返回第2步.第2步y=ad(b)=min ( d(b), d (a)1 a (a, b)=min (7, 4+3 =7d(d) =min ( d(d), d (a) +a (at d) =min (6t 4+2 =6d(t)=nin( d(t)» d(a) +a(at t) =min g 4- eo)=©od(d)=6是最小位

13、，对d着色，确定d(d)的弧有两条(即(c,d)和(a, d),可任选其中的条,对其着色,我们选(c,d)见图c)第3加顶点1未看色,返I可第2米.d(b) =min cl (b), d(d)+a(d, b)=min 7, 6+°°=7d(t)=min d(t), d(d)+a(d, l)i n 00, 6+2 =8d(b)=7是最小值,对点b着色,对确定d(b)的弧(s,b)着色。见图d)。第3步顶点t未着色，返回第2步。第2步y=bd(t)=min d(t), d (b) +a (b, t)=niin(8, 7+2|=8对点i及弧(d, 1)着色最终的最短路树形图由弧(

14、s, c) (s, a) (c, d)(s, h)利(d, t) 组成，见图e)。从s到t的最短路由弧(s, c) (c, d)和(d, t)组成，其长度为3+3+2=8。e)Dijkstra算法的基本思想是:设目的节点（就恂造spf例而言，是相节点）为h 任一条福跳"，）的长度为为， 怖个小点，到我的最也跣径长度估计为。小 定义所仃节点的集合为a,定义集合户曰4, 并设定集ft P晌初始值为P = 外0在算法迭代的过程中，如果。&已经变成一个确定值，则将j标尼为固定点，并将其加 入比合尸*在外法的每一步迭代中，在尸以外的H点中，必定是选择与目的节点我最近的 ”点加入到尸中.

15、算法的R阵步骤如下:”<.）尸=£ %=。， jwP. f若J和&不是相邻节点，则=a求解使4 = min D.成。的八，w . 即寻找下一个和目的节点最近的节点：令P=PUi-/2二八，算法第束口（3）对所用/匚7.置0井=呷n/）9 R+dJ,返I可4獴2）这样.通过一心上的迭代，就M以求出某一外点到算他每一个节点的最旬路存，也就是 说.构造出了以该节点为根节点的$PF树.卜面是利用Dijkstra即法构冷SPF期的一个例子。图23示一个网络的拓扑结构.箸个路由器以及各条情廊的代价已经标出.现在计科 以R为根节点的5PF树，来说明Dijk5g算法的I作过程：82 J3DijkMra算法成川举例求解以RI为根力点的SP卜树的儿骤如下:（1） P = m,很显然，与R1直接相邻的节点只有R2和R3,其中Dr” =八=6 , 。沏="科九=I，其他节点到R1的蹈禹都是无穷大（因为没书和R1邻接）.（2）在4加和W中，Dr31a蚊小,所以下一个即离R1最近的节点i是R3,曲昌为 I：此