Dijkstra算法实现综述

1、di jkstra算法实现综述摘要：dijkstra算法是典型的最短路径算法，用于计算一个结点到其他所有结点 的最短路径。dijkstra的变形和应用非常多，需要一定的时间和题量积累，通过 改进获得精度较高的结果。一、刖吕最短路径问题是在给定的网络图中寻找出一条从起始点到目标点之间最短 路径。最短路算法不仅在gis的交通路线导航、路径分析领域应用广泛，在解 决路径搜索相关的应用中也十分普遍，包括网络路由算法、机器人探路、人工 智能、游戏设计等等。最短路径是在很多的路径中，找寻行经距离最短、或者 说所花费成木最少的路径。由於交通运输的便利与普及，所以两地之间有发生 运送或者资讯的传递下，最短路径

2、(shortest path)的问题随吋都可能会冇需求 产生。一般应用的领域涵盖很广泛，如物流配送、货运快递邮务信件配送、警 力巡逻、消防救灾救护、设施规划、生产排程、电子电路、水管配置、行动通 讯、及电脑网路等。二、技术说明：dijkstra 算法迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959年提出的，因此 又叫狄克斯特拉算法。dijkstra经典算法是曲计算机科学家edsger dijkstra 在文献中提出的。它是一个图的搜索算法，解决带非负权重图的单元最短路径问 题并产生一棵最短路径树。该算法经常使用在网络路由和地理信息系统屮。dijkstra算法是典型的最短路径算法，用于计算

3、一个结点到其他所有结点 的最短路径。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图屮最 短路径问题。dijkstra算法的基本思想是以源点为圆心，按最短路径长度递增 的顺序通过对路径长度迭代得到从源点到其他各目标结点的最短路径。迪杰斯特 拉算法主要特点是以起始点为屮心向外层层扩展，直到扩展到终点为止。 dijkstra算法是典型的算法。dijkstra算法是很有代表性的算法。dijkstra 般的表述通常有两种方式，一种用永久和临吋标号方式，一种是用open, close 表的方式，这里均采用永久和临吋标号的方式。注意该算法要求图中不存在负权 边。其基本原理是：每次新扩展一个距离最短的

4、点，更新与其相邻的点的距离。 当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点 的距离永远不会再被改变，因而保证了算法的正确性。不过根据这个原理，用 dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的 距离，冇可能就破坏了已经更新的点距离不会改变的性质。具体如下：（1）算法分配给每个节点一个初步的距离值：设置初始节点为零和其他节点 为无穷；（2）将当前访问节点设置为初始节点，其他的所有节点设置为未访问节点， 并创建一个未访问节点集合；（3）针对当前节点，计算其与所有邻接节点的距离。将计算出来的距离值与 当前值进行比较，指定较小的一个。（4）当我们

5、考虑完当前节点的所冇邻接节点，标记当前为已访问，并将其从 未访问集合删除。已访问节点将永远不会被访问；（5）选择为访问过的标记最小试探距离的节点，并将其作为新的当前节点， 然后冋到步骤3；（6）如果终止节点已标记访问或者最小试探性距离在未设置节点之间是无限 的，该算法已完成。举例来说，如果图中的顶点表示城市，而边上的权重表示著城市间开车行经 的距离。dijkstra算法可以用来找到两个城市z间的最短路径。dijkstra算法的输入包含了一个有权重的有向图g,以及g中的一个来源顶 点s。我们以v表示g中所有顶点的集合。每一个图屮的边，都是两个顶点所 形成的有序元索对。（u,v）表示从顶点u到v有

6、路径相连。我们以e所冇边的集 合，而边的权重则由权重函数w: e - 0, g定义。因此，讥u,v）就是从顶 点u到顶点v的非负花费值（cost） o边的花费可以想像成两个顶点z间的距离。 任两点间路径的花费值，就是该路径上所有边的花费值总和。已知有v中有顶 点s及t, dijkstra算法可以找到s到t的最低屁费路径（i. e.最短路径）。这 个算法也可以在一个图中，找到从一个顶点s到任何其他顶点的最短路径。 算法描述这个算法是通过为每个顶点v保留目前为止所找到的从s到v的最短路径来 工作的。初始时，源点s的路径长度值被赋为0 （ds二0）,同时把所有其他顶 点的路径长度设为无穷大，即表示我

7、们不知道任何通向这些顶点的路径（对于v 中所有顶点v除s外dv二8）。当算法结束吋，dv中储存的便是从s到v的 最短路径，或者如杲路径不存在的话是无穷大。dijstra算法的基础操作是边 的拓展:如果存在一条从u到v的边,那么从s到u的最短路径可以通过将边（u, v） 添加到尾部来拓展一条从s到v的路径。这条路径的长度是du+w（u,v）o如果 这个值比目前已知的dv的值要小,我们可以用新值来替代当前dv中的值。 拓展边的操作一直执行到所有的dv都代表从s到v最短路径的花费。这个算 法经过组织因而当du达到它最终的值的时候没条边（u, v）都只被拓展一次。算法维护两个顶点集s和qo集合s保留了

8、我们已知的所冇dv的值已经是 最短路径的值顶点，而集合q则保留其他所有顶点。集合s初始状态为空，而后 每一步都有一个顶点从q移动到s。这个被选择的顶点是q中拥有最小的du 值的顶点。当一个顶点u从q中转移到了 s中，算法对每条外接边（u,v）进行拓 展。在下而的算法中,u:=extract_min（q）在在顶点集q中搜索冇最小的du值 的顶点u。这个顶点被从集合q中删除并返冋给用户。1 function dijkstra（g, w, s）2for each vertex v in vg/初始化3dv := infinity4previousv := undefined5ds:二 06s :二

9、empty set7q :二 set of all vertices8while q is not an empty set/ dijstra 算法主体9u :二 extract_min(q)10s :二 s union u11for each edge (u,v) outgoing from u12if dv > du + w(u, v)/拓展边(u, v)13dv:二 du + w(u, v)14previousv:二 u如果我们只对在s和t之间寻找一条最短路径的话，我们可以在第9行添加 条件如果满足u二t的话终止程序。现在我们可以通过迭代来回溯出s到t的最短路径1 s := emp

10、ty sequence2 u :二 t3 whi1e defined u4 insert u to the beginning of s5 u := previousu现在序列s就是从s到t的最短路径的顶点集.di jkstra算法的过程dijkstra算法又称为单源最短路径，所谓单源是在一个有向图中，从一个顶点 出发，求该顶点至所冇可到达顶点的最短路径问题。设g二(v, e)是一个有向图，v表示顶点，e表示边。它的每一条边(i, j) 属于e,都有一个非负权w (i, j),在g屮指定一个结点vo,要求把从vo到g 的每一个接vj (vj属于v)的最短有向路径找出來(或者指出不存在)。 di

11、jstra算法是运用贪心的策略，从源点开始，不断地通过相联通的点找出到其 他点的最短距离。基亲思想是：设置一个顶点的集合s,并不断地扩充这个集合，一个顶点属于集 合s当且仅当从源点到该点的路径已求出。开始吋s屮仅有源点，并且调整非s 中点的最短路径长度，找当前最短路径点，将其加入到集合s,直到终点在s中。 基本步骤：(1) 把所冇结点分成两组：第一组：包描已经确定最短路径的结点；第二组：包括尚未确定最短路径的结点。(2) 开始时，第一组只包含起点，第二组包含剩余的点；(3) 用贪心的策略，按最短路径长度递增的顺序把第二组的结点加到第一组 去，直到vo可达的所有结点都包含于笫一组中。在这个过程中

12、，不断更新最短路 径，总保持从vo到第一组各结点的最短路径长度dist都不大于从vo 到第二组任何结点的路径长度。(4) 每个结点对应一个距离值，第一组结点对应的距离就是vo到此结点的 最短路径长度，第二组结点对应的距离值就是vo由第一组结点到此结 点的最短路径长度。(5) 直到所冇的顶点都扫描完毕(vo可达的所冇结点都包含于第一组中)， 找到vo到其它各点的所有最短路径。三、原理描述:令e接矩阵的dijkstra算法从某个源点到其余各顶点的最短路径问题：dijkstra算法解决了有向图g二(v,e)上带权的单源最短路径问题，但是要求所 有边的权值非负(原因后面叙述)。dijkstra算法思想

13、为：设g二(v, e)是一个带权有向图，把图中顶点集合v分 成两组，第一组为以求出最短路径顶点的集合(用s表示，初始时s屮只冇一个源点，以后每求得一条最短路径，就将其加入到集合 s中，直到全部顶点都加入到s中，算法就结束了),第二组为其余未确定最短路径的顶点的集合(用u表示)，按最短路径长度的 递増次序依次把第二组的顶点加入s中。在加入的过程中，总保持从源点v到s中各顶点的最短路径长度不大于从源点v到u中 任何顶点的最短路径长度。此外，每个顶点对应一个距 离，s中的顶点的距离就是从v到此顶点的最短路径长，u中的顶点的距离， 是从v到此顶点只包括s屮的顶点为屮间顶点的当前最短路径长度。伪代码：d

14、ijkstra (g, w, s)1 1n1t1al1ze-s1ngle-source (g, s) /初始源2 s - 03 q - vg4 while q h 05 do u - extract-min(q)/找出q中距离源最短路径6 s - s u u7 for each vertex v e adju8 do relax (u, v, w)/松弛操作单源最短路径算法中使用了松弛(relaxation)操作。对于每个顶点vgv, 都设置一个屈性dv,用来描述从源点s到v的最短路径上权值的上界，称为 最短路径估计(shortest-path estimate)。n v代表s到v的当前最短路

15、径屮 v点之前的一个点的编号。一次松弛操作可以减小最短路径估计的值dv0每个单源最短路径算法屮都会调用initialize-single-source,然后重复 对边进行松弛的过程。另外，松弛是改变最短路径和前趋的唯一方式。下面的伪 代码对边(u, v)进行了一步松弛操作。1 relax (u, v, w)2 if (d v >d u +w(u, v)3 then dv -*-du+w(u, v)4 兀v u邻接表的dijkstra算法当一个图为稀疏图吋，顶点个数相对比边的个数多。此时用邻接表来存储图，不 仅节省存储空间，在算法实现上也会更高效。这里实现o(e+v)*iegv),近似 的

16、o(elogv)复杂度的dijkstra算法。其中e为边的个数。正如在前而所讨论的，迪杰斯特拉算法的维护两组顶点集合，一组已经包含在 spt(最短路径树)中的顶点集合，另一组是未包含在spt内的顶点集合。算法的优化在于使用最小堆作为一个优先队列。因为，每次迭代我们都要从 未包含在spt内的顶点集合中找到一个最小距离的节点，普通作为是遍历一遍， 复杂度为0(v),使用最小堆，可以降低到0(1), z家取出堆顶点即可。优先队列的dijkstra算法算法思想：(1) 在任意时刻，我们都要得到从源点到所有顶点的估算距离，并维持一个 顶点集合s,若顶点v在s中，则说明从源点到v的最短路径已知；(2) 在

17、每一次将不在s中的顶点v加到s中去时，总是选择从源点到v的估算距离最小的；(3) 顶点v加入s屮之后，对于所有与v相邻的顶点(不属于s),更新它们的估算距离。伪代码如下：1 dijkstra(g, w, s)2 ds -03 for each v e v - s由(2),我们看到了贪心的影了，在每次选择时，我们总是想选择花费最小 的，正常人都会这样去想，至于为什么这样选，这样选对不对，我们将在后而进 行证明。/g表示图，w表示权值函数，s表示源顶点 /源点到源点最短路为0/3-8行均为初始化操作4 do dv5 pare ntvjnil6 s07 q-v/此处q为优先队列，存储未进入s的各顶点

18、以及从源点到这8 /些顶点的估算距离，采用二叉堆(最小堆)实现， 越小越优先9 while qh010 do u-extract-min(q) /提取估算距离最小的顶点，在优先队列中位于顶部，11 /出队列，放入集合s中12 s-su u13 for each v e adj (u) /松弛操作，对与u相邻的每个顶点v,进行维持三14 /角不等式成立的松弛操作。15 do if dv > du + w(u, v)16 then dv = du + w(u, v)/这一步隐含更新优先队列屮的值,1718parentvu/decreaseo/置v的前驱结点为ui、算法实现邻接表：void i

19、nsert(int a, int b, int w) /尾插法，插入以a为起点，b为终点，权为w的边，效率不如头插，但是可以去重边 arcnode * q 二 new arcnode(b, w);if (vera, firarc = null)vera. firarc = q;elsearcnode * p 二 vera. firarc; if (p-vertex 二二 b)if (p->weight > w) p->weight 二 w;return ;while(p->next != null)if (p->next->vertex = b)if (p-

20、>ncxt-weight > w); p->next->weight = w;return ;p = p->next;p->next = q;void tnsert2(int a, int b, int w)/头插法，效率更高，但不能去重arcnode * q 二 new arcnode (b, w); if (vera. firarc = null)vera. firarc = q;elsearcnode * p 二 vera. firarc; q->next = p;邻接矩阵:void dijkstra(int s)/di jkstra算法，传入源

21、顶点for(int i = 1; i <= n; i+) di. id 二 i; di weight = inf; parenti = -1; visitedi = false;ds. weight 二 0; q. push(ds);while(!q. empty() 操作node cd 二 q. top();q pop (); int u = cd. id;if(visitedu) continue;visitedu二 true;松弛操作 for (int v/初始化估算距离置inf每个顶点都无父亲节点源点到源点最短路权值为0压入队列中算法的核心，队列空说明完成了/取最小估算距离顶点=

22、1； v <= n; v+) /找所冇与他相邻的顶点，进行松弛操作，更新估算距离，压入队列。if (v != u &&!visitedv &&dv, weight >du wcight+wuv)dv. weight = du. weight+wuv;parentv二 u;q. push(dv);优先队列：void create_graph(int m)int i, s, e, w;arcnode tcmp_arc;for(i=l;i<=m;i+)cout«，/输入第条边的起点、终点和权值：; cin>>s>>e

23、>>w;tcmp_arc 二 new arcnode; temp_arc->arcnode_lnit(e, w); temp_arc->next=heads. firstarc; heads. firstarc=temp_arc; "arcsum=m;cout«z，建图完成z，«endl;void dijkstra(int sre)dij_node first, next, temp; priorityqueue <dij_node> q; arcnode *arc;int i;for(i=l;i二vexsum;i+)disi=

24、inf;findi二false;dissrc=0;temp. node_init(sre, dissrc);q. push (temp);whi le(!q. empty ()first二q. top();q. pop 0 ;findfirst. v二true;for(arc=headfirst, v. firstarc;arc!=null;arc=arc->next)if(findarc->v) continue;next.nodc_init (arc>v, first, dis+arc->wcight); if (next, dis < disnext. v)

25、disnext. v二next. dis;q. push (ncxt);五、测试与运行算法结果：邻接矩阵请输入顶点数和边数：5 7请输入边以及权值（a, b, c）1 2 12 3 13 4 14 5 11 5 11 3 12 4 1请输入起点和终点：2 5最短路径权值为：2process returned 0 (0x0) execution time : 29.484 s press any key to continue.邻接表 请输入顶点数和边数:5 7请输入边以及权值(a, b, c)1 2 12 3 13 4 14 5 11 5 12 4 11 3 1请输入起点和终点：2 4最短路径

26、权值为：1process rcturncd 0 (0x0) cxccution time : 24.055 s press any key to continue.123456条边的起点、终点和权值：1310条边的起点、终点和权值：1530条边的起点、终点和权值：16100条边的起点、终点和权值：235条边的起点、终点和权值：3450条边的起点、终点和权值：5420优先队列输入顶点总数：6 输入边的总数：8 输入第 输入第 输入第 输入第 输入第 输入第输入第7条边的起点、终点和权值：4 6 10 输入第8条边的起点、终点和权值：5 6 60 建图完成to2最短路径不存在to3is: 10to

27、4is: 50to5is: 30to6is: 60process returned 0 (0x0) execution time : 55.614 s press any key to continuc.01310 0 0 3 1 5 6 1 10543024501640665占小点占小占小占小占小占吿小终终终终终终终终占小点占吿小点占小点占小 己-己-nj- pu-己-己-5-己- dnjtnd人只nt 刁dn8二.dh二qljjy y一 i jmu二 矢気边边边边边边边边 silzi 貳肌1 2 3 4 5 6 2 8感耿i k边第第第第第第第蔓兀2 3 x入人人人人人人a-a-toto1

28、2345678径0& 1s一-°一 矢s4oti 1 1 1 1s 1 5ottime : 55.614 sprocess urned 0 <0x0> execut丄on press any key to continue.结果分析时间复杂度我们可以用大0符号将dijkstra算法的运行时间表示为边数m和顶点数n 的函数。dijkstra算法最简单的实现方法是用一个链表或者数组来存储所有顶 点的集合q,所以搜索q中最小元索的运算(extract-min(q)只需要线性搜索q 中的所有元素。这样的话算法的运行时间是0(n2)o对于边数少于n2稀疏图来 说，我们可以用

29、邻接表来更冇效的实现dijkstra算法。同时需耍将一个二叉堆 或者斐波纳契堆用作优先队列来寻找最小的顶点(extract-min)。当用到二叉堆 的吋候，算法所需的吋间为0(m+n)log n),斐波纳契堆能稍微提高一些性能， 让算法运行时间达到0(m + n log n)o相关问题和算法在dijkstra算法的基础上作一些改动，可以扩展其功能。例如，有时希望 在求得最短路径的基础上再列出一些次短的路径。为此，可先在原图上计算出最 短路径，然后从图中删去该路径中的某一条边，在余下的子图中重新计算最短路 径。对于原最短路径屮的每一条边，均可求得一条删去该边后子图的最短路径， 这些路径经排序后即

30、为原图的一系列次短路径。ospfcopcn shortest path first, 开放最短路径优先)算法是dijkstra算法在网络路由中的一个具体实现。与dijkstra算法不同，bellman-ford算法可用于具有负花费边的图，只要 图屮不存在总屁费为负值且从源点s可达的环路(如果有这样的环路，则最短 路径不存在，因为沿环路循环多次即口j无限制的降低总花费)。与最短路径问题 有关的一个问题是旅行商问题(traveling salesman problem),它要求找出通过 所冇顶点恰好一次月最终回到源点的最短路径。该问题是np难的；换言z,与 最短路径问题不同，旅行商问题不太可能具有

31、多项式时间算法。如果有已知信息 可用来估计某一点到口标点的距离，则可改用a*算法，以减小最短路径的搜索 范围。空间复杂度分析对于数据的存储传统的dijkstra算法采用图论屮的邻接矩阵方法，其存 储量为n# n(n为网络图中的节点数)，通常的网络图尽管节点很多，但与节 点相关联的节点数口并不多，一般都为稀疏图，这样该存储方法将浪费大量的 空间，而且在计算时亦要花费大量的时间遍历无意义的数据。而本文的改进算 法采用了邻接表的链式存储结构，对于一个无向图來说，其存储量为0(e+2n) (e为节点列表屮同节点关联的所有弧段数目)。另外述使用了两个数组，其 中一个数组dv用来存储所求得源点到其它所有节

32、点的最短路径值，另外一 个数组tv用来暂存待排序节点。所以总的空间复杂度为0(e+4n)。与传 统dijkst ra算法相比较，节省了空间，提高了存储效率。小结通过木次大作业，我对dijkstra算法有了更深入的理解。dijkstra算法是 典型的最短路径算法，用于计算一个结点到其他所有结点的最短路径。是从一个 顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。dijkstra 算法的基本思想是以源点为圆心，按最短路径长度递增的顺序通过对路径长度迭 代得到从源点到其他各目标结点的最短路径。迪杰斯特拉算法主要特点是以起始 点为屮心向外层层扩展，直到扩展到终点为止。dijkstra算法是典型的算法。 dijkstra算法是很有代表性的算法。dijkstra 般的表述通常冇两种方式，一 种用永久和临时标号方式，一种是用open, close表的方式，这里均采用永久和 临时标号的方式。注意该算法要求图屮不存在负权边。其基本原理是：每次新扩展一个距离最短的点，更新与其相邻的点的距离。 当所有边权都为正吋，由于不会存在一个距离更短的没扩展过的点，