苏州学校网站建设,郑州注册公司代理记账,wordpress怎么建立二级菜单,盘县 网站建设百度首页 登录 注册 新闻网页贴吧知道音乐图片视频地图百科文库进入词条搜索词条帮助首页分类艺术科学自然文化地理生活社会人物经济体育历史特色百科历史上的今天数字博物馆史记2015城市百科二战百科非遗百科用户蝌蚪团燃梦计划百科任务百科商城权威合作合作模式常见问题联系方… 百度首页 登录 注册 新闻网页贴吧知道音乐图片视频地图百科文库 进入词条 搜索词条帮助 首页 分类 艺术 科学 自然 文化 地理 生活 社会 人物 经济 体育 历史 特色百科 历史上的今天 数字博物馆 史记·2015 城市百科 二战百科 非遗百科 用户 蝌蚪团 燃梦计划 百科任务 百科商城 权威合作 合作模式 常见问题 联系方式 手机百科 网页版 个人中心 收藏 707 6 迪杰斯特拉算法 编辑 本词条由“科普中国”百科科学词条编写与应用工作项目 审核 。 迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展直到扩展到终点为止。[1] 中文名迪克斯特拉算法外文名Dijkstras Algorithm 分 类计算机算法用 途单源最短路径问题 目录 1 定义 2 原理 3 问题描述 4 算法思想 5 算法实现 ▪ pascal语言 ▪ java语言 ▪ C语言 6 堆优化 ▪ 思考 ▪ 实现 ▪ 代码 定义 编辑 Dijkstra算法是典型的算法。Dijkstra算法是很有代表性的算法。Dijkstra一般的表述通常有两种方式一种用永久和临时标号方式一种是用OPEN, CLOSE表的方式这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。[2] 原理 编辑 1.首先引入一个辅助向量D它的每个分量 D 表示当前所找到的 Dijkstra算法运行动画过程 从起始点 即源点 到其它每个顶点 的长度。 例如D[3] 2表示从起始点到顶点3的路径相对最小长度为2。这里强调相对就是说在算法执行过程中D的值是在不断逼近最终结果但在过程中不一定就等于长度。[1] 2.D的初始状态为若从 到 有弧即从 到 存在连接边则D 为弧上的权值即为从 到 的边的权值否则置D 为∞。 显然长度为 D Min{ D | ∈V } 的路径就是从 出发到顶点 的长度最短的一条路径此路径为( )。 3.那么下一条长度次短的是哪一条呢也就是找到从源点 到下一个顶点的最短路径长度所对应的顶点且这条最短路径长度仅次于从源点 到顶点 的最短路径长度。 假设该次短路径的终点是 则可想而知这条路径要么是( )或者是( )。它的长度或者是从 到 的弧上的权值或者是D 加上从 到 的弧上的权值。 4.一般情况下假设S为已求得的从源点 出发的最短路径长度的顶点的集合则可证明下一条次最短路径设其终点为 要么是弧( )或者是从源点 出发的中间只经过S中的顶点而最后到达顶点 的路径。 因此下一条长度次短的的最短路径长度必是D Min{ D | ∈V-S }其中D 要么是弧( )上的权值或者是D ( ∈S)和弧( , )上的权值之和。 算法描述如下 1令arcs表示弧上的权值。若弧不存在则置arcs为∞在本程序中为MAXCOST。S为已找到的从 出发的的终点的集合初始状态为空集。那么从 出发到图上其余各顶点 可能达到的长度的初值为Darcs[Locate Vex(G, )] ∈V 2选择 使得D Min{ D | ∈V-S } 3修改从 出发的到集合V-S中任一顶点 的最短路径长度。[1] 问题描述 编辑 在无向图 G(V,E) 中假设每条边 E[i] 的长度为 w[i]找到由顶点 V0 到其余各点的最短值。[2] 算法思想 编辑 按路径长度递增次序产生算法 把顶点集合V分成两组 1S已求出的顶点的集合初始时只含有源点V0 2V-ST尚未确定的顶点集合 将T中顶点按递增的次序加入到S中保证 1从源点V0到S中其他各顶点的长度都不大于从V0到T中任何顶点的最短路径长度 2每个顶点对应一个距离值 S中顶点从V0到此顶点的长度 T中顶点从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度 依据可以证明V0到T中顶点Vk的或是从V0到Vk的直接路径的权值或是从V0经S中顶点到Vk的路径权值之和 反证法可证 求最短路径步骤 算法步骤如下 G{V,E} 1. 初始时令 S{V0},TV-S{其余顶点}T中顶点对应的距离值 若存在V0,Vid(V0,Vi)为V0,Vi弧上的权值 若不存在V0,Vid(V0,Vi)为∞ 2. 从T中选取一个与S中顶点有关联边且权值最小的顶点W加入到S中 3. 对其余T中顶点的距离值进行修改若加进W作中间顶点从V0到Vi的距离值缩短则修改此距离值 重复上述步骤2、3直到S中包含所有顶点即WVi为止 算法实现 编辑 pascal语言 下面是该算法的Pascal程序 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 type boolarray[1..10]ofboolean; arrarray[0..10]ofinteger; var a:array[1..10,1..10]ofinteger;//存储图的邻接数组无边为10000 c,d,e:arr;//c为最短路径数值,d为各点前趋, t:bool;//e路径t为辅助数组 i,j,n,m:integer; inf,outf:text; procedureinit;//不同题目邻接数组建立方式不一样 begin assign(inf,inputfile); assign(outf,outputfile); reset(inf); rewrite(outf); read(inf,n); fori:1tondo begin forj:1tondo begin read(inf,a[i,j]); ifa[i,j]0then a[i,j]:10000; end; end; end; proceduredijkstra(qi:integer;t:bool;varc{,d}:arr); //qi起点,{}中为求路径部分,不需求路径时可以不要 var i,j,k,min:integer; begin t[qi]:true; //t数组一般在调用前初始,除起点外所有节点都化成false,也可将部分点初始化成true以回避这些点 fori:1tondo d[i]:qi; d[qi]:0; fori:1tondo c[i]:a[qi,i]; fori:1ton-1do begin min:maxint;//改为最大值 forj:1tondo if(c[j]min)andnott[j]then begin k:j; min:c[j]; end; t[k]:true; forj:1tondo if(c[k]a[k,j]c[j])andnott[j]then begin c[j]:c[k]a[k,j]; d[j]:k; end; end; end; proceduremake(zh:integer;d:arr;vare:arr);//生成路径,e[0]保存路径 var i,j,k:integer;//上的节点个数 begin i:0; whiled[zh]0do begin inc(i); e[i]:zh; zh:d[zh]; end; inc(i); e[i]:qi; e[0]:i; end; 主程序调用求长度初始化t然后dijkstra(qi,t,c,d) 求路径make(m,d,e) m是终点 java语言 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 //初始化路径都为最大值。 intpath[][]newint[n1][n1]; for(inti1;in1;i){ for(intj1;jn1;j) path[i][j]Integer.MAX_VALUE; } //这里需要输入path[i][j]的具体内容如果有重复数据的话需要更新路径为最小值。 intminLen[]newint[n1]; //visit初始为0防止回溯 intvisit[]newint[n1]; //初始化1到其他点的距离。 for(inti1;in1;i){ minLen[i]path[1][i]; } voidDijkstra(){ minLen[1]0; visit[1]1; intminj1; for(inti1;in1;i){ intminInteger.MAX_VALUE; for(intj1;jn1;j){ if(visit[j]0minLen[j]min){ minminLen[j]; minjj; } } visit[minj]1; for(intj1;jn1;j){ if(visit[j]0minLen[minj]!Integer.MAX_VALUEpath[minj][j]! Integer.MAX_VALUEminLen[j](minLen[minj]path[minj][j])){ minLen[j]minLen[minj]path[minj][j]; } } } } C语言 下面是该算法的C语言实现[1] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 #includestdio.h #includestdlib.h #define max 11000000000 inta[1000][1000]; intd[1000];//d表示某特定边距离 intp[1000];//p表示永久边距离 inti,j,k; intm;//m代表边数 intn;//n代表点数 intmain() { scanf(%d%d,n,m); intmin1; intx,y,z; for(i1;im;i) { scanf(%d%d%d,x,y,z); a[x][y]z; a[y][x]z; } for(i1;in;i) d[i]max1; d[1]0; for(i1;in;i) { min1max1; for(j1;jn;j) if(!p[j]d[j]min1) { min1d[j]; kj; } p[k]j; for(j1;jn;j) if(a[k][j]!0!p[j]d[j]d[k]a[k][j]) d[j]d[k]a[k][j]; } for(i1;in;i) printf(%d-,p[i]); printf(%d\n,p[n]); return0; } 大学经典教材数据结构(C语言版 严蔚敏 吴为民 编著) 中该算法的实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 /* 测试数据 教科书 P189 G6 的邻接矩阵 其中 数字 1000000 代表无穷大 6 1000000 1000000 10 100000 30 100 1000000 1000000 5 1000000 1000000 1000000 1000000 1000000 1000000 50 1000000 1000000 1000000 1000000 1000000 1000000 1000000 10 1000000 1000000 1000000 20 1000000 60 1000000 1000000 1000000 1000000 1000000 1000000 结果 D[0] D[1] D[2] D[3] D[4] D[5] 0 1000000 10 50 30 60 */ #include iostream #include cstdio #define MAX 1000000 using namespace std; int arcs[10][10];//邻接矩阵 int D[10];//保存最短路径长度 int p[10][10];//路径 int final[10];//若final[i] 1则说明 顶点vi已在集合S中 int n 0;//顶点个数 int v0 0;//源点 int v,w; void ShortestPath_DIJ() { for (v 0; v n; v) //循环 初始化 { final[v] 0; D[v] arcs[v0][v]; for (w 0; w n; w) p[v][w] 0;//设空路径 if (D[v] MAX) {p[v][v0] 1; p[v][v] 1;} } D[v0] 0; final[v0]0; //初始化 v0顶点属于集合S //开始主循环 每次求得v0到某个顶点v的最短路径 并加v到集合S中 for (int i 1; i n; i) { int min MAX; for (w 0; w n; w) { //我认为的核心过程--选点 if (!final[w]) //如果w顶点在V-S中 { //这个过程最终选出的点 应该是选出当前V-S中与S有关联边 //且权值最小的顶点 书上描述为 当前离V0最近的点 if (D[w] min) {v w; min D[w];} } } final[v] 1; //选出该点后加入到合集S中 for (w 0; w n; w)//更新当前最短路径和距离 { /*在此循环中 v为当前刚选入集合S中的点 则以点V为中间点 考察 d0vdvw 是否小于 D[w] 如果小于 则更新 比如加进点 3 则若要考察 D[5] 是否要更新 就 判断 d(v0-v3) d(v3-v5) 的和是否小于D[5] */ if (!final[w] (minarcs[v][w]D[w])) { D[w] min arcs[v][w]; // p[w] p[v]; p[w][w] 1; //p[w] p[v] [w] } } } } int main() { cin n; for (int i 0; i n; i) { for (int j 0; j n; j) { cin arcs[i][j]; } } ShortestPath_DIJ(); for (int i 0; i n; i) printf(D[%d] %d\n,i,D[i]); return 0; } 堆优化 编辑 思考 该算法复杂度为n^2,我们可以发现如果边数远小于n^2,对此可以考虑用堆这种数据结构进行优化取出最短路径的复杂度降为O(1)每次调整的复杂度降为Oelogne为该点的边数所以复杂度降为O((mn)logn)。 实现 1. 将与源点相连的点加入堆并调整堆。 2. 选出堆顶元素u即代价最小的元素从堆中删除并对堆进行调整。 3. 处理与u相邻的未被访问过的满足三角不等式的顶点 1):若该点在堆里更新距离并调整该元素在堆中的位置。 2):若该点不在堆里加入堆更新堆。 4. 若取到的u为终点结束算法否则重复步骤2、3。 代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 procedureDijkstra; var u,v,e,i:longint; begin fillchar(dis,sizeof(dis),$7e);//距离 fillchar(Inh,sizeof(Inh),false);//是否在堆中 fillchar(visit,sizeof(visit),false);//是否访问过 size:0; e:last[s]; whilee0do//步骤1 begin u:other[e]; ifnot(Inh[u])then//不在堆里 begin inc(size); heap[size]:u; dis[u]:cost[e]; Loc[u]:size;//Loc数组记录元素在堆中的位置 Inh[u]:true; Shift_up(Loc[u]);//上浮 end else ifcost[e]dis[u]then//在堆里 begin dis[u]:cost[e]; Shift_up(Loc[u]); Shift_down(Loc[u]); end; e:pre[e]; end; visit[s]:true; whiletruedo begin u:heap[1];//步骤2 ifutthenbreak;//步骤4 visit[u]:true; heap[1]:heap[size]; dec(size); Shift_down(1); e:last[u]; whilee0do//步骤3 begin v:other[e]; ifNot(visit[v])and(dis[u]cost[e]dis[v])then//与u相邻的未被访问过的满足三角不等式的顶点 ifInh[v]then//在堆中 begin dis[v]:dis[u]cost[e]; Shift_up(Loc[v]); Shift_Down(Loc[v]); end else//不再堆中 begin inc(size); heap[size]:v; dis[v]:dis[u]cost[e]; Loc[v]:size; Inh[v]:true; Shift_up(Loc[v]); end; e:pre[e]; end; end; writeln(dis[t]); end; 参考资料 1. 最短路径 nocow[引用日期2013-08-19] 2. 最短路径—Dijkstra算法和Floyd算法 博客园[引用日期2014-11-28] 词条标签 中国电子学会 计算机学 迪杰斯特拉算法图册 V百科往期回顾 其他人还看 纠错 艾兹格·迪科斯彻 Floyd算法 SPFA算法 最短路径 A*算法 Bellman-Ford算法 贪心算法 Prim kruskal算法 权威合作编辑 “科普中国”百科科学词条编写与应用工作项目 “科普中国”是为我国科普信息化建设塑造的全... 什么是权威编辑查看编辑版本 资源提供 中国电子学会 中国电子学会Chinese Instit... 提供资源类型内容 什么是资源合作 词条统计 浏览次数343708次编辑次数76次历史版本最近更新2016-05-29创建者317611123 srchttp://entry.baidu.com/rp/home?typepageembeddiu2140330rsi0270rsi1175title%E8%BF%AA%E6%9D%B0%E6%96%AF%E7%89%B9%E6%8B%89%E7%AE%97%E6%B3%95_%E7%99%BE%E5%BA%A6%E7%99%BE%E7%A7%91ltuhttp%3A%2F%2Fbaike.baidu.com%2Flink%3Furl%3DNr56Guiec9n-ZTMXxA9SUVGiKQOhTMRdNM16VkCjEGvhj17gHdpOl4eP1Kf6vWVfq6xUC_7rYrMqNN7gpUnT5ZNA8LJiM7gkMLVBzt7GW9rsdzVulvyazVfX22LmcKwwKjio4YPTUtf0T0nDbWp2Z7pf3EitqAWEWWwpfkBUjdOrefhttps%3A%2F%2Fwww.baidu.com%2Flink%3Furl%3DNr56Guiec9n-ZTMXxA9SUVGiKQOhTMRdNM16VkCjEGvhj17gHdpOl4eP1Kf6vWVfq6xUC_7rYrMqNN7gpUnT5ZNA8LJiM7gkMLVBzt7GW9rsdzVulvyazVfX22LmcKwwKjio4YPTUtf0T0nDbWp2Z7pf3EitqAWEWWwpfkBUjdO%26wd%3D%26eqid%3Dd61a7a7d000011640000000457ebb3a9pageWidth1169pageHeight827t1475064805210iframeWidth1169iframeHeight827 aligncenter,center marginwidth0 marginheight0 classBAIDU_SS_HHIFRAME scrollingno frameborder0 allowtransparencytrue styledisplay: block; width: 270px; height: 175px; background-color: transparent;idiframeu1997633_0 srchttp://pos.baidu.com/xcgm?rdid1997633dc2diu1997633dri0dis0dai1ps0x0coawn%3D2%26hn%3D8dcbBAIDU_SSP_definedtmHTML_POSTdvi0.0dci-1dptnonetsr0tpr1475064805031ti%E8%BF%AA%E6%9D%B0%E6%96%AF%E7%89%B9%E6%8B%89%E7%AE%97%E6%B3%95_%E7%99%BE%E5%BA%A6%E7%99%BE%E7%A7%91ari2dbv2drs3pcs1169x827pss1169x9068cfv18cpl6chi1ccetruececUTF-8tlm1475064805rw827ltuhttp%3A%2F%2Fbaike.baidu.com%2Flink%3Furl%3DNr56Guiec9n-ZTMXxA9SUVGiKQOhTMRdNM16VkCjEGvhj17gHdpOl4eP1Kf6vWVfq6xUC_7rYrMqNN7gpUnT5ZNA8LJiM7gkMLVBzt7GW9rsdzVulvyazVfX22LmcKwwKjio4YPTUtf0T0nDbWp2Z7pf3EitqAWEWWwpfkBUjdOltrhttps%3A%2F%2Fwww.baidu.com%2Flink%3Furl%3DNr56Guiec9n-ZTMXxA9SUVGiKQOhTMRdNM16VkCjEGvhj17gHdpOl4eP1Kf6vWVfq6xUC_7rYrMqNN7gpUnT5ZNA8LJiM7gkMLVBzt7GW9rsdzVulvyazVfX22LmcKwwKjio4YPTUtf0T0nDbWp2Z7pf3EitqAWEWWwpfkBUjdO%26wd%3D%26eqid%3Dd61a7a7d000011640000000457ebb3a9ecd1psr1440x900par1375x876pis-1x-1ccd24cjatruecmi8colzh-CNcdo-1tcn1475064805qndd41c9ba3c55a69ett1475064804993.43.440.445 width250 height250 aligncenter,center vspace0 hspace0 marginwidth0 marginheight0 scrollingno frameborder0 allowtransparencytrue styledisplay: block; border-width: 0px; border-style: initial; vertical-align: bottom; margin: 0px; 猜你喜欢 计算机技术学校排名 计算机专业高校排名 计算机专业院校排名 广州本田飞度 广本飞度 本田汽车飞度 平面设计培训机构 北大青鸟怎么样 迪杰斯特拉 c语言基础培训课程 idiframe1120393_0 srchttp://pos.baidu.com/xcgm?mpdi203980rtbid1969725rdid9223372032564609772dc2di1120393dri0dis0dai2ps8799x104dcbBAIDU_SSP_definedtmHTML_POSTdvi0.0dci-1dptnonetsr0tpr1475064805031ti%E8%BF%AA%E6%9D%B0%E6%96%AF%E7%89%B9%E6%8B%89%E7%AE%97%E6%B3%95_%E7%99%BE%E5%BA%A6%E7%99%BE%E7%A7%91ari2dbv2drs3pcs1169x827pss1169x9068cfv18cpl6chi1ccetruececUTF-8tlm1475064805rw827ltuhttp%3A%2F%2Fbaike.baidu.com%2Flink%3Furl%3DNr56Guiec9n-ZTMXxA9SUVGiKQOhTMRdNM16VkCjEGvhj17gHdpOl4eP1Kf6vWVfq6xUC_7rYrMqNN7gpUnT5ZNA8LJiM7gkMLVBzt7GW9rsdzVulvyazVfX22LmcKwwKjio4YPTUtf0T0nDbWp2Z7pf3EitqAWEWWwpfkBUjdOltrhttps%3A%2F%2Fwww.baidu.com%2Flink%3Furl%3DNr56Guiec9n-ZTMXxA9SUVGiKQOhTMRdNM16VkCjEGvhj17gHdpOl4eP1Kf6vWVfq6xUC_7rYrMqNN7gpUnT5ZNA8LJiM7gkMLVBzt7GW9rsdzVulvyazVfX22LmcKwwKjio4YPTUtf0T0nDbWp2Z7pf3EitqAWEWWwpfkBUjdO%26wd%3D%26eqid%3Dd61a7a7d000011640000000457ebb3a9ecd1psr1440x900par1375x876pis-1x-1ccd24cjatruecmi8colzh-CNcdo-1tcn1475064805qn4fe6bf408add6e71dpv4fe6bf408add6e71tt1475064804993.103.452.453 width960 height90 aligncenter,center vspace0 hspace0 marginwidth0 marginheight0 scrollingno frameborder0 allowtransparencytrue styledisplay: block; border-width: 0px; border-style: initial; vertical-align: bottom; margin: 0px; 新手上路 成长任务 编辑入门 编辑规则 百科术语 我有疑问 我要质疑 我要提问 参加讨论 意见反馈 投诉建议 举报不良信息 未通过词条申诉 投诉侵权信息 封禁查询与解封 ©2016Baidu 使用百度前必读 | 百科协议 | 百度百科合作平台 登录 分享
