彻底弄懂最短路径问题
————————————————————————————————作者: ————————————————————————————————日期:
彻底弄懂最短路径问题
只想说:温故而知新,可以为师矣。我大二的《数据结构》是由申老师讲的,那时候不怎么明白,估计太理论化了(ｐs：或许是因为我睡觉了);今天把老王的2011年课件又看了一遍,给大二的孩子们又讲了一遍,随手谷歌了N多资料，算是彻底搞懂了最短路径问题。请读者尽情享用……
我坚信:没有不好的学生，只有垃圾的教育。不过没有人理所当然的对你好，所以要学会感恩。
一.问题引入
问题：从某顶点出发,沿图的边到达另一顶点所经过的路径中，各边上权值
之和最小的一条路径——最短路径。解决最短路的问题有以下算法，Dｉｊkstra 算法，Bellman-Fｏrd算法,Ｆlｏyd算法和ＳＰFＡ算法，另外还有著名的启发式搜索算法A*，不过Ａ*准备单独出一篇，其中Floyd算法可以求解任意两点间的最短路径的长度。笔者认为任意一个最短路算法都是基于这样一个事实：从任意节点Ａ到任意节点B的最短路径不外乎2种可能，1是直接从Ａ到Ｂ,２是从A 经过若干个节点到B。
二.Dijkｓtrａ算法
该算法在《数据结构》课本里是以贪心的形式讲解的,不过在《运筹学》教
材里被编排在动态规划章节,建议读者两篇都看看。
观察右边表格发现除最后一个节点外其他均已经求出最短路径。
(1) 迪杰斯特拉（Ｄiｊkstra）算法按路径长度（看下面表格的最后一行,就是next点)递增次序产生最短路径。先把Ｖ分成两组：
?S:已求出最短路径的顶点的集合
?Ｖ-S＝T:尚未确定最短路径的顶点集合
将T中顶点按最短路径递增的次序加入到Ｓ中，依据:可以证明V0到T中顶点Vk的最短路径,或是从V0到Vk的直接路径的权值或是从V０经S中顶点到Vk的路径权值之和（反证法可证，说实话，真不明白哦)。
（２) 求最短路径步骤
1.初使时令S＝｛V0},T=｛其余顶点}，
T中顶点对应的距离值, 若存在
ＰＦA初始化方式不同)，若不存在<
Ｖ０,Vi>，为Inf。
2.从T中选取一个其距离值为最小的
顶点W(贪心体现在此处),加入S(注意不是直接从S集合中选取，理解这个对于理解vis数组的作用至关重要),
对T中顶点的距离值进行修改:若加
进Ｗ作中间顶点,从Ｖ0到Vi的距离
值比不加W的路径要短，则修改此
距离值(上面两个并列fｏｒ循环,使
用最小点更新）。
3.重复上述步骤，直到Ｓ中包含所有顶
点,即S=V为止(说明最外层是除起点外的遍历)。
下面是上图的求解过程，按列来看,第一列是初始化过程，最后一行是每次求得的neｘt点。
（3) 问题：Dｉjkｓtaｒ能否处理负权边?(来自《图论》）
答案是不能，这与贪心选择性质有关(pｓ：貌似还是动态规划啊，晕了）,每次都找一个距源点最近的点（dｍin）,然后将该距离定为这个点到源点的最短路径；但如果存在负权边,那就有可能先通过并不是距源点最近的一个次优点
（dmin＇)，再通过这个负权边L(L<0），使得路径之和更小（dmin＇+L 则dｍin＇+L成为最短路径，并不是dmi ｎ,这样dｉjkstra就被囧掉了。比如ｎ=3，邻接矩阵： 0，3,4 3，０，-２?4，-2,0,用dijksｔra求得d[１,2]＝3，事实上ｄ［1,２]=２,就是通过了１-３-2使得路径减小。不知道讲得清楚不清楚。 二.Flｏyd算法 参考了南阳理工牛帅（目前在新浪)的博客。 Floyd算法的基本思想如下:从任意节点A到任意节点B的最短路径不外乎 ２种可能,１是直接从A到B,２是从Ａ经过若干个节点到B,所以,我们假设dｉ st(AB)为节点Ａ到节点B的最短路径的距离,对于每一个节点K，我们检查ｄist(AK) + dist(KB）＜diｓt(AB)是否成立,如果成立,证明从Ａ到K再到B的路径比A直接到B的路径短,我们便设置dist(AB) = diｓt（AK) + dist(KＢ),这样一来,当我们遍历完所有节点Ｋ,ｄist（AB)中记录的便是Ａ到B的最短路径的距离。 很简单吧,代码看起来可能像下面这样: ｆor (inｔｉ=０; i for (ｉnt j＝0; ｊ＜n; +＋j) ｛ fｏr（int k=0；ｋ＜n; ＋+k) ｛ if（disｔ[ｉ][k］＋dist［k][ｊ] ＜ｄiｓt［i][j] ) ｛ dist[ｉ]［j］ = ｄist［i]［k] + dist［k][j］; } } } } 但是这里我们要注意循环的嵌套顺序,如果把检查所有节点Ｋ放在最内层,那么结果将是不正确的,为什么呢？因为这样便过早的把ｉ到ｊ的最短路径确定下来了,而当后面存在更短的路径时，已经不再会更新了。 让我们来看一个例子，看下图： 图中红色的数字代表边的权重。如果我们在最内层检查所有节点K,那么对 于A->Ｂ,我们只能发现一条路径，就是Ａ->B,路径距离为9，而这显然是不正确的,真实的最短路径是Ａ->D->C->B,路径距离为6。造成错误的原因就是我们把检查所有节点Ｋ放在最内层，造成过早的把A到Ｂ的最短路径确定下来了，当确定Ａ->Ｂ的最短路径时ｄist(AC)尚未被计算。所以,我们需要改写循环顺序,如下： ps：个人觉得,这和银行家算法判断安全状态（每种资源去测试所有线程),树状数组更新（更新所有相关项)一样的思想。 ｆor（int k＝０; k for(intｉ=0; i for (ｉｎt j＝0; j＜n; ++j) { /＊ 实际中为防止溢出,往往需要选判断ｄist［ｉ］［k]和dｉ st[k][j 都不是Ｉnf ，只要一个是Inｆ，那么就肯定不必更新。 ＊／ if(ｄist[i］［ｋ] ＋ｄist［ｋ］[j] < dｉst[ｉ][j］ ) { dist[ｉ][j] = dｉst[i］[k] ＋dist［k］[j]； } } } } 如果还是看不懂，那就用草稿纸模拟一遍，之后你就会豁然开朗。半个小时足矣（早知道的话会节省很多个半小时了。。） 再来看路径保存问题: voiｄｆloyd() ｛ for（ｉｎtｉ=1; ｉ<＝ｎ ; i＋+)｛ ｆor（int j=1；j＜＝n; j++){ if（ｍap[ｉ][j］==Inf){ ｐath［ｉ］[j] ＝ -1；／/表示 i －> j 不通 }else{ paｔh[ｉ][j］ = i;// 表示 i －> j 前驱为 i } ｝ ｝ for(int k＝1; ｋ<=n；k++) { for(iｎt i＝１； i＜=ｎ; i＋+）{ for(int j=1; j<=n; ｊ++） { iｆ（!（dｉｓt[i][k］=＝Ｉnf||dｉsｔ[k][j]＝＝Inf)&&ｄist[i］［j] > disｔ［i]［k］ + dist[k］[j］） { disｔ［i]［j] ＝ diｓt[ｉ]［k] + disｔ[k][ｊ］; path[i][k] = ｉ; pａth［ｉ］[ｊ] = ｐath[k］[j]; } } ｝ } } void priｎｔＰath(int frｏm, ｉnt to) ｛ /* * 这是倒序输出,若想正序可放入栈中，然后输出。 ＊ * 这样的输出为什么正确呢?个人认为用到了最优子结构性质, * 即最短路径的子路径仍然是最短路径 */ ｗｈile(path［ｆroｍ][ｔo]!=from) { Ｓystｅm.oｕt.print（path[from][to] ＋""); ｔo ＝ｐath[fｒom][ｔo]； } } 《数据结构》课本上的那种方式我现在还是不想看,看着不舒服…… Ｆloyd算法另一种理解ＤＰ,为理论爱好者准备的,上面这个形式的算法其实是Floyd算法的精简版，而真正的Fｌoyd 算法是一种基于DＰ（Dynamic Proｇra ｍminｇ)的最短路径算法。设图G中n 个顶点的编号为1到ｎ。令c [i, j，k]表示从ｉ到ｊ的最短路径的长度，其中k 表示该路径中的最大顶点,也就是 说c［i,ｊ,k]这条最短路径所通过的中间顶点最大不超过ｋ。因此,如果G中包含边＜i, j>,则ｃ[i, ｊ, 0] =边＜ｉ，j> 的长度；若i= ｊ，则c[ｉ,j,０]=０;如果G中不包含边 k-１] +c [ｋ, j, k-1]。c[i, j, k］可取两者中的最小值。状态转移方程：ｃ[ｉ, j, k]=min{c［i, ｊ，ｋ-1], c [ｉ, k, ｋ-1]+ｃ[ｋ，j, ｋ-1]},k＞0。这样,问题便具有了最优子结构性质,可以用动态规划方法来求解。 看另一个DP（直接引用王老师课件) 说了这么多，相信读者已经跃跃欲试了，咱们看一道例题，以ＺOJ 1092 为例:给你一组国家和国家间的部分货币汇率兑换表,问你是否存在一种方式，从一种货币出发，经过一系列的货币兑换,最后返回该货币时大于出发时的数值(ps:这就是所谓的投机倒把吧)，下面是一组输入。?３//国家数 USDollar //国家名 BrｉtiｓhＰound FreｎchFranc ?３//货币兑换 数?ＵSDoｌlａr 0.5 BrｉｔisｈPo ｕnd //部分货币汇率兑换表?BrｉｔｉshＰｏｕnd １0．０ＦrenｃhFranc ＦrｅｎchＦrａnc ０.21 USDｏllａr 月赛做的题,不过当时用的思路是 求强连通分量(ｐs：明明说的,那时我和华杰感觉好有道理)，也没做出来，现在知道了直接ｆlｏyd算法就ok了。 思路分析:输入的时候可以采用Ma ｐ 为了能够求解边上带有负值的单源最短路径问题，Ｂｅｌｌman(贝尔曼，动态规划提出者)和Fｏrd(福特)提出了从源点逐次绕过其他顶点,以缩短到达终点的最短路径长度的方法。 Bｅｌｌmａn－ford算法是求含负权图的单源最短路径算法，效率很低，但代码很容易写。即进行不停地松弛,每次松弛把每条边都更新一下，若n-1次松弛后还能更新,则说明图中有负环，无法得出结果,否则就成功完成。Bellmaｎ-ford算法有一个小优化:每次松弛先设一个ｆlag，初值为FALSE,若有边更新则赋值为TRUＥ,最终如果还是FALSE则直接成功退出。Bellmａn-ｆord算法浪费了许多时间做 无必要的松弛,所以ＳPＦＡ算法用队列进行了优化,效果十分显著,高效难以想象。SPＦＡ还有SLＦ,ＬLＬ,滚动数组等优化。 关于SPFA,请看我这一篇错误!未定义书签。 递推公式(求顶点u到源点ｖ的最短路径): dｉst 1 [u］= Ｅｄge[ｖ][u] dist k [u］= min{ diｓt ｋ－1 [u］, mｉn{ ｄist k-1 ［ｊ］+ Edge[ｊ]［u] } }，j=0,1,…，n-１,j≠u Diｊkstra算法和Ｂeｌｌman算法思想有很大的区别:Diｊksｔｒａ算法在求解过程中，源点到集合S内各顶点的最短路径一旦求出，则之后不变了,修 :算法的设计思想 本算法采用分支定界算法实现。构造解空间树为：第一个城市为根结点，与第一个城市相邻的城市为根节点的第一层子节点，依此类推；每个父节点的子节点均是和它相邻的城市；并且从第一个根节点到当前节点的路径上不能出现重复的城市。 本算法将具有最佳路线下界的节点作为最有希望的节点来展开解空间树，用优先队列实现。算法的流程如下：从第一个城市出发，找出和它相邻的所有城市，计算它们的路线下界和费用，若路线下界或费用不满足要求，将该节点代表的子树剪去，否则将它们保存到优先队列中，并选择具有最短路线下界的节点作为最有希望的节点，并保证路径上没有回路。当找到一个可行解时，就和以前的可行解比较，选择一个较小的解作为当前的较优解，当优先队列为空时，当前的较优解就是最优解。算法中首先用Dijkstra算法算出所有点到代表乙城市的点的最短距离。算法采用的下界一个是关于路径长度的下界，它的值为从甲城市到当前城市的路线的长度与用Dijkstra算法算出的当前城市到乙城市的最短路线长度的和；另一个是总耗费要小于1500。 伪代码 算法AlgBB() 读文件m1和m2中的数据到矩阵length和cost中 Dijkstra(length) Dijkstra(cost) while true do for i←1 to 50 do //选择和node节点相邻的城市节点 if shortestlength>optimal or mincost>1500 pruning else if i＝50 optimal=min(optimal,tmpopt)//选当前可行解和最优解的 较小值做最优解 else if looped //如果出现回路 pruning //剪枝 else 将城市i插入到优先队列中 end for while true do if 优先队列为空 输出结果 else 取优先队列中的最小节点 if 这个最小节点node的路径下界大于当前的较优解 continue 八年级数学最短路径问题 【问题概述】最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径．算法具体的形式包括： ①确定起点的最短路径问题 - 即已知起始结点，求最短路径的问题． ②确定终点的最短路径问题 - 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题． ③确定起点终点的最短路径问题 - 即已知起点和终点，求两结点之间的最短路径． ④全局最短路径问题 - 求图中所有的最短路径． 【问题原型】“将军饮马”，“造桥选址”，“费马点”． 【涉及知识】“两点之间线段最短”，“垂线段最短”，“三角形三边关系”，“轴对称”，“平移”． 【出题背景】角、三角形、菱形、矩形、正方形、梯形、圆、坐标轴、抛物线等． 【解题思路】找对称点实现“折”转“直”，近两年出现“三折线”转“直”等变式问题考查． 在直线l 上求一点P ，使PB PA -的值最大． 作直线AB ，与直线l 的交 点即为P ． 三角形任意两边之差小于 第三边．PB PA -≤AB ． PB PA -的最大值＝AB ． 【问题11】 作法 图形 原理 在直线l 上求一点P ，使PB PA -的值最大． 作B 关于l 的对称点B ＇作直线A B ＇，与l 交点即 为P ． 三角形任意两边之差小于 第三边．PB PA -≤AB ＇． PB PA -最大值＝AB ＇． 【问题12】“费马点” 作法 图形 原理 △ABC 中每一内角都小于120°，在△ABC 内求一点P ，使P A +PB +PC 值最小． 所求点为“费马点”，即满足∠APB ＝∠BPC ＝∠ APC ＝120°．以AB 、AC 为边向外作等边△ABD 、△ACE ，连CD 、BE 相交于P ，点P 即为所求． 两点之间线段最短． P A +PB +PC 最小值＝CD ． 【精品练习】 1．如图所示，正方形ABCD 的面积为12，△ABE 是等边三角形，点E 在正方形ABCD 内，在对角线AC 上有 一点P ，使PD +PE 的和最小，则这个最小值为（ ） A ．3 B ．26 C ．3 D 6 2．如图，在边长为2的菱形ABCD 中，∠ABC ＝60°，若将△ACD 绕点A 旋转，当AC ′、AD ′分别与BC 、CD 交于点E 、F ，则△CEF 的周长的最小值为（ ） A ．2 B ．32 C ．32+ D ．4 l B A l P A B l A B l B P A B' A B C P E D C B A A D E P B C 一、课程设计题目：校园最短路径问题 二、课程设计目的： 1.了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 4.训练用系统的观点和软件开发一般规进行软件开发，培养软件工作者所具备的科学工作方法和作风。 三、课程设计要求： 1.设计的题目要求达到一定的工作量（300行以上代码），并具有一定的深度和难度。 2.编写出课程设计报告书，容不少于10页（代码不算）。 四、需求分析： 1、问题描述 图的最短路径问题是指从指定的某一点v开始，求得从该地点到图中其它各地点的最短路径，并且给出求得的最短路径的长度及途径的地点。除了完成最短路径的求解外，还能对该图进行修改，如顶点以及边的增删、边上权值的修改等。 校园最短路径问题中的数据元素有： a) 顶点数 b) 边数 c) 边的长度 2、功能需求 要求完成以下功能： a)输出顶点信息：将校园各位置输出。 b)输出边的信息：将校园每两个位置（若两个位置之间有直接路径）的距 离输出。 c)修改：修改两个位置（若两个位置之间有直接路径）的距离，并重新输 出每两个位置（若两个位置之间有直接路径）的距离。 d)求最短路径：输出给定两点之间的最短路径的长度及途径的地点或输出 任意一点与其它各点的最短路径。 e)删除：删除任意一条边。 f)插入：插入任意一条边。 3、实现要点 a) 对图的创建采用邻接矩阵的存储结构，而且对图的操作设计成了模板类。 为了便于处理，对于图中的每一个顶点和每一条边都设置了初值。 b) 为了便于访问，用户可以先输出所有的地点和距离。 c) 用户可以随意修改两点之间好的距离。 d) 用户可以增加及删除边。 e) 当用户操作错误时，系统会出现出错提示。 五、概要设计: 最短路径算法—D i j k s t r a 总结 -标准化文件发布号：（9556-EUATWK-MWUB-WUNN-INNUL-DDQTY-KII Dijkstra 算法解释 本文引用三篇文章：分别是谢光新-Dijkstra 算法， zx770424 -Dijkstra 算法， 中华儿女英雄 -Dijkstra 算法 有兴趣的朋友请引用原文，由于分类很不相同难以查找，此处仅作汇总。 谢光新的文章浅显易懂，无需深入的数学功力，每一步都有图示，很适合初学者了解。 zx770424将每一步过程，都用图示方式和公式代码\伪代码对应也有助于，代码的理解。 中华儿女英雄从大面上总结了Dijkstra 的思想，并将演路图描叙出来了。起到总结的效果。 希望这篇汇总有助于大家对Dijkstra 算法的理解。 Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。 简介 Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。 算法描述 (这里描述的是从节点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)=min{d(i),i属于S}，令S=S-{j}，若S为空集则算法结束，否则转3 3．对全部i属于S,如果存在边j->i，那么置d(i)=min{d(i), d(j)+Wj->i}，转2 Dijkstra算法思想为：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。 算法具体步骤 （1）初始时，S只包含源点，即S=，v的距离为0。U包含除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 算法的时间复杂度为O(n^2) 空间复杂度取决于存储方式，邻接矩阵为O(n^2) 摘要 现实生活中许多实际问题的解决依赖于最短路径的应用，其中比较常用的是floyd 算法。通过floyd算法使最短路径问题变得简单化。采用图的邻接矩阵或邻接表实现最短路径问题中图的存储。采用Visual C++6.0的控制台工程和MFC工程分别实现基于floyd算法求最短路径的应用。 关键词：最短路径；floyd算法；邻接矩阵；MFC工程 目录 1需求分析 (1) 2算法基本原理 (1) 2.1邻接矩阵 (1) 2.2弗洛伊德算法 (2) 3类设计 (2) 3.1类的概述 (2) 3.2类的接口设计 (3) 3.3类的实现 (4) 4基于控制台的应用程序 (7) 4.1主函数设计 (7) 4.2运行结果及分析 (8) 5基于MFC的应用程序 (9) 5.1图形界面设计 (9) 5.1程序代码设计 (11) 5.3运行结果及分析 (20) 结论 (21) 参考文献 (22) 1需求分析 Floyd算法又称为插点法，是一种用于寻找给定的加权图中多源点之间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。 假若要在计算机上建立一个交通咨询系统则可以采用图的结构来表示实际的交通网络。这个资讯系统可以回答游客提出的各种问题。例如，一位旅客要从A城到B城，他希望选择一条途中中转次数最少的路线。假设图中每一站都需要换车，则这个问题反映到图上就是要找一条从顶点A到B所含边的数目最少的路径。我们只需从顶点A出发对图作广度优先搜索，一旦遇到顶点B就终止。由此所得广度优先生成树上，从根顶点A到顶点B的路径就是中转次数最少的路径，路径上A与B之间的顶点就是途径中的中转站数。但是这只是一类最简单的图的最短路径的问题。有时对于旅客来说，可能更关心的是节省交通费用；对于司机来说里程和速度则是他们感兴趣的信息。为了在图上标示有关信息可对边赋以权的值，权的值表示两城市间的距离，或图中所需时间，或交通费用等等。此时路径长度的量度就不再是路径上边的数目，而是路径上边的权值之和。边赋以权值之后再结合最短路径算法来解决这些实际问题。Floyd算法是最短路径经典算法中形式较为简单，便于理解的一种。 2算法基本原理 2.1 邻接矩阵 邻接矩阵（Adjacency Matrix）：是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V={v1,v2,…,vn}。G的邻接矩阵是一个具有下列性质的n阶方阵：（1）对无向图而言，邻接矩阵一定是对称的，而且对角线一定为零（在此仅讨论无向简单图），有向图则不一定如此。 （2）在无向图中，任一顶点i的度为第i列所有元素的和，在有向图中顶点i的出度为第i行所有元素的和，而入度为第i列所有元素的和。 （3）用邻接矩阵法表示图共需要个空间，由于无向图的邻接矩阵一定具有对称关系，所以扣除对角线为零外，仅需要存储上三角形或下三角形的数据即可，因此仅需 初二最短路径问题归纳 Document serial number【UU89WT-UU98YT-UU8CB-UUUT-UUT108】 最短路径问题专题学习【基本问题】 m n 在直线l 上求一点P ，使PB PA -的值最小． 【问题10】 作法 图形 原理 在直线l 上求一点P ，使PB PA -的值最大． 作B 关于l 的对称点B ＇作直线A B ＇，与l 交点即为 P ． 三角形任意两边之 差小于第三边．PB PA -≤ AB ＇． PB PA -最大值＝ AB ＇． 【精品练习】 1．如图所示，正方形ABCD 的面积为12，△ABE 是等边三角形，点E 在正方形ABCD 内，在对角线AC 上有一点P ，使PD +PE 的和最小，则这个最小值为（ ） A ．23．6 C ．3 D 6 2．如图，在边长为2的菱形ABCD 中，∠ABC ＝60°，若将△ACD 绕点A 旋转，当 AC ′、AD ′分别与BC 、CD 交于点E 、F ，则△CEF 的周长的最小值为（ ） A ．2 B ．32 C ．32+ D ．4 3．四边形ABCD 中，∠B ＝∠D ＝90°，∠C ＝70°，在BC 、CD 上分别找一点M 、N ，使△AMN 的周长最小 时，∠AMN +∠ANM 的度数为（ ） l A B D E A B C A D E P B C D A M A B M N 第2题 第3题 第4 A ．120 ° B ．130° C ．110° D ．140° 4．如图，在锐角△ABC 中，AB ＝4 2 ，∠BAC ＝45°，∠BAC 的平分线交BC 于点D ， M 、N 分别是AD 和AB 上的动点，则BM +MN 的最小值是 ． 5．如图，Rt △ABC 中，∠C ＝90°，∠B ＝30°，AB ＝6，点E 在AB 边上，点D 在BC 边上（不与点B 、C 重 合），且ED ＝AE ，则线段AE 的取值范围是 ． 6．如图，∠AOB ＝30°，点M 、N 分别在边OA 、OB 上，且OM ＝1，ON ＝3，点P 、Q 分 别在边OB 、OA 上，则MP ＋PQ ＋QN 的最小值是_________． 7．如图，三角形△ABC 中，∠OAB ＝∠AOB ＝15°，点B 在x 轴的正半轴，坐标为 B (36，0)． OC 平分∠AOB ，点M 在OC 的延长线上，点N 为边OA 上的点，则MA ＋MN 的最小值 是______． 8．已知A （2，4）、B （4，2）．C 在y 轴上，D 在x 轴上，则四边形ABCD 的周长最 小值为 ， 此时 C 、D 两点的坐标分别为 ． 9．已知A （1，1）、B （4，2）． y x B O A y x B A O 第6题 第 第36卷第5期2002年9月 浙 江 大 学 学 报(工学版) Jo ur nal o f Zhejiang U niv ersity(Eng ineer ing Science) Vol.36No.5Sep.2002 收稿日期:2001-10-24. 作者简介:柴登峰(1974-),男,浙江江山人,博士生,从事遥感图像处理、地理信息系统方面研究.E-mail:chaidf@z https://www.doczj.com/doc/ff1164319.html, 前N 条最短路径问题的算法及应用 柴登峰,张登荣 (浙江大学空间信息技术研究所,杭州浙江310027) 摘 要:现有最短路径问题指的是狭义最短路径问题,针对该问题而设计的算法只能求得最短的一条路径.前N 条最短路径拓宽了最短路径问题的内涵(即不仅要求得最短路径,还要求得次短、再次短…第N 短路径),是广义最短路径问题.在图论理论基础上分析问题之后,设计了一个递归调用Dijkstr a 算法的新算法,该算法可以求取前N 条最短路径,而且时间、空间复杂度都为多项式阶.该算法已经成功应用于一个交通咨询系统中,自然满足实时应用需要. 关键词:最短路径;N 条最短路径;网络分析;地理信息系统;交通咨询系统 中图分类号:P 208;O 22 文献标识码:A 文章编号:1008-973X (2002)05-0531-04 Algorithm and its application to N shortest paths problem CHAI Deng-f eng,ZHAN G Deng-rong (I nstitute of Sp ace and I n f ormation T echnical ,Zhej iang U niv er sity ,H angz hou 310027,China ) Abstract :As the shor test path denotes one path ,algorithms designed for shor test path problem can g et only one path .N shortest paths are N paths including the shortest one ,the one inferior to the shortest one,eto.After reviewing the application of shortest poth pro blem ,an N shortest paths problem w as put fo rw ard and described.Gr aph theo ry w as used to analy ze the problem and results in fo ur theoretical con-clusions .T hen ,algo rithm recursively calling the Dijkstra algor ithm was desig ned and analy zed .Bath time co nplexity and space conplex ity are poly nom ial order.The algo rithm w as tested by ex periment and applied to a traffic consultatio n system of Guang zhou City ,it can meet the need of r eal-time application.Key words :sho rtest path;N shor test paths;netw ork analysis;tr affic consultation system ;GIS 20世纪中后期,随着计算机的出现和发展,图论的理论和应用研究得到广泛重视,图论作为一个数学分支的地位真正得到了确立.现在,图论的应用已经深入到众多领域,GIS 网络分析就是图论在地理信息领域的重要应用[3] ,此外,还有城市规划、电子导航、交通咨询等等. 最短路径问题是图论中的一个典范问题[1],主要研究成果有Dijkstra 、Floy d 等优秀算法[1,2],Dijk-stra 还被认为是图论中的好算法[1] .目前的研究工作主要集中于算法实现的优化改进与应用方面[3,4].最短路径问题通常有两类[2]:一类是求取从某一源点到其余各点的最短路径;另一类是求取每一对顶 点之间的最短路径.它们从不同的角度描述问题,但有一个共同的缺陷:这里的最短路径指两点之间最 短的那一条路径,不包括次短、再次短等等路径.在此不妨称以上两类问题为狭义最短路径问题,为此设计的算法只能求得最短的一条路径,而不能得到次短、再次短等等路径. 实际上,用户在使用咨询系统或决策支持系统时,希望得到最优的决策参考外,还希望得到次优、再次优等决策参考,这同样反映在最短路径问题上.因此,有必要将最短路径问题予以扩充,成为N 条最短路径问题,即不但要求得到最短路径,还要得到次短、再次短等路径.这称之为广义最短路径问题. 中南大学 《数据结构》课程设计 题目第9题 Dijkstra算法求最短路径 学生姓名 XXXX 指导教师 XXXX 学院信息科学与工程学院 专业班级 XXXXXXX 完成时间 XXXXXXX 目录 第一章问题分析与任务定义---------------------------------------------------------------------3 1.1 课程设计题目-----------------------------------------------------------------------------3 1.2 原始数据的输入格式--------------------------------------------------------------------3 1.3 实现功能-----------------------------------------------------------------------------------3 1.4 测试用例-----------------------------------------------------------------------------------3 1.5 问题分析-----------------------------------------------------------------------------------3 第二章数据结构的选择和概要设计------------------------------------------------------------4 2.1 数据结构的选择--------------------------------------------------------------------------4 2.2 概要设计-----------------------------------------------------------------------------------4 第三章详细设计与编码-----------------------------------------------------------------------------6 3.1 框架的建立---------------------------------------------------------------------------------6 3.2 点结构体的定义---------------------------------------------------------------------------7 3.3 创立带权值有向图------------------------------------------------------------------------8 3.4 邻接矩阵的显示---------------------------------------------------------------------------9 3.5 递归函数的应用---------------------------------------------------------------------------10 3.6 Dijkstra算法实现最短路径--------------------------------------------------------------10 第四章上机调试------------------------------------------------------------------------------------11 4.1 记录调试过程中错误和问题的处理---------------------------------------------------11 4.2 算法的时间课空间性能分析------------------------------------------------------------11 4.3 算法的设计、调试经验和体会---------------------------------------------------------11 第五章测试结果-----------------------------------------------------------------------------------12 第六章学习心得体会-----------------------------------------------------------------------------12 第七章参考文献-----------------------------------------------------------------------------------12 附录------------------------------------------------------------------------------------------------------12 13.4 课题学习最短路径问题 一、教学设计理念 最短路径问题在现实生活中经常遇到，初中阶段主要以“两点之间线段最短”、“连接 直线外一点与直线上各点的所有线段中，垂线段最短”为知识基础，有时还要借助轴对称、 平移、旋转等变化进行研究。 本节课以数学史中的两个经典问题——“将军饮马”“造桥选址”为载体展开对“最短 路径问题”的课题研究，让学生经历将实际问题转化为数学问题，利用轴对称、平移等变化再把数学问题转化为线段和最小问题，并运用“两点之间线段最短”（或“三角形两边之和大于第三边”）解决问题，体现了数学化的过程和转化思想。 最短路径问题从本质上说是最值问题，作为初中生，此前很少在几何中接触最值问题， 解决此类问题的数学经验尚显不足，特别是面对具有实际背景的最值问题，更会感到陌生， 无从下手．解答“当点A、B 在直线l 的同侧时，如何在直线l 上找到点C，使AC 与CB 的和最小”，需要将其转化为“在直线l 异侧两点的线段和最小值问题”，为什么需要这样 转化、怎样通过轴对称、平移变化实现转化，一些学生在理解和操作上存在困难．在证明 作法的合理性时，需要在直线上任取点(与所求作的点不重合)，证明所连线段和大于所求作的线段和，这种思路、方法，一些学生想不到．所以在课堂上特别对这几个问题进行了针对 性的设计。 二、教学对象分析 八年级的学生已经学习研究过一些“两点之间，线段最短”、“垂线段最短”等问题。 一直以来，学生对多媒体环境下的几何探究都十分感兴趣，有较强的好奇心，在学习上有较强的求知欲望，学习投入程度大。他们观察、操作、猜想能力较强，但演绎推理、归纳、运 用数学意识的思想比较薄弱，思维的广阔性、敏捷性、灵活性比较欠缺，自主探究和合作学 习能力也需要在课堂教学中进一步加强和引导。学生在数学问题的提出和解决上有一定的方法，但不够深入和全面，需要教师的引导和帮助，学生本身具有一定的探究精神和合作意识，能在亲身的经历体验中获取一定的数学新知识，但在数学的说理上还不规范，几何演绎推理能力有待加强。(1)最短路径问题从本质上说是最值问题，作为初中生，此前很少在几何中 接触最值问题，解决此类问题的数学经验尚显不足，特别是面对具有实际背景的最值问题， 更会感到陌生，无从下手。(2)解答“当点 A 、B 在直线l 的同侧时，如何在直线l 上找到点C，使AC 与CB 的和最小”，需要将其转化为“在直线l 异侧两点的线段和最小值问题”，为什么需要这样转化、怎样通过轴对称、平移变化实现转化，一些学生在理解和操作上存 在困难。(3)在证明作法的合理性时，需要在直线上任取点(与所求作的点不重合)。证明所连线段和大于所求作的线段和，这种思路、方法，一些学生会想不到。 三、教学目标 1、了解解决最短路径问题的基本策略和基本原理。 2、能将实际问题中的“地点”“河”“桥”等抽象为数学中的“点”“线”，使实际 问题数学化。 3、能运用轴对称、平移变化解决简单的最短路径问题，体会几何变化在解决最值问题中 的重要作用。 4、在探索最短路径的过程中，感悟、运用转化思想。进一步培养好奇心和探究心理，更 进一步体会到数学知识在生活中的应用。 四，教学重点 地图中最短路径的搜索算法研究 学生:李小坤导师：董峦 摘要：目前为止, 国内外大量专家学者对“最短路径问题”进行了深入的研究。本文通过理论分析, 结合实际应用，从各个方面较系统的比较广度优先搜索算法(BFS)、深度优先搜索算法(DFS)、A* 算法的优缺点。 关键词:最短路径算法；广度优先算法；深度优先算法；A*算法； The shortest path of map's search algorithm Abstract:So far, a large number of domestic and foreign experts and scholars on the" shortest path problem" in-depth study. In this paper, through theoretical analysis and practical application, comprise with the breadth-first search algorithm ( BFS ), depth-first search algorithm ( DFS ) and the A * algorithms from any aspects of systematic. Key words: shortest path algorithm; breadth-first algorithm; algorithm; A * algorithm; 前言： 最短路径问题是地理信息系统（GIS）网络分析的重要内容之一，而且在图论中也有着重要的意义。实际生活中许多问题都与“最短路径问题”有关, 比如: 网络路由选择, 集成电路设计、布线问题、电子导航、交通旅游等。本文应用深度优先算法，广度优先算法和A*算法，对一具体问题进行讨论和分析，比较三种算的的优缺点。 在地图中最短路径的搜索算法研究中，每种算法的优劣的比较原则主要遵循以下三点:[1] (1)算法的完全性：提出一个问题，该问题存在答案，该算法能够保证找到相应的答案。算法的完全性强是算法性能优秀的指标之一。 (2)算法的时间复杂性: 提出一个问题，该算法需要多长时间可以找到相应的答案。算法速度的快慢是算法优劣的重要体现。 (3)算法的空间复杂性:算法在执行搜索问题答案的同时，需要多少存储空间。算法占用资源越少，算法的性能越好。 地图中最短路径的搜索算法: 1、广度优先算法 广度优先算法(Breadth-First-Search)，又称作宽度优先搜索，或横向优先搜索，是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型,Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽 最短路径问题的算法分析及建模案例 最短路径问题的算法分析及建模案例 一.摘要 (3) 二.网络最短路径问题的基础知识 (5) 2.1有向图 (7) 2.2连通性................... 错误！未定义书签。 2.3割集....................... 错误！未定义书签。 2.4最短路问题 (8) 三．最短路径的算法研究.. 错误！未定义书签。 3.1最短路问题的提出 (9) 3.2 Bellman最短路方程错误！未定义书签。 3.3 Bellman-Ford算法的基本思想错误！未定义书签 3.4 Bellman-Ford算法的步骤错误！未定义书签。 3.5实例....................... 错误！未定义书签。 3.6 Bellman-FORD算法的建模应用举例错误！未定义 3.7 Dijkstra算法的基本思想 (9) 3.8 Dijkstra算法的理论依据 (9) 3.9 Dijkstra算法的计算步骤 (9) 3.10 Dijstre算法的建模应用举例 (10) 3.11 两种算法的分析错误！未定义书签。 1.Diklstra算法和Bellman-Ford算法 思想有很大的区别错误！未定义书签。 Bellman-Ford算法在求解过程中，每 次循环都要修改所有顶点的权值，也就 是说源点到各顶点最短路径长度一直 要到Bellman-Ford算法结束才确定下 来。...................... 错误！未定义书签。 2.Diklstra算法和Bellman-Ford算法 的限制.................. 错误！未定义书签。 3.Bellman-Ford算法的另外一种理解错误！未定 4.Bellman-Ford算法的改进错误！未定义书签。 摘要 近年来计算机发展迅猛，图论的研究也得到了很大程度的发展，而最短路径 问题一直是图论中的一个典型问题，它已应用在地理信息科学，计算机科学等 诸多领域。而在交通路网中两个城市之间的最短行车路线就是最短路径问题的 一个典型例子。 由于最短路径问题在各方面广泛应用，以及研究人员对最短路径的深入研究， 使得在最短路径问题中也产生了很多经典的算法。在本课题中我将提出一些最 短路径问题的算法以及各算法之间的比较，最后将这些算法再应用于实际问题 最短路径问题探究 一、教材分析与学情分析 1．教材分析 （1）教学内容 《最短路径问题探究》是九年级下为让学生能灵活的运用对称、平移解决近几年中考中常见的最短路径问题而设置的一节专题课． 初中三年，孩子们也具备了一定的学习能力，在老师的指导下，能针对某一问题展开讨论并归纳总结．但受年龄特征的影响，他们知识迁移能力不强，自主探究能力较差，不善于思考。所以本节课设计为通过对最短路径问题探究，在于引导学生学会思考，帮助学生掌握良好的学习方法为一节学法指导课 （2）地位和作用 近几年各地中考均有最短路径问题的考试，为让学生能熟练解决该类问题，本节课在已有平移、对称知识的基础上，引导学生探究如何运用平移、对称解决最短路径问题。它既是平移、对称知识运用的延续，又能培养学生自主探究，学会思考，在知识与能力转化上起到桥梁作用. 2．学情分析 （1）已有基础知识与生活经验分析 学生已掌握对称、平移、勾股定理等知识，但综合运用能力还较差。加之来自社会、家长和老师的压力较大，学生学的辛苦．对于学习方法不好的同学来说，感觉疲惫，无法体验学习的乐趣；从平时教学反映出学生不重视学习方法，不注意归纳总结，不会思考，更不善于思考，学生学得累。所以想通过本节课引导学生学会学习，学会思考，从而使其感受到学习的快乐，提高学习的兴趣，避免死做题，读死书，以达到提高学习能力的目的. （2）学生起点能力分析 学生已学过一些关于空间与图形的简单推理知识，具备了一定的合情推理能力，能应用勾股定理、线段公理等知识解决简单的问题，但演绎推理的意识和能力还有待加强，思维缺乏灵活性．综合运用能力较差，学习死，不能做到学习与研究相结合. 二、教学目标： 依据新课程标准的理念和学生实际情况，制定如下教学目标： ●知识与技能目标 1、结合具体实例，能灵活的运用勾股定理、线段公理解决实际问题 2、学会思考，逐步提高思维技能和思维的有效性，初步学会探究问题 ●方法与过程目标 1、经历问题的探究，学会从中提取有用信息，善于思考，善于提问，善于归纳总结，培养良好思维习惯． 2、经历运用已有的生活经验，已有的数学知识，培养思维能力、推理能力和有条理的表达能力 ●情感与态度目标 数据结构课程设计题目 2012-1 1、医务室模拟。（5人） 问题描述：假设只有一位医生，在一段时间内随机地来几位病人；假设病人到达的时间间隔为0~14分钟之间的某个随机值，每个病人所需处理时间为1~9分钟之间的某个随机值。试用队列结构进行模拟。 实现要求：要求输出医生的总等待时间和病人的平均等待时间。 程序设计思路：计算机模拟事件处理时，程序按模拟环境中的事件出现顺序逐一处理，在本程序中体现为医生逐个为到达病人看病。当一个病人就诊完毕而下一位还未到达时，时间立即推进为下一位病人服务，中间时间为医生空闲时间。当一个病人还未结束之前，另有一位病人到达，则这些病人应依次排队，等候就诊。 2、招聘模拟（5人） 问题描述：某集团公司为发展生产向社会公开招聘m个工种的工作人员，每个工种各有不同的编号（0，1，2，…，m-1）和计划招聘人数，参加招聘的人数有n个（编号为0，1，2，。。。，n-1）。每位应聘者可以申报两个工种，并参加公司组织的考试。公司将按应聘者的成绩，从高到低的顺序排队录取。公司的录取原则是：从高分到低分依次对每位应聘者按其第一志愿录取；当不能按第一志愿录取时，便将他的成绩扣去5分后，重新排队，并按其志愿考虑录取。 程序为每个工种保留一个录取者的有序队列。录取处理循环直至招聘额满，或已对全部应聘者都做了录用处理。 实现要求：要求程序输出每个工种录用者的信息（编号、成绩），以及落选者的信息（编号、成绩）。 3、组织机构问题（5人） 问题描述：以物资学院为例，实现对我校组织结构的管理。要求把我校的组织结构以树型结构存储，实现要求： （1）树中每个结点保存部门名称； （2）假定处级部门（含院系）在树中第二层，科级部门在第三层（即最后一层），软件应该能计算出处级部门有几个，有哪几个？ （3）软件可以查询某部门下面的具体编制？ 4、最少换车次数问题（5人） 问题描述：设某城市有n个车站，并有m条公交线路连接这些车站。设这些公交车站都是单向的，这n个车站被顺序编号为0~n-1。编程序，输入该城市的公交线路数，车站个数，以及各公交线路上的各站编号。 实现要求：求得从站0出发乘公交车至站n-1的最少换车次数。 设计思路：利用输入信息构建一张有向图G（邻接矩阵存储），有向图的顶点表示车站，若某条公交线路经i站能到达j站，就在图G中存在一条有向边 课程设计任务书 目录 第1章概要设计 (1) 1.1题目的内容与要求 (1) 1.2总体结构 (1) 第2章详细设计 (2) 2.1主模块 (2) 2.2构建城市无向图 (3) 2.3添加城市 (4) 2.4修改城市距离 (5) 2.5求最短路径 (6) 第3章调试分析 (7) 3.1调试初期 (7) 3.2调试中期 (7) 3.3调试末期 (7) 第4章测试及运行结果 (7) 附页（程序清单） (10) 第1章概要设计 1.1题目的内容与要求 内容：给出一张无向图，图上的每个顶点表示一个城市，顶点间的边表示城市间存在路径，边上的权值表示城市间的距离。试编写程序求解从某一个城市出发到达任意其他任意城市的最短路径问题。 要求： 1)能够提供简单友好的用户操作界面，可以输入城市的基本信息，包括城市名 称，城市编号等； 2)利用矩阵保存城市间的距离； 3)利用Floyd算法求最短路径； 4)独立完成系统的设计，编码和调试； 5)系统利用C语言完成； 6)按照课程设计规范书写课程设计报告。 1.2总体结构 本程序主要分为四个模块（功能模块见图1.1）：主模块对整个程序起一主导作用，开始构建一城市无向图，对其进行添加城市顶点，以及对原来的距离数据进行修改，整体构建结束可以实现求一城市到其他城市的最短路径问题。 图1.1 功能模块图 第2章详细设计 2.1主模块 用户根据屏幕上显示的操作提示输入要进行操作的模块，通过调用相对应的模块程序，达到用户所想进行操作。程序的总框架大致分为四个模块：1.建立城市无向图2.添加城市模块3.修改城市距离4.求最短路径。具体实现过程见2.2：建立城市无向图2.3：添加城市2.4：修改城市距离2.5：求最短路径。流程图中通过输入n，由n的值来选择调用相对应子函数，实现所选择的功能，调用完后可以返回调用主函数进行下一次选择，从而实现反复调用子函数而实现四个模块的功能等。 图2.1 主模块流程图 最短路径问题专题学习 【精品练习】 1．如图所示，正方形ABCD 的面积为12，△ABE 是等边三角形，点E 在正方形ABCD 内，在对角线AC 上有一点P ，使PD +PE 的和最小，则这个最小值为（ ） A ．23 B ．26 C ．3 D ．6 2．如图，在边长为2的菱形ABCD 中，∠ABC ＝60°，若将△ACD 绕点A 旋转，当AC ′、AD ′分别与BC 、CD 交于点E 、F ，则△CEF 的周长的最小值为（ ） A ．2 B ．32 C ．32 D ．4 3．四边形ABCD 中，∠B ＝∠D ＝90°，∠C ＝70°，在BC 、CD 上分别找一点M 、N ，使△AMN 的周长最小 时，∠AMN +∠ANM 的度数为（ ） A ．120° B ．130° C ．110° D ．140° 4．如图，在锐角△ABC 中，AB ＝42，∠BAC ＝45°，∠BAC 的平分线交BC 于点D ，M 、N 分别是AD 和AB 上的动点，则BM +MN 的最小值是 ． 5．如图，Rt △ABC 中，∠C ＝90°，∠B ＝30°，AB ＝6，点E 在AB 边上，点D 在BC 边上（不与点B 、C 重 合），且ED ＝AE ，则线段AE 的取值范围是 ． 6．如图，∠AOB ＝30°，点M 、N 分别在边OA 、OB 上，且OM ＝1，ON ＝3，点P 、Q 分别在边OB 、OA 上，则MP ＋PQ ＋QN 的最小值是_________． D E A B C A D E P B C D A M A B M N 第2题 第3题 第4题 第5题 7．如图，三角形△ABC 中，∠OAB ＝∠AOB ＝15°，点B 在x 轴的正半轴，坐标为B (36，0)． OC 平分∠AOB ，点M 在OC 的延长线上，点N 为边OA 上的点，则MA ＋MN 的最小值是______． 8．已知A （2，4）、B （4，2）．C 在y 轴上，D 在x 轴上，则四边形ABCD 的周长最小值为 ， 此时 C 、D 两点的坐标分别为 ． 9．已知A （1，1）、B （4，2）． （1）P 为x 轴上一动点，求P A +PB 的最小值和此时P 点的坐标； （2）P 为x 轴上一动点，求PB PA 的值最大时P 点的坐标； （3）CD 为x 轴上一条动线段，D 在C 点右边且CD ＝1，求当AC +CD +DB 的最小值和此时C 点的坐标； 10．点C 为∠AOB 内一点． （1）在OA 求作点D ，OB 上求作点E ，使△CDE 的周长最小，请画出图形； （2）在（1）的条件下，若∠AOB ＝30°，OC ＝10，求△CDE 周长的最小值和此时∠DCE 的度数． 第6题 第7题最短路径流程图及算法详解
(完整版)八年级最短路径问题归纳小结
数据结构课程设计校园最短路径问题
最短路径算法—dijkstra总结
基于Floyd算法的最短路径问题的求解c++
初二最短路径问题归纳
前N条最短路径问题的算法及应用
数据结构课程设计报告Dijkstra算法求最短路径
课题学习最短路径问题.doc
地图中最短路径的搜索算法研究综述 (1)
最短路径问题的算法分析及建模案例
《最短路径问题探究》教案
数据结构课程设计题目(最终版)-2011
弗洛伊德算法求解最短路径
初二最短路径问题归纳
相关主题
文本预览