最短路径问题—Bellman-Ford算法
最短路径问题—Bellman-Ford 算法
一、算法思想
1．Dijkstra 算法的局限性
上节介绍了Dijkstra 算法，该算法要求网络中各边上得权值大于或等于0.如果有向图中存在带负权值的边，则采用Dijkstra 算法求解最短路径得到的结果有可能是错误的。
例如，对下图所示的有向图，采用Dijkstra 算法求得顶点v0到顶点v2的最短距离是dist[2]，即v0到v2的直接路径，长度为5.但从v0到v2的最短路径应该是(v0,v1,v2)，其长度为2。
(a) 有向图 (b) 邻接矩阵
(c) 初始状态
(d) 求出顶点2的最短路径 (e) 求出顶点1的最短路径 图1 有向图中存在带有负权值的边，用Dijkstra
算法求解是错误的
如果把图1(a)中的边<1,2>的权值由-5改成5
，则采用Dijkstra 算法求解最短路径，得到的结果是正确的（这里不再求解）。
为什么当有向图中存在带负权值的边时，采用Dijkstra 算法求解得到的最短路径有时是错误的？答案是：Dijkstra 算法在利用顶点u 的dist[]去递推T 集合各顶点的dist[k]值时，前提是顶点u
的dist[]值时当前T 集合中最短路径长度最小的。如果图中所有边的权值都是正的，这样推导是没有问题的。但是如果有负权值的边，这样推导是不正确的。例如，在图1(d)中，第
1次在T 集合中找到dist[]最小的是顶点2，dist[2]等于
5；但是顶点0距离顶点2的最短路径是(v0,v1,v2)，长度为2，而不是5，其中边<1,2>是一条负权值边。
2．Bellman-Ford 算法思想
为了能够求解边上带有负权值的单源最短路径问题，Bellman(贝尔曼)
和Ford(福特)提出了从源点逐次途经其他顶点，以缩短到达终点的最短路径长度的方法。该方法也有一个限制条件：要求图中不能包含权值总和为负值的回路。
例如图2(a)所示的有向图中，回路(v0,v1,v0)包括了一条具有负权值的边，且其路径长
度为-1。当选择的路径为(v0,v1,v0,v1,v0,v1,v0,v1,…)时，路径的长度会越来越小，这样顶点0到顶点2的路径长度最短可达-∞。如果存在这样的回路，则不能采用Bellman-Ford 算法求解最短路径。
如果有向图中存在由带负权值的边组成的回路，但回路权值总和非负，则不影响Bellman-Ford 算法的求解，如图2(b)所示。
0 7 5
Edge= ∞ 0 -5 ∞ ∞ 0
(a) 回路权值总和为负(b) 回路权值总和为正
图2 Bellman-Ford算法：有向图中存在负权值的边
权值总和为负值的回路我们称为负权值回路，在Bellman-Ford算法中判断有向图中是否存在负权值回路的方法，见后面。
假设有向图中有n个不存在负权值回路，从顶点v1和到顶点v25如果存在最短路径，则此路径最多有n-1条边。这是因为如果路径上得边数超过了n-1条时，必然会重复经过一个顶点，形成回路；而如果这个回路的权值总和为非负时，完全可以去掉这个回路，使得v1到v2的最短路径长度缩短。下面将以此为依据，计算从源点v0到其他每个顶点u的最短路径长度dist[u]。
Bellman-Ford算法构造一个最短路径长度数组序列：dist1[u],dist2[u],dist3[u]，…，dist n-1[u]。其中：
dist1[u]为从源点v0到终点u的只经过一条边的最短路径的长度，并有dist1[u]=edge[v0,u]。
dist2[u]为从源点v0出发最多经过不构成负权值回路的两条边到达终点u的最短路径长度。
dist3[u]为从源点v0出发最多经过不构成负权值回路的3条边到达终点u的最短路径长度。
……
dist n-1[u]为从源点v0出发最多经过不构成负权值回路的n-1条边到达终点u的最短路径长度。
算法的最终目的是计算出dist n-1[u]，为源点v0到顶点u的最短路径长度。
采用递推方式计算dist k[u]。
设已经求出dist k-1[u]，u=0,1,…,n-1，此即从源点v0最多经过不构成负权值回路的k-1条边到达终点u的最短路径的长度。
从图的邻接矩阵可以找出各个顶点j到达顶点u的(直接边)距离edge[j,u]，计算min{dist k-1[j]+edge[j,u]}，可得从源点v0途经各个顶点，最多经过不构成回路的k条边到达终点u的最短路径的长度。
比较dist k-1[u]和min{dist k-1[j]+edge[j,u]}，取较小者作为dist k[u]的值。
因此Bellman-Ford算法的递推公式（求源点v0到各顶点u的最短路径）为：
初始：dist1[u]=edge[v0,u]，v0是源点
递推：dist k[u]=min{dist k-1[u],min{dist k-1[j]+edge[j,u]}}
j=0,1,...,n-1,j<>u; k=2,3,4,...,n-1
二、算法实现
Bellman-Ford算法在实现时，需要使用以下两个数组。
(1)使用同一个数组dist[n]来存放一系列的dist k[n]，其中k=1,2,...,n-1；算法结束时dist[u]
数组中存放的是dist n-1[u]；
(2)path[n]数组含义同Dijkstra算法中的path数组。
【例题1】利用Bellman-Ford算法求解下图(a)中顶点0到其他各顶点的最短路径长度，并输出对应的最短路径。
输入：首先输入顶点个数n，然后输入每条边的数据。每条边的数据格式为：u v w，分别表示这条边的起点、终点和边上的权值。顶点序号从0开始计起。最后一行为-1 -1 -1，表示输入数据的结束。
样例输入： 样例输出： 7 1 0->3->2->1 0 1 6 3 0->3->2 0 2 5 5 0->3 0 3 5 0 0->3->2->1->4 1 4 -1 4 0->3->5 2 1 -2 3 0->3->2->1->4->6 2 4 1 3 2 -2 3 5 -1 4 6 3 5 6 3 -1 -1 -1
(a) 带负权值的有向图 (b) 邻接矩阵
(c) dist []的递推过程
图3 Bellman-Ford 算法的求解过程
【分析】
如图3(c)所示，k=1时，dist 数组各元素的值dist[u]就是edge[0,u]（见图3(b)）。在Bellman-Ford 算法执行过程中，dist 数组各元素的变化如图3(c)所示。在图3(c)中，dist[u]的值如有更新，则用粗体，红色标明，u=1,2,3,4,5,6。以k=2,u=1加以解释。求dist 2[1]的递推公式是：
dist 2[1]=min{ dist 1[1],min{ dist 1[j]+edge[j,1]}} j=0,2,3,4,5,6 所以，在程序中k=2时，dist[1]的值为：
dist[1]=min{6,min{dist[0]+edge[0,1], dist[2]+edge[2,1], dist[3]+edge[3,1], dist[4]+edge[4,1],
dist[5]+edge[5,1], dist[6]+edge[6,1]}}
=min{6,min{0+6, 5+(-2), 5+∞, ∞+∞, ∞+∞, ∞+∞}} =3
此时dist[1]的值为从源点v0出发，经过不构成负权值回路的两条边到达顶点v1的最短路
0 6 5 5 ∞ ∞ ∞ ∞ 0 ∞ ∞ -1 ∞ ∞ ∞ -2 0 ∞ 1 ∞ ∞ ∞ ∞ -2 0 ∞ -1 ∞
∞ ∞ ∞ ∞ 0 ∞ 3 ∞ ∞ ∞ ∞ ∞ 0 3 ∞ ∞ ∞ ∞ ∞ ∞ 0 edge= 在递推dist k [u]时，有更新的dist k [u]用粗体、红色标明，u=1,2,3,4,5,6
径长度，其路径为(v0,v2,v1)。
在Bellman-Ford算法执行过程中，path[n]数组的变化与Dijkstra算法类似，所以在图3中没有列出path[n]数组的变化过程。当顶点0到其他各顶点的最短路径长度求解完毕后，如果根据path数组求解顶点0到其他各顶点vk的最短路径？方法跟Dijkstra算法中的方法完全一样：从path[k]开始，采用“倒向追踪”方法，一直找到源点v0。
在下面的代码中，bellman(v0)函数实现了求源点v0到其他各顶点的最短路径。在主函数中调用bellman(0)，则求解的是从顶点0到其他各顶点的最短路径。另外，主函数中的shortest数组用来保存最短路径上各个顶点的序号，其作用和上一讲中Dijkstra程序代码中的shortest数组的作用一样。
【参考程序】
var n:longint; //顶点个数
i,j,k,u,v,w:longint;
edge:array[0..8,0..8]of longint; //邻接矩阵，这里的8为顶点个数最大值，可修改
dist,path,shortest:array[0..8]of longint; //shortest数组是输出最短路径上的各个顶点时存放各个顶点的序号
procedure bellman(v0:longint); //求顶点v0到其他顶点的最短路径
var i,j,k,u:longint;
begin
for i:=0 to n-1 do //初始化
begin
dist[i]:=edge[v0,i];
if (i<>v0)and(dist[i]<1000000) then path[i]:=v0 else path[i]:=-1;
end;
for k:=2 to n-1 do //从dist(1)[u]递推出dist(2)[u],...,dist(n-1)[u]
begin
for u:=0 to n-1 do //修改每个顶点的dist[u]和path[u]
if u<>v0 then
for j:=0 to n-1 do //考虑其他每个顶点
if (edge[j,u]<1000000)and(dist[j]+edge[j,u] begin dist[u]:=dist[j]+edge[j,u]; path[u]:=j; end; end; end; begin readln(n); //读入顶点个数 while true do begin readln(u,v,w); //读入边地起点，终点和权值 if (u=-1)and(v=-1)and(w=-1) then break; edge[u,v]:=w; //构造邻接矩阵 end; for i:=0 to n-1 do //设置邻接矩阵中其他元素的值 for j:=0 to n-1 do if i=j then edge[i,j]:=0 else if edge[i,j]=0 then edge[i,j]:=1000000; bellman(0); //求顶点0到其他顶点的最短路径 for i:=1 to n-1 do begin write(dist[i],' '); //输出顶点0到顶点i 的最短路径长度 //下面是输出顶点0到顶点i 的最短路径 fillchar(shortest,sizeof(shortest),0); k:=0; //k 表示shortest 数组中最后一个元素的下标 shortest[k]:=i; while path[shortest[k]]<>0 do begin inc(k);shortest[k]:=path[shortest[k-1]];end; inc(k);shortest[k]:=0; for j:=k downto 1 do write(shortest[j],'->'); writeln(shortest[0]); end; end. 三、关于Bellman-Ford 算法的进一步讨论 （1）本质思想 在从dist(k-1)[]递推到dist(k)[]的过程中，Bellman-Ford 算法的本质是对每条边 图4 Bellman-Ford 算法的本质思想 按照这样的思想，Bellman-Ford 算法的递推公式应该改为(求源点v0到各顶点v 的最短路径)： 初始：dist(0)[v]=∞，dist(0)[v0]=0，v0是源点，v<>v0 递推：对每条边(u,v)，dist(k)[v]=min{dist(k-1)[v],dist(k-1)[u]+w(u,v)} k=1,2,3,...,n-1 理解了这点，就能理解Bellman-Ford 算法的复杂度分析、Bellman-Ford 算法的优化等。 （2）时间复杂度分析 在例题1的Bellman-Ford 算法代码中，有一个三重嵌套的for 循环，如果使用邻接矩阵存储有向图，最内层的if 语句的总执行次数为n^3，所以算法的时间复杂度为o(n^3)。 如果使用邻接表来存储有向图，内层的两个for 循环可以改成一个while 循环，可以使算法的时间复杂度降为o(n*m)，其中n 为有向图中顶点个数，m 为边的数目。这时因为， 邻接表里直接存储了边地信息，浏览完所有的边，复杂度为o(m)。而邻接矩阵是间接存储边，浏览完所有的边，复杂度为o(n^2)。 使用邻接表存储思想实现Bellman-Ford算法的具体过程为： 将每条边的信息（两个顶点u,v和权值w，可以使用记录record来实现）存储到一个数组edges中，从dist(k-1)[]递推到dist(k)[]的过程中，对edges数组中的每条边 根据上面的分析，可以将例题1中的bellman函数简化成如下代码： procedure bellman(v0:longint); //求顶点v0到其他顶点的最短路径 var i,k:longint; begin for i:=0 to n-1 do //初始化dist数组 begin dist[i]:=1000000;path[i]:=-1; end; dist[v0]:=0; for k:=1 to n-1 do //从dist(0)[u]递推出dist(1)[u],...,dist(n-1)[u] //判断第i条边 for i:=0 to m-1 do //m为边的数目，即edges数组中元素个数 if (dist[edges[i].u]<.1000000)and(edges[i].w+dist[edges[i].u] begin dist[edges[i].v]:=edges[i].w+dist[edges[i,u]; path[edges[i].v]:=edges[i].u; end; end; 其中，dist数组各元素中，除源点v0外，其他顶点的dist[]值都初始化为∞，这样Bellman-Ford算法需要多递推一次，详见后面。 （3）Bellman-Ford算法负权值回路的判断方法 如果存在从源点可达的负权值回路，则最短路径不存在，因为可以重复走这个回路，使得路径无穷小。在Bellman-Ford算法中，判断是否存在从源点可达的负权值回路的方法如下。在求出dist(n-1)[]后，再对每条边 dist[u]+edge[u,v] 是否成立，如果成立，则说明存在从源点可达的负权值回路。代码如下： for i:=0 to n-1 do //采用邻接矩阵 for j:=0 to n-1 do if (edge[i,j]<1000000)and(dist[i]+edge[i,j] exit(1); //不存在从源点可达的负权值回路 或者： for i:=0 to m-1 do if (dist[edges[i].u]<>1000000)and(edges[i].w+dist[edges[i].u] exit(1); //不存在从源点可达的负权值回路 （4）Bellman-Ford算法中数组dist的初始值 dist数组的初始值为邻接矩阵中源点v0所在的行，实际上还可以采用以下方式对dist 数组初始化：除源点v0外，其他顶点的最短距离初始为∞（在程序实现时可以用一个权值不会达到的一个大数表示）：源点dist[v0]=0。这样Bellman-Ford算法的第1重for循环要多执行一次，即要执行n-1次；且执行第1次后，dist数组的取值为邻接矩阵中源点v0所在的行。 （5）Bellman-Ford算法的改进 Bellman-Ford算法是否一定要循环n-2次，n为顶点个数，即是否一定需要从dist(1)[u]递推到dist(n-1)[u]？ 答案是未必！其实只要在某次循环过程中，考虑每条边后，都没能改变当前源点到所有顶点的最短路径长度，那么Bellman-Ford算法就可以提前结束了。 摘要：主要介绍最短路径问题中的经典算法——迪杰斯特拉(Dijkstra)算法和弗洛伊德（Floyd）算法，以及在实际生活中的运用。 关键字：Dijkstra算法、Floyd算法、赋权图、最优路径、Matlab 目录 摘要 (1) 1引言 (1) 2最短路 (2) 2.1 最短路的定义 (2) 2.2最短路问题常见算法 (2) 3 Dijkstra算法 (2) 3.1Dijkstra算法描述 (2) 3.2 Dijkstra算法举例 (3) 3.3算法的正确性和计算复杂性 (5) 3.3.1贪心选择性质 (5) 3.3.2最优子结构性质 (6) 3.3.3 计算复杂性 (7) 4 Floyd算法 (7) 4.1Floyd算法描述 (8) 4.2 Floyd算法步骤 (11) 4.3 Floyd算法举例 (11) 5 Dijkstra算法和Floyd算法在求最短路的异同 (11) 6 利用计算机程序模拟算法 (11) 7 附录 (11) 8 论文总结 (13) 9 参考文献 (13) 1 引言 最短路问题是图论理论的一个经典问题。寻找最短路径就是在指定网络中两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。 最短路径算法的选择与实现是通道路线设计的基础,最短路径算法是计算机科学与地理信息科学等领域的研究热点,很多网络相关问题均可纳入最短路径问题的范畴之中。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。 2 最短路 2.1 最短路的定义 对最短路问题的研究早在上个世纪60年代以前就卓有成效了,其中对赋权图 的有效算法是由荷兰著名计算机专家E.W.Dijkstra 在1959年首次提出的,该算法能够解决两指定点间的最短路,也可以求解图G 中一特定点到其它各顶点的最短路。后来海斯在Dijkstra 算法的基础之上提出了海斯算法。但这两种算法都不能解决含有负权的图的最短路问题。因此由Ford 提出了Ford 算法,它能有效地解决含有负权的最短路问题。但在现实生活中,我们所遇到的问题大都不含负权,所以我们在的() 0ij w ≥的情况下选择Dijkstra 算法。 定义1若图G=G(V,E)中各边e 都赋有一个实数W(e),称为边e 的权,则称这种图为赋权图,记为G=G(V,E,W)。 定义2若图G=G(V,E)是赋权图且()0W e ≥,()e E G ∈,假设[i,j] 的权记为()i j W ，,若i 与j 之间没有边相连接，那么()i j =W ∞，。路径P 的定义为路径中各边的长度之和，记W （P ）。图G 的结点u 到结点v 距离记为d(u,v)，则u 、v 间的最短路径可定义为 { ()min P 0d(u,v)=,u v W =∞（），不可达时 。 2.2 最短路问题常见算法 在求解网络图上节点间最短路径的方法中,目前国内外一致公认的较好算法有迪杰斯特拉(Dijkstra)及弗罗伊德(Floyd)算法。这两种算法中,网络被抽象为一个图论中定义的有向或无向图,并利用图的节点邻接矩阵记录点间的关联信息。在进行图的遍历以搜索最短路径时,以该矩阵为基础不断进行目标值的最小性判别,直到获得最后的优化路径。 Dijkstra 算法是图论中确定最短路的基本方法,也是其它算法的基础。为了求出赋权图中任意两结点之间的最短路径,通常采用两种方法。一种方法是每次以一个结点为源点,重复执行Dijkstra 算法n 次。另一种方法是由Floyd 于1962年提出的Floyd 算法,其时间复杂度为 ()3O n ,虽然与重复执行Dijkstra 算法n 次的时间复杂度相同,但其形式上略为简单,且实际运 算效果要好于前者。 3 Dijkstra 算法 3.1 Dijkstra 算法描述 :算法的设计思想 本算法采用分支定界算法实现。构造解空间树为：第一个城市为根结点，与第一个城市相邻的城市为根节点的第一层子节点，依此类推；每个父节点的子节点均是和它相邻的城市；并且从第一个根节点到当前节点的路径上不能出现重复的城市。 本算法将具有最佳路线下界的节点作为最有希望的节点来展开解空间树，用优先队列实现。算法的流程如下：从第一个城市出发，找出和它相邻的所有城市，计算它们的路线下界和费用，若路线下界或费用不满足要求，将该节点代表的子树剪去，否则将它们保存到优先队列中，并选择具有最短路线下界的节点作为最有希望的节点，并保证路径上没有回路。当找到一个可行解时，就和以前的可行解比较，选择一个较小的解作为当前的较优解，当优先队列为空时，当前的较优解就是最优解。算法中首先用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 最短路径之Dijkstra算法详细讲解 １最短路径算法 在日常生活中，我们如果需要常常往返A地区和B 地区之间，我们最希望知道的可能是从A地区到B地区间的众多路径中，那一条路径的路途最短。最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括： （１）确定起点的最短路径问题：即已知起始结点，求最短路径的问题。 （２）确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。 （３）确定起点终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。 （４）全局最短路径问题：求图中所有的最短路径。 用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。最常用的路径算法 有：Dijkstra算法、A*算法、Bellman-Ford算法、Floyd-Warshall算法、Johnson算法。 本文主要研究Dijkstra算法的单源算法。 ２Dijkstra算法 2.1 Dijkstra算法 Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。 Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。 2.2 Dijkstra算法思想 Dijkstra算法思想为：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径, 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U 表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S 中的顶点为中间顶点的当前最短路径长度。 2.3 Dijkstra算法具体步骤 （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中。 2.4 Dijkstra算法举例说明 如下图，设A为源点，求A到其他各顶点（B、C、D、E、F）的最短路径。线上所标注为相邻线段之间的距离，即权值。（注：此图为随意所画，其相邻顶点间的距离与图中的目视长度不能一一对等） 摘要 现实生活中许多实际问题的解决依赖于最短路径的应用，其中比较常用的是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）用邻接矩阵法表示图共需要个空间，由于无向图的邻接矩阵一定具有对称关系，所以扣除对角线为零外，仅需要存储上三角形或下三角形的数据即可，因此仅需 实验五分支限界法实现单源最短路径 一实验题目：分支限界法实现单源最短路径问题 二实验要求：区分分支限界算法与回溯算法的区别，加深对分支限界法的理解。 三实验内容：解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。算法从图G的源顶点s和空优先队列开始。 结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。 四实验代码 #include 最短路径问题的算法分析及建模案例 最短路径问题的算法分析及建模案例 一.摘要 (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算法的改进错误！未定义书签。 摘要 近年来计算机发展迅猛，图论的研究也得到了很大程度的发展，而最短路径 问题一直是图论中的一个典型问题，它已应用在地理信息科学，计算机科学等 诸多领域。而在交通路网中两个城市之间的最短行车路线就是最短路径问题的 一个典型例子。 由于最短路径问题在各方面广泛应用，以及研究人员对最短路径的深入研究， 使得在最短路径问题中也产生了很多经典的算法。在本课题中我将提出一些最 短路径问题的算法以及各算法之间的比较，最后将这些算法再应用于实际问题 实验三单源最短路径 一、实验目的及要求 掌握贪心算法的基本思想 用c程序实现单源最短路径的算法 二、实验环境 Window下的vc 2010 三、实验内容 1、有向图与单源点最短路径 2、按路径长度非降的次序依次求各节点到源点的最短路径 3、Dijkstra算法 四、算法描述及实验步骤 设给定源点为Vs，S为已求得最短路径的终点集，开始时令S={Vs} 。当求得第一条最短路径(Vs ，Vi)后，S为{Vs，Vi} 。根据以下结论可求下一条最短路径。 设下一条最短路径终点为Vj ，则Vj只有：源点到终点有直接的弧 #define MAX 999 void getdata(int **c,int n) { int i,j; int begin,end,weight; for (i=1;i<=n;i++) { for (j=1;j<=n;j++) { if(i==j) c[i][j]=0; else c[i][j]=MAX; } } do { cout<<"请输入起点终点权值(-1退出)："; cin>>begin; if(begin==-1) break; cin>>end>>weight; c[begin][end]=weight; } while(begin!=-1); } void Dijkstra(int n,int v ,int *dist,int *prev,int **c) { bool s[MAX]; int i,j; for (i=1;i<=n;i++) { dist[i]=c[v][i]; //从源点到各点的值 s[i]=false; if(dist[i]==MAX) prev[i]=0; //最大值没有路径 else prev[i]=v; //前驱为源点 } dist[v]=0;s[v]=true; for (i=1;i<=n;i++) { int temp=MAX; int u=v; for(j=1;j<=n;j++) if((!s[j])&&(dist[j] 第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.sodocs.net/doc/5f16757484.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 条最短路径问题,即不但要求得到最短路径,还要得到次短、再次短等路径.这称之为广义最短路径问题. 课程设计任务书 目录 第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、理解分支限界法的剪枝搜索策略； 2、掌握分支限界法的算法柜架； 3、掌握分支限界法的算法步骤； 4、通过应用范例学习动态规划算法的设计技巧与策略； 二、实验内容及要求： 1、使用分支限界法解决单源最短路径问题。 2、通过上机实验进行算法实现。 3、保存和打印出程序的运行结果，并结合程序进行分析，上交实验报告。 三、实验原理： 分支限界法的基本思想： 1、分支限界法与回溯法的不同： 1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。 2、分支限界法基本思想： 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 3、常见的两种分支限界法： 1）队列式(FIFO)分支限界法 按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 2）优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 四、程序代码 #include 数据结构与算法课程实验报告实验四：图的相关算法应用 姓名：王连平 班级：09信科2班 学号：I09630221 实验四图的相关算法应用 一、实验内容 求有向网络中任意两点之间的最短路。 二、实验目的 掌握图和网络的定义，掌握图的邻接矩阵、邻接表和十字链表等存储表示。掌握图的深度和广度遍历算法，掌握求网络的最短路的标号法和floyd算法。 三、问题描述 对于下面一张若干个城市以及城市间距离的地图，从地图中所有可能的路径中求出任意两个城市间的最短距离及路径，给出任意两个城市间的最短距离值及途径的各个城市。 四、问题的实现 4.1数据结构的抽象数据类型定义和说明 1） typedef struct ArcCell{//储存弧信息 int Distance; ArcCell *info;//此项用来保存弧信息，，在本实验中没有相关信息要保存 }ArcCell,AdjMatrix[ MAX_VERTEX_NUM][ MAX_VERTEX_NUM]; typedef struct{//储存顶点信息 string vexs[ MAX_VERTEX_NUM];//顶点向量 AdjMatrix arcs;//邻接矩阵 int vexnum , arcnum;//图的当前顶点数和弧数 }MGraph; 顶点信息和弧信息都是用来建立一个有向网G 2） d[v][w];//G中各对顶点的带权长度 若P[v][w][u]为TRUE，则u是从v到w当前求得最短路径上的顶点 4.2主要的实现思路 首先通过一个函数（CreateDN）建立图的邻接矩阵储存方式,一次输入某条弧的起点，终点，和权值。通过调用Locate函数来找到该弧在邻接矩阵中的相应位置。 其次运用弗洛伊德算法来求各定点的最短路劲，具体思路为：如果从v到w有弧，则存在一条长度为arcs[v][w]的路径，该路径不一定是最短路径。考虑路径（v,u,w）是否存在，若存在，比较（v,w）和（v,u,w）的长度，取较短者为从v到w的中间点序号不大于0的最短路径。以此类推，每次增加一个点，从而求出任意两点间的最短路径。这样，经过n次比较后，所求得的必为从v到w的最短路径。按此方法，可以同时求得任意两点间的最短路径。 五、主要源程序代码（包含程序备注） #include 单源最短路径的Dijkstra算法： 问题描述： 给定一个带权有向图G=（V，E），其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其他各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。 算法描述： Dijkstra算法是解单源最短路径的一个贪心算法。基本思想是：设置顶点集合S并不断地做贪心选择来扩充这个集合。一个顶点属于S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist做必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其他顶点之间的最短路径长度。 源代码： #include using namespace std; //-------------------------------------数据声明------------------------------------------------//c[i][j]表示边(i,j)的权 //dist[i]表示当前从源到顶点i的最短特殊路径长度 //prev[i]记录从源到顶点i的最短路径上的i的前一个顶点 //--------------------------------------------------------------------------------------------- void Dijkstra(int n, int v, int dist[], int prev[], int c[][LEN]) { bool s[LEN]; // 判断是否已存入该点到S集合中 for (int i = 1; i <= n; i++) { dist[i] = c[v][i]; s[i] = false; //初始都未用过该点 if (dist[i] == MAX) prev[i] = 0; //表示v到i前一顶点不存在 else prev[i] = v; } dist[v] = 0; s[v] = true; 最短路径算法在物流运输 中的应用 Last revision date: 13 December 2020. 本科生毕业设计（论文）题目：线性表的设计和实现 学生姓名：张三 学号： 1153 院系：基础科学学院信息技术系 专业年级： 2012级信息与计算科学专业 指导教师：李四 年月日 摘要 随着现代物流业的发展，如何优化和配置物流的运输路径成为了一个热点的问题。其中，最具代表性的问题就是如何在一个道路网络中选择两点之间的合适路径，使其距离最短。为了解决这个问题，本文介绍了两种最常用的最短路径求解方法——DIJKSTRA算法与FLOYD算法，分析了它们的适用范围以及时间复杂度。最后，对一个具体的航空公司物流配送问题进行了求解，得到了理论最优路径。 关键词：最短路径问题；DIJKSTRA算法；物流运输 ABSTRACT With the development of modern logistics industry, how to optimize and configure the transport path of logistics has become a hot issue. Among them, the most representative problem is how to select the appropriate path between two points in a road network to minimize the distance. In order to solve this problem, this paper introduces two most common shortest path solutions —— Dijkstra algorithm and Floyd algorithm, and analyzes their application range and time complexity. Finally, a specific airline logistics distribution problem is solved, and the theoretical optimal path is obtained. Keywords：Minimum path problem；Dijkstra algorithm；Logistics transportation 数据结构课程设计报告撰写要求 （一）纸张与页面要求 1．采用国际标准A4型打印纸或复印纸，纵向打印。 2．封页和页面按照下面模板书写（正文为：小四宋体1.5倍行距）。 3．图表及图表标题按照模板中的表示书写。 （二）课设报告书的内容应包括以下各个部分：（按照以下顺序装订） 1.封页(见课设模版) 2、学术诚信声明，所有学生必须本人签字，否则教师拒绝给予成绩。 2.任务书(学生教师均要签字,信息填写完整) 3.目录 4.正文一般应包括以下内容: （1)题目介绍和功能要求（或描述） 课程设计任务的详细描述(注意不能直接抄任务书),将内容做更详细的具体的分析与描述； （2) 系统功能模块结构图 绘制系统功能结构框图及主要模块的功能说明； （3) 使用的数据结构的描述: 数据结构设计及用法说明; （4) 涉及到的函数的描述 ; （5) 主要算法描述( 程序流程图) （6) 给出程序测试/运行的结果 设计多组数据加以描述（包括输入数据和输出结果） （7) 课程设计的总结及体会 （8) 参考文献 格式要求：[1]作者，等. 书名.出版地：出版社，出版年 5.附录：程序清单 (应带有必要的注释) 沈阳航空航天大学 课程设计报告 课程设计名称：数据结构课程设计 课程设计题目：利用弗洛伊德（Floyd)算法求解 最短路径 院（系）：计算机学院 专业：计算机科学与技术(物联网方向) 班级：34010105 学号： 姓名： 指导教师： 说明：结论（优秀、良好、中等、及格、不及格）作为相关教环节考核必要依据；格式不符合要求；数据不实,不予通过。报告和电子数据必须作为实验现象重复的关键依据。 单源最短路径问题 I 用贪心算法求解 贪心算法是一种经典的算法，通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。一般具有2个重要的性质：贪心选择性质和最优子结构性质。 一、问题描述与分析 单源最短路径问题是一个经典问题，给定带权有向图G =(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其他各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。 分析过程：运用Dijkstra算法来解决单源最短路径问题。 具备贪心选择性质 具有最优子结构性质 计算复杂性 二、算法设计（或算法步骤） 用贪心算法解单源最短路径问题： 1.算法思想： 设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其他顶点之间的最短路径长度。 2.算法步骤： (1) 用带权的邻接矩阵c来表示带权有向图, c[i][j]表示弧 数据结构课程设计 —省会城市最短路径求解一、类关系图 说明：Graph类继承Form类，同时嵌入了CityInf结构体和List类。 Graph类的几个重要函数、类、结构体 private void Init()//初始化函数 private void ShowMap_Paint(object sender, PaintEventArgs e) //绘制地图 private bool GetMinDistanceFun(int entry) //采用迪杰斯特拉算法获得最短路径private void BFS(int StartPoint, int[] visited, string name) //广度优先遍历函数private void DFS(int StartPoint, int[] visited, string name)//深度优先遍历函数private void Prim()//求解最小生成树 Prim算法 private class List //广度优先遍历用到的队列类 public struct CityInf//存放城市信息：城市名称、城市坐标、状态值 二、流程图 三、主要算法的实现 1．用迪杰斯特拉算法实现省会城市间最短路径的求解 private bool GetMinDistanceFun(int entry) { int inputnodenum = CityData.citysum; int[] Mark = new int[inputnodenum]; //标志位数组标记数据在哪个集合 int mindis = 0, nextnode = 0;//最短路径，下一个城市结点 int i, j; //第一轮距离数组记录从起始点到其他所有点的边权值 for (i = 0; i < inputnodenum; i++) { Distance[i] = GetCityWeight(entry, i); //所有标志位清零 Mark[i] = 0; //如果起始结点可以抵达某个结点 if (i != entry && Distance[i] < MaxWeight) { RoutePath[i] = entry; //则把该结点首先放入路径数组 } else { RoutePath[i] = -1;//表示该路径不通 } } //初始状态下集合存放找到最短路径顶点集合的中只包含源点entry 所以把它在Mark 中标记出来 Mark[entry] = 1; //在还没有找到最短路径的结点集合中选取最短距离结点nextnode for (i = 1; i < inputnodenum; i++) { //设定每轮的初始最小距离为无穷大 mindis = MaxWeight; for (j = 0; j < inputnodenum; j++) { //保证每次循环mindis是到entry的最小值 if (Mark[j] == 0 && Distance[j] < mindis)//如果没有进入最短路径且距离小于最小距离 { nextnode = j; mindis = Distance[j];//记录本次循环的最短路径 } }最短路径学年论文
最短路径流程图及算法详解
gis计算最短路径的Dijkstra算法详细讲解
基于Floyd算法的最短路径问题的求解c++
分支限界法实现单源最短路径问题
最短路径问题的算法分析及建模案例
单源最短路径 贪心算法
前N条最短路径问题的算法及应用
弗洛伊德算法求解最短路径
单源最短路径问题
实验四图的最短路径弗洛伊德算法实现
单源最短路径的Dijkstra算法
最短路径算法在物流运输中的应用
数据结构课程设计-Floyd算法求解最短路径
单源最短路径
数据结构课程设计_城市最短路径求解
相关文档
- _几种最短路径的算法及比较
- 数据结构与算法单源最短路径问题C++求解
- 几种常用的最短路径算法
- 图的最短路径 dijkstra算法
- 弗洛伊德算法求解最短路径
- 几种常用的最短路径算法
- 最短路径流程图及算法详解
- 复杂网络中最短路径问题的求解算法研究
- 运筹学C语言实现Dijkstra算法求解图的最短路径
- 最短路径流程图及算法详解
- 复杂网络中最短路径问题的求解算法研究
- 所有最短路径的求解算法
- 运筹学C语言实现Dijkstra算法求解图的最短路径
- 最短路径流程图及算法详解
- 基于Floyd算法的最短路径问题的求解c++
- 数据结构课程设计-Floyd算法求解最短路径
- 弗洛伊德算法求解最短路径
- 弗洛伊德算法求解最短路径
- 最短路径问题的算法分析及建模案例
- c课设报告基于Dijkstra算法的最短路径问题求解精编版