最短路问题的FLOYD算法的若干讨论

第22卷 第5期 Vo1．22 No．5 重 庆 工 学 院 学 报(自然科学) Journal of Chongqing Institute of Technology(Natural Science) 2008年 5月 Mav 2008 最短路问题的 Floyd算法的若干讨论 郝 自军 ，何尚录2 (1，北方民族大学 信息与计算科学学院，银川 750021； 2．兰州交通大学 数理与软件工程学院，兰州 730070) Some Discussions on Floyd Algorithm HA0 Zi—jun ，HE Shang—lu (1，School of hfformation and Calculating~ience，Noah University for Nationalities，Yinchuan 750021，China； 2．School of Mathematics，Physics＆Software Engineering，l~q．rlzhou Jiaotong U versity，Lallzhou 730070，China ) Abstract：Floyd algorithm is usually used in shortest path when a graph does not include negative circuit． This article first discusses this algorithm ，and then gives some modification of the calculating process of this algorithm．Th e modified algorithm can produce the shortest paths between peaks with simple calculation when it comes to networks with not too big number of orders． Key words：Floyd Algorithm；shortest path 最短路问题是网络最优化中一个基本而又非常重要的问题，这一问题相对比较简单，在实际生产和 生活中经常遇到，许多的网络最优化问题可以化为最短路问题，或者用最短路算法作为其子程序．因此， 最短路的用途已远远超出其表面意义一1 J迄今为止，所有最短路算法都只对不含负回路的网络有效，实 际上对含有负回路的网络，其最短路问题是 NP困难的_2 J，因此本研究所讨论的网络也不含负回路．此 外，如果将无向图每条边用两条端点相同、方向相反的弧来代替，可以将其化为有向图，因而不讨论无向 图．本研究中未述及的术语 、记号可参见文献[2]． * 收稿 日期：2008—02—20 基金项 目：北方民族大学科研项 目(2(Kr-／Y044)． 作者简介：郝自军(1978一)，男，宁夏灵武人(回族)，硕士，讲师，主要从事运筹与优化的研究 维普资讯 http://www.cqvip.com 郝自军，等：最短路问题的 Floyd算法的若干讨论 157 1 相关定义及准备 定义 1_】 】 一个有向图 D是由一个非空的有限集合 (D)和 (D)中某些元素的有序对集合 A(D) 构成的二元组，记为 D=(V(D)，A(D))，简记为 D=(V，A)．其中：有限集合 V={ ， 2，⋯， }为 D的 顶点集；A={n ， 2，⋯，n }为 D的弧集，A中每个元素n 都是 (D)中某 2个元素 和 的有序对，记 为 。 =( ， )． 如果给有向图 D中的每条弧都赋一个或多个实数值，得到的有向图称为赋权有向图或有向网络，简 称为网络，并记为 D=(V，A，W)． 定义 2 】 设 D=(V，A，W)是一个赋权有向图， 和 是D中2个顶点，，J中所有( ，vi)路中权最 小的路称为最短( vi)路． 假设网络 D=(V，A， )不含负回路，顶点集 V={ ， 2，⋯， }，先考虑特定顶点 l到其它各顶点 的最短路．D中最短( ， )路的线性规划模型为： ， X0"-- ={蔓。 ≤n一 x／j=0或 1 (对V(Vi， )∈A) (1) (2) (3) 其中：条件(1)中w0．代表弧( ， )的权；条件(2)则代表在( l，Vn)路上除了顶点 1只有一条出弧、 只有 一 条人弧以外，其余的顶点出弧数量与入弧数量相同；条件(3)中 取 1或 0分别代表弧( ， )在( ， )路上的次数．对于一般的( ， )路(i=1，2，⋯，n)，可以将条件(1)～(3)做适当变换得到类似的线性 规划模型．显然如果能解出(1)～(3)，则最短( ， )路的长就是目标函数的值，而根据 的取值-g~Pff 定出最短( ，Vn)路．但不幸的是这样做并不能带来很大帮助．通常可以将条件(1)～(3)化为其对偶规 划，也可以根据下述定理化为一个方程． 定理 1[ ] 设 D=(V，A， )是一个不含非正回路的网络，顶点集 ={ l， 2，⋯， }，且 D中存在 ( l， ) (i=1，2，⋯，n)路，则 瓦，是D中最短( 】， ． =1，2，⋯，n)路的长，当且仅当(瓦 ，西2，⋯，u )满足： f ～ (4) 【 f= ， rai ⋯n (tti+w／j) = 2，3，⋯ ， ”i’ C H 为了方便，这里约定对某个( ， ) A，令 +∞，这样式(4)等价于 ／／'l 0 (5) L M，=rain( +wkj) =2，3，⋯， 方程(5)称为最短路方程，它是一个非线性方程组，求 u 时必须知道所有其它的 ，故直接求解式 (5)是相当困难的，因而将最短路问题化为方程(5)似乎并没有什么好处，但可以以它为基础得到特定顶 点到其他各顶点最短路的各种算法．对于特殊的无回路网络、非负权网络和一般的不含回路的网络，分别 可以用代换法、Dijkstra算法和 Ford算法求出顶点 到其他各顶点之间的最短路，具体可见文献[2]． 2 Floyd算法及在计算中的改进 在某些问题中，需要求出给定的不含负回路的网络 D=(V，A，W)中所有顶点对之问的最短路，其中 维普资讯 http://www.cqvip.com 158 重 庆 工 学 院 学 报 V={ 1， 2，⋯， }．Floyd算法就是解决这类问题的．当然这个问题可以在一定条件下反复应用已有的代 换法、Dijkstra算法和Ford算法，第 1次求从 l到 2， 3，⋯， 的最短路，第 2次求从 2到 l， 3，⋯， 的 最短路，⋯，第 n次求从 到 ⋯， 一 的最短路．这样就得到 D中所有顶点对之间的最短路．但这 样做程序复杂且计算量大，计算量为 0(n )，而如果用 Floyd算法，可以达到简化复杂汁算的目的． 在不含负回路的网络 D=( ，4， )中，对一切( ， ，)∈A，W 是弧( ， )的权，当( ，vJ)硭A时， Floyd算法 规定 关于下班后关闭电源的规定党章中关于入党时间的规定公务员考核规定下载规定办法文件下载宁波关于闷顶的规定 ： 用 D( ， ，m)表示由顶点集合 }U{ ，：U{ l， 2，⋯， }导出的 D的子网络(i， =1，2，⋯，n)．特别地 D(i， ，0)表示由顶点集{ }U{ = ， }导出的 D的子网络，把网络 D(i， ，m)中最短( ， )路的长 记为 “ ’，则显然有下面的结论： 结论 1 “ =W 结论2 D(i， ，凡)=D，因此 u：，’是D中最短( ， )路的长． 结论3 D(i， ，m一1)是 D(i， ，m)的子网络，因而 “ ，’≤“：， ’． 结论 4 D(i，m，m)=D(i，m，m一1)，D(m， ，m)=D(m， ，m一1)，所以有 “( tn)=“ 。。)，H = u ． 有了上述准备及几个重要的结论，就可以得出以下这个很重要的定理． 定理 2[。] 设网络 D=( ，A， )不含负回路，则对一切 i， =1，2，⋯，n，网络 D(i， ，m)中最短( ， )路的长 “ ’满足： f H =W i ： in (m-1) ， + } (1≤ m≤ 川 ‘6’ 定理 2是 Floyd算法的重要依据，让 m从 1循环到 凡就可以得到网络D中最短( )路的长 “ ． 为了在计算网络 D(i， ，m)中最短( )路的长的同时求出 D(i， ，m)中最短( ， )路，引进一个正向 追踪法： 令 P ’是网络D(i√，m)中最短( )路，r 表示P 的第一条弧的头的下标，显然 r = ．如果 r 已经知道，当 u7。。 ≤“ 。。 +“ 。。 时，则 “ =“ 。。 ，因而有 r ’=r ；否则 r ’= r ． 若 r ’=k，则 P 的第 1条弧为( )，因为 D不含负回路，因而 P 一(Ui， )是 D中最短 ( ， )路，从而P 的第1条弧就是P 的第2条弧，依次类推，可以得到P； 的所有弧． 因此，Floyd算法的步骤： Step 0 令 H ’=W r： ’= (i， =1，2，⋯，凡)，m=1． Step 1 对一一切 1≤i≤凡，1≤ ≤凡，令： r ，= Fl jm -1 ．若 u O" (m 一 - l ) ~ > -- U im(m 一 - l ，)：： (m一- 1)u~m)=rain{U 一 ⋯ ， )．若 M )>M 一1)+H 一1) Step 2 如果 m=凡，结束；否则置 m=m+1，转 Step 1． 基于上述 Floyd算法，我们在计算中可以将其简化为： Step 0 令 H ’=W r ’= (i， =1，2，·--，凡)，m=1． Step 1 对一切 1≤ ≤凡，1≤ ≤凡，令 U m’=(H ’)；R m’=(r ’)． 先写出U‘一 ’的第m行和第m列的所有元素，用第m列的第1个元素uf 。。’与第m行的每个元素 u ’(1≤ ≤凡)相加，并取u ’=min{ul?。。’，u{ ’+u 。。’}；再用第m列的第2个元素 u5： 与第 维普资讯 http://www.cqvip.com 郝 自军，等：最短路问题的 Floyd算法的若干讨论 159 m 行中的每个元素u (1u )+u ’，则 u =u ’+u ’，此时在 u ’下端划一横 线．在 R ’的相应于 U )中所有划横线的元素位置( ，1)处，将 R 的元素 r ’变为该行的第m 列的元素 r )，并将 ( ’变为 ( ’ Step 2 如果 m=n，结束；否则置 m=／Tt+1，转 Step1． 这样我们对阶数不太大的网络进行较简单的计算就能得出所有顶点对之间的最短路． 参考文献： [1] 运筹学教材编写组．运筹学[M]．2版．北京：清华大学出版社，1990． [2] 谢政．网络算法与复杂性理论[M]．长沙：国防科技大学出版社，2004 [3] 谢金星，邢文训 ．网络优化[M]．北京：清华大学出版社，2000． (责任编辑 刘 舸) (上接第 146页) 对式(6)取模 31 601，得剩余序列周期为 20，当 n 8，9，18，19(mod20)时，一M +7v ±619，-4-31 (Ⅱ 31 601)．由式(6)得1：( )：(j+ 一 6 ⋯ 19)，( )=一1，矛盾，所以式(6)无解． 综合 1)和 2)的结论知，式(1)仅有正整数解(X，Y)=(7，1)． 证明完毕． 参考文献： [1] COHN J H E．Some Quartic Diophantine Equations[J]．Pacific J Math，1968，26；233—243． [2] TZANAKIS N．On the Diophantine Equation Y 一D=2 [J]．NumberTheory，1983，17：144—164 [3] 黎进香，张春蕊．关于不定方程的初等解法[J]．哈尔滨工业大学学报，1995(5)：13—16． [4] 柯召，孙琦．数论讲义[M]．北京：高等教育出版社，2001． [5] 罗明．关于不定方程 +1=7y [J]．重庆师范学院学报：自然科学版，2003，20(1)：5—7． (责任编辑 刘 舸) 维普资讯 http://www.cqvip.com