（计算机软件与理论专业论文）求图中受顶点数限制的所有最短路径的算法分析研究.pdf

华东师范大学硕士学位论文 求图中受顶点数限制的所有屉短路径的算法研究 摘要 解决图中受顶点数限制的最短路径问题在交通工程、通信网络等方面有重要 的实际意义。本文主要是针对k 顶点数限制最短路径问题提出求解算法。在实 际应用中，除希望得到最短路径外，还希望得到次短、再次短等路径，称为广义 最短路径，本文还提出了受k 顶点数受限制的广义最短路径的求解算法。 本文首先介绍了最短路径问题的研究意义、现状等，接着对图的基本知识和 最短路径问题做了简单介绍，并对求解最短路径问题常用算法和本文工作相关的 最短路径算法作了总结概述。 第三章是本文的主要工作，本章首先给出了求解图中受k 顶点数限制的所有 最短路径的一种基础算法，简称b c s p 算法，b c s p 算法借助了图的广度搜索算法， 生成扩展最短路径树，然后根据扩展最短路径树输出所有最短路径；算法的时间 复杂度为n y c ( n 为图中顶点总数，k 为受限制的顶点数，c 为相应生成树中每 一层结点鬏了。为了提高算法效率，本文又提出了新的改进算法，简称i c s p 算法， i c s p 算法采用了逆邻接表、标记数组等数据结构并灵活使用了指针等，此算法 主要是在求解最短路径的基础上生成了有效前驱结点链表而其它相关算法都只 关注于一个有效| j 驱结点；相对算法b c s p 而言，i c s p 算法的时日j 复杂度得到了 很大程度的优化，时间复杂度为m a x 0 ( ( k 一2 ) w ) ，o ( k * s h ( g ，i ，j ) ) ) ( w 为图 中弧的条数，s h ( g ，i ，j ) 为所有受顶点数限制的最短路径条数) 。我们在实际问 题中可能还需考虑图的次短等路径，因此本文提出了求解受顶点数限制的广义最 短路径算法，简称g c s p 算法，它在算法i c s p 的基础j ：采用了吲溯路径算法，可 以得到受顶点数限制的次短等路径，其算法时问复杂度为o ( k 2 木( s h ( g ，i ，j ) + ( s h 2 ( g ，i ，j ) ) 2 ) ( s h 2 ( g ，i ，j ) 为广义最短路径条数) 。 在第四章中通过一个交通实例对本算法进行了仿真实现，通过实验表明，本 文提出的算法快速有效。 关键词：逆邻接表；限制；最短路径；生成树；，“义最短路径 华东师范大学硕十学位论文 求图中受顶点数限制的所有最短路径的算法研究 a b s t r a c t k - n o d e ss h o r t e s tp a t hi n v o l v e sm a n yd o m a i n s ，w h i c hi ss i g n i f i c a n tf o rt r a f f i c e n 舀n e e r i n g , c o m m u n i c a t i o ns y s t e m ，a n ds oo n t h i sa l g o r i t h mi s d i r e c t e da tt h e d e f i c i e n c y ，a n ds o l v et h ep r o b l e mo na l ls h o f l e s tp a t hw i t hv e r t i c e s - c o n s t r a i n e d b u ti n p r a c t i c e ，t h es h o r t e s tp a t hm a y b ei sn o tt h eo n l yo n et h a ti sc a r e da b o u t a l s ot h e s e c o n ds h o r t e s tp a t ho rt h et h i r ds h o r t e s tp a t ha r eb ec a r e da b o u t ，a n dw ec a l lt h e m g e n e r a l i z e ds h o r t e s tp a t h s s ot h i sp r o b l e mi sa l s os o l v e di nt h ep a p e r t h i sd i s s e r t a t i o na n a l y s e st h es e n a n ds t a t u sq u oo ft h es h o r t e s tp a t h t h e n i n t r o d u c eb a s i ck n o w l e d g eo ng r a p ha n ds h o r t e s tp a t hp r o b l e m n o r m a la l g o r i t h m sf o r s h o r t e s tp a t ha r eg i v e na n ds o m ea l g o r i t h m sr e l a t e ds h o r t e s tp a t h sa r eg i v e nt o o c h a p t e r3i st h ei m p o r t a n to n ei nt h i sp a p e r f i m t ，ab a s i ca l g o r i t h mc a l l e db c s p a l g o r i t h mi sp u tf o r w a r d b c s pu s e sa l g o r it h mb f sa n dp r o d u c t ss p a n n i n gt r e e t h e na l ls h o r t e s tp a t h sa r ep r o d u c t e da c c o r d i n gt ot h es p a n n i n gt r e e b u ti t st i m e c o m p l e x i t yi sc o m p l e xt h a ti s 竹罗c ( ni st h en u m b e ro fv e r t i c e si nag r a p h ，ki st h e c o n s t r a i n e dn u m b e ro fv e r t i c e s 。ti st h en u m b e ro fn o d e s 伽e a c hl e v e l ) t h e n a l g o r i t h mi c s pi sg i v e no u tt oi m p r o v ei t st i m ec o m p l e x i t y i c s pu s e si n v e r s e a d j a c e n c yl i s t ，f l a g a r r a ya n dp o i n t i tm a r k s t h el i s to ft h ee f f c c t e dn o d e sb a s e do nt h e s h o r t e s tp a t hw h i l eo t h e ra l g o r i t h m sa r ec o n c e r n e da b o u to n l yo n en o d e a n di t st i m e c o m p l e x i t yi sm a x 0 ( ( k 一2 ) $ w ) ，0 ( k * s h ( g ，i ，j ) ) j ( wi st h en u m b e ro fa r ci na g r a p h ，s h ( g ，i ，j ) i st h en u m b e ro fs h o r t e s tp a t h s ) t h a ti sb e t t e rt h a na l g o r i t h m b c s p b u ti np r a c t i c e ，t h es h o r t e s tp a t hm a y b ei sn o tt h eo n l yo n et h a ti sc a r e da b o u t a l s ot h es e c o n ds h o r t e s tp a t ho rt h et h i r ds h o r t e s tp a t ha r eb ec a r e da b o u t ，a n dw ec a l l t h e mg e n e r a l i z e ds h o r t e s tp a t h s t h ea l g o r i t h mg c s pi sg i y e nt os o l v et h i sp r o b l e m a l g o r i t h mg c s pb a s e so nt h ea l g o r i t h m1 c s ea n di t u s e sb a c k t r a c k a l g o r i t h mt og e t a l lt h eg e n e r a l i z e ds h o r t e s tp a t h s ，a n di t st i m ec o m p l e x i t yi so ( k 2 车( s h ( g ，i ，j ) + ( s h 2 ( g ，i ，j ) ) 2 ) ( s h 2 ( g ，i ，j ) i st h en u m b e ro fg e n e r a ls h o r t e s tp a t h sw h o s e v e r t i c e sa r ec o n s t r a i n e d ) i n c h a p t e r4 ，w ed e s i g n at r a f f i cm o d e la n dc o n d u c ts i m u l a t i o ns t u d i e st o e v a l u a t eo u ra l g o r i t h ma n ds t r a f e g i e s a n dw es e et h ee f f i c i e n c yo ft h i sa l g o r i t h mi s h i g l l k e yw o r d s ：i n v e r s ea d j a c e n c yl i s t ；c o n s t r a i n ；s h o r t e s tp a t h ：s p a n n i n gt r e e ；g e n e r a l s h o r t e s tp a t h j l 华东师范大学硕士学位论文求图中受顶点数限制的所有最短路径的算法研究 学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及取得的研 究成果。据我所知，除文中已经注明引用的内容外，本论文不包含其它个人已 经发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均已 在文中作了明确说明并表示谢意。 v ，p 作者签名：三生兰望!日期：兰塑2 竺 学位论文授权使用声明 本人完全了解华东师范大学有关保留、使用学位论文的规定，学校有权保 留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版。有权 将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅。有 权将学位论文的内容编入有关数据库进行检索。有权将学位论文的标题和摘要 汇编出版。保密的学位论文在解密后适用本规定。 学位论文作者签名丘卫弦 导师签名： 日期：j 哦f 土 如3 每 日期：垃22 沙 华东师范大学硕士学位论文 求图中受顶点数限制的所有最短路径的算法研究 第一章绪论 本章主要对最短路径算法的研究意义和国内外的研究现状加以描述，最后介 绍了本文所作的主要工作以及本文的内容安排。 1 1 研究背景及研究意义 图论作为一个新兴的应用分支，由于其在自然科学、工程技术、管理科学以 及社会科学等领域有广泛应用，所以受到国内外学术界的高度重视。随着计算机 的出现和发展，图论的研究范围更广更深，已经渗透到诸如语言学、逻辑学、物 理学、化学、电讯工程等分支中【1 】【2 】。最短路径问题是图论中的一个重要研究 课题1 3 】，有着广泛的应用，它作为许多领域中选择最优问题的基础，在电子导 航、交通旅游、城市规划以及电力、通讯等各种管网、管线的布局设计和实际交 通通网络分析以及计算机网络路由分析中都占有重要地位1 4 】。 “最短路径”，顾名思义就是在所有路径中找到一条距离最短的路径。但是 从网络模型的角度看，最短路径分析就是在指定网络中两结点问找一条阻碍强度 最小的路径。根据阻碍强度的不同定义，最短路径不仅仅指一般地理意义上的距 离最短，还可以引申到其它的度量，如时间、费用等。相应的，最短路径问题就 成为最快路径问题、最低费拜j 问题等，所以我们所说的最短路径也可看作是最优 路径问题【5 】。最短路径分析有着广泛的应用【6 】，在实际中常用于汽车导航系统 以及各种城市应急系统等( 如1 1 0 匪警、1 1 9 火警以及1 2 0 医疗急救系统) ，还 有各种线路保障问题( 配电网的抢修问题，通讯光缆的最快抢修问题) 。 在交通运输和通信网络的研究中碰到的许多问题经转化后都可以归结为最 短路径问题，这也是最短路径问题撮适用的两个方面。文献 7 就是针对这两个 方面应用最短路径算法。 最短路径问题一直是计算机科学、运筹学、交通工程学、地理信息学等学科 的一个研究热点。经典的图论与不断发展完善的计算机数据结构以及算法的有效 结合使得新的最短路径算法不断涌现，各具特色 8 9 。山于这些算法主要诞生 于计算机科学及运筹学领域，在算法的设计过程中，根掘抽象网络的拓扑特性， 华东师范人学硕士学位论文求图中受顶点数限制的所有最短路径的算法研究 力求通过各种新型的计算机数据结构和运筹学方法，从理论上减少算法的时间复 杂度，而忽略了具体的网络可能具有的分布特性。 在实际应用问题中，常常需要求解带约束条件的最短路径问题，如通过指定 的节点、带宽和时延等约束条件。本文的重点在于约束最短路径经过的中间顶点 数，即从源点到目的点经过的顶点数目不超过一定数量。受顶点数限制的最短路 径问题有着实用价值，例如：在交通运输中，某汽车队从甲地到乙地，假设选择 路线的指标有两个：其一是距离短；其二是沿途中尽可能少的经过一些城市点( 这 是从时间上考虑到由于城市交通拥挤，经过一个城市需较多的时间) 。即：汽车 队往往要求所选择的行车路线在沿途经过城市的个数不超过k 个的限制条件下， 总路程最短 1 0 。在实际的计算机网络系统中，都包含多个路由器等中间转换部 件 11 ，数据包的转发也尽可能少的经过一些中间站点并使经过的路程最短，因 为数据包在内存中存储转发需要耗费大量时间 1 2 。 1 2 国内外研究现状 最短路径算法是图论中的一个经典问题，它的研究起源于2 0 世纪5 0 年代末 期，至今大约有两千多篇文献讨论此问题，其中大部分都是出现在关于图的总体 组合优化的杂志或会议论文中，还有一些是发表在专业学术期刊中。它已经应用 于许多涉及到统筹规划的领域，其中最普遍的一个应用领域就是交通运输领域。 最短路径l u 】题的计算机求解就是交通运输分析与规划研究中必不可少的一个环 节。这也j f 是随着大规模数学模型的应用越来越广泛，寻求一种高效、快速的最 短路径算法变得越束越重要的原因。目| i i 在交通运输问题及计算机网络通讯问题 中所普遍采用的最短路径算法主要是d i j k s t r a 算法，此算法找出一个给定顶点 与图中各个其它顶点相连的最短路径；求图中任意一对顶点之间的最短路径算法 由f 1 0 y d ( 弗罗依德) 和d a n t z i g ( 但茨希) 提出；二重扫除算法可以求图中一 个给定顶点和所订其它顶点之i h j 第k 条最短路径的长度；推广的f 1 0 y d 算法 ( g e n e r a i z e df 1 0 y da g o r i t h m ) 和推广的d a n t z i g 算法( g e n e r a l i z e dd a n t z j g a l g n r i t h m ) ，这两个算法町以求图中每一对顶点之间第k 条最短路径的长度；以 上各种最短路径算法郜利用了加法运算和求极小值运算。还有种就是a 乖算法， 这种算法主要应用于极大规模网络中，网络中的节点数量往往达到指数级，但这 华东师范人学硕上学位论文求图中受顶点数限制的所有最短路径的算法研究 种情况般只在计算机网络通讯应用中出现，而在实际交通路网中不常见 1 3 2 。 在我国关于最短路径算法的研究除了计算机网络通讯技术领域的应用之外，在交 通运输中的应用主要是交通运输网络优化中的网络平衡分析及智能交通运输 ( i t s ) 中车辆诱导子系统内的最优路径( o p t i m a lp a t h ) 求解，其中吉林大学交 通学院i t s 研究实验室及同济大学的i t s 研究中心在这方面取得了一定的成果； 在交通领域的另外一个应用就是动态交通分配( d t a ) 中的路径优化选择 ( r o u t i n g ) ，清华大学的交通研究所在此方面取得了一定的研究成果 1 4 。 1 。3 本文的主要工作 最短路径问题是一个著名问题，它在实际生产生活中有广泛应用，其中受顶 点数限制的最短路径的研究具有重要的实用价值。1 9 9 6 年，周经伦和吴唤群已 提出了一个求受顶点数限制的最短路径问题的算法 周算法) 1 1 5 ，周算法解决 了受顶点数限制的最短路径问题，其时间复杂度为o ( n 3 l o g n ) ( n 为图中顶点数) ， 且周算法使用了几种标号，存储结构较复杂，这使得周算法的描述和实现较为复 杂。2 0 0 2 年，孙强老师提出了一种新的求受顶点数限制的最短路径问题的算法 ( 孙算法) 【1 0 】，孙算法相对于周算法而言，有了相对大的改进，孙算法时问复 杂度为o ( k 一2 ) 幸n 2 ) ( k 为顶点数的限制值) ，并且算法比较简单。2 0 0 4 年，钟子 飞又提出了一种求顶点数限制的最短路径的新算法( 钟算法) 【1 6 】，钟算法在孙 算法的基础上做了改进，钟算法的时问复杂度为o ( ( k 一2 ) t w ) ( w 为图中所有边的 条数) 。 ， 通过上述的国内外研究现状介绍，可以看到目的对最短路径问题的研究似乎 已经达到了很完善的地步，对丁受顶点数限制的最短路径问题，虽然有一些研究， 但是还没有求解图中受顶点数限制的所有最短路径算法，本文正是针对这一问 题，提出了相应的求解算法。主要是本文第三章的工作，本牵首先给出了求解图 中受顶点数限制的所有最短路径的一种基础算法，简称b c s p 算法，牛| j 关论文“求 受顶点数限制的所_ 自，最幻路径的一种算法”已经发表 ：计算机应用研究”2 0 0 7 一1 年7 月增刊，算法b c s p 的时问复杂度比较复杂。为圩x c ( n 为图中顶点总数， 何 k 为受限制的顶点数，c 为生成树巾每一层结点数) 。为了提高笄法的时问复杂度， 华东帅范大学硕l - a t 位论文求图中受顶点数限制的所有昂短路往的算法研究 本文又提出了新的改进算法，简称i c s p 算法，相关论文“求图中受顶点数限制 的所有最短路径的一种算法”已经被“计算机工程与设计”录用，相对算法b c s p 而言，i c s p 算法的时问复杂度得到了很大程度的优化，时间复杂度为 m a x 0 ( ( k - 2 ) 押) ，0 ( k * s h ( g ，i ，j ) ) ) ( w 为图中弧的条数，s h ( g ，i ，j ) 为所有 受顶点数限制的最短路径条数) 。但是我们在实际问题中不仅仅关心图中的最短 路径，可能还需考虑图的次短等路径，因此本文还提出了求解受顶点数限制的广 义最短路径算法，简称g c s p 算法，它在算法i c s p 的基础上采用了回溯路径算法， 可以得到受顶点数限制的次短等路径，其算法时间复杂度为0 ( k 2 掌( ( s h ( g ，i ，j ) + s h 2 ( g ，i ，j ) ) 2 ) ( s h 2 ( g ，i ，j ) 为广义最短路径条数) 。 该算法的主要有以下特点： ( 1 ) 提出了求解算法，能够高效的求出图中受顶点数限制的所有最短路径。 ( 2 ) 采用逆邻接表作为图的存储结构，降低了算法的时间复杂度。 ( 3 ) 使用常见的数据结构，如：指针、链表、生成树、标志数组等，使得算 法易懂易读。 ( 4 ) 使用熟悉的算法设计技术，如：递归法、回溯法、分支限界和贪心算法 等。 ( 5 ) 在狭义的求解图中受顶点数限制的所有最短路径的基础上，采用从目的 点回溯路径来获得次短等广义最短路径。 在第四章中通过一个交通实例对本算法进行了仿真实现，通过实践表明，本 文提出的算法快速有效。 1 4 本论文的内容安排 本文的内容安排如下： 第一章绪论，主要针对最短路径问题的研究7 景、发展历史，国内外的研 究现状加以描述，并介绍了本文所作的主要工作和本文的内容安排。 第二章图和最短路径| u j 题，主要介绍了图论的基本知u 和最短路径的拍关 内容，并给出了最短路径的常_ j 算法和本文j 作棚关的最短路径算法。 第三章本文提出的求解算法，实现了求顶点数限制的所仃最短路径的算法， 主要有基础算法b c s p 和改进算法i c s p ，还提出了求解次短、再次短等所有的 4 华东师范大学硕l 学位论文求图中受顶点数限制的所有屉氰- 路径的算法研究 广义最短路径算法g c s p 。 第四章实验仿真和研究，对本文提出的算法借助于实际交通数据，进行了 仿真实验和性能分析。 第五章结束语，主要是对本文的相关工作进行了总结，并对这一问题的研 究及其发展前景加以描述。 5 华东师范人学硕上学位论文求图中受顶点数限制的所有屉短路径的算法研究 第二章图和最短路径问题 本章主要介绍了图的基本知识，且对最短路径问题作了概述，给出了求解最 短路径问题常用的算法，包括最小生成树算法、最短路径生成树算法和s t e i n e r 树算法等，最后介绍了与本文工作相关的求解最短路径的算法，包括受顶点数限 制的最短路径算法，求图中所有最短路径算法和其他相关最短路径算法。 2 1 图的基本概念 图( g r a p h ) 是一种较线性表和树更为复杂的数据结构。在线性表中，数据 元素之间仅有线性关系，每个元素只有一个直接前驱和一个直接后继；在树形结 构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一 层中多个元素( 其孩子结点) 相关，但只能和上一层中一个元素( 其双亲结点) 相关；而在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素 之间都可能相关1 1 7 1 8 1 。 1 图 图g 是由两个集合v 和e 组成，记为g = ( v e ) ，其中v 是顶点的有穷非空 集合，e 是v 中顶点偶对的有穷结合，这些顶点偶对称为边。 规定用v ( g 1 表示图g 中的顶点集合，是一个非空的顶点集合，通常用字母 或自然数( 顶点的编号) 来标识图中顶点。约定第i 个项点用v j 表示；e ( g ) 表示 图g 的边的集合，它确定了图g 中的数据元素的关系。e ( g ) 可以为空集，当e ( g ) 为空集时，则图g 只有顶点而没有边。n = l v l 为图g 的顶点数，m = i e i 为图g 的 边数。顶点集和边集分别记为v = ”0 ，v 1 ，一，v 。) ，e = e l ，e 2 ，e 。) 。为了方便起 见也把一个连接顶点对( v i ，v j ) 的路径记为b 2 无向图和有向图 若边e i 与顶点无序偶对( v i ，v k ) 相关联，则称该边为无向边。 若边e i 与顶点有序偶对( 。i v k ) 相关联，则称该边为有向边。 这罩，v 。称为边e i 的起始顶点；v t 称为边e i 的终止顶点。每一条边都是无向 边的图称为无向图。每一条边都足有向边的图称为有向图。 3 关联与邻接 在一个图中，若两个顶点由一条有向边或一条无向边关联，则称这两个顶点 是两邻接点。类似的，关联于矧一顶点的两条边称为邻接边f 1 9 。 4 度 6 华东师范大学硕士学位论文求图中受顶点数限制的所有塌短路径的算法研究 在无向图中，顶点v 所具有的边的数目称为该顶点的度。在有向图中，顶点 v 的度又分为入度和出度，以顶点v 为终点( 头) 的入边的数目，称为该顶点的 入度。以顶点v 为始点( 尾) 的出边的数目，称为该顶点的出度。一个顶点的入 度和出度的和为该顶点的度。 5 完全图 若无向图中的每两个顶点之间都存在着一条边，有向图中的每两个顶点之间 都存在着方向相反的两条边，则称此图为完全图f 2 0 】。 6 路径 在无向图g = ( ve ) 中，顶点交替序列( v i ，v 。， v j ) 称为从顶点v i 到顶点v j 的一 条路径。 如果是有向图，则路径也是有向的，路径的长度是指路径上的边或弧的数目。 序列中第一个顶点和最后一个顶点相同的路径称为回路或环。 序列中顶点不重复出现的路径称为简单路径1 2 1 。 7 连通 在无向图中，如果从顶点v i 到顶点v j 有路径存在，则称v j 和v j 是连通的。 图中任意两个顶点都连通的无向图称为连通图。 在有向图中，如果从顶点v j 到顶点v j 有路径存在，则称v i 相对于v i 是连通 的。图中的每一对顶点都连通的有向图称为强连通图。 8 权与网 图中每一条边都可以附有一个对应的数，则这种与连接顶点v i 和v i 的边或 弧相关的数w ( v l , 。i ) 就称为边或弧的权。权可以表示从一个顶点到另一个顶点的 距离或花费的代价。边上带有权的图称为带权图，也称作网【2 0 】。 权可以用来描述一个项点到另一个顶点的距离或费用。如果把道路交通网中 的道路起点，终点和交叉口表示为顶点，把道路表示为连接点的弧，把道路的长 度，通行时间等属性表示为道路的权，那么道路网就被抽象为带权的图，而与之 相关的问题就可以利用图论的方法进行分析。 9 生成树与生成森林 连通图的生成树是一个极小连通子图，它包含图中全部n 个顶点和n 1 条不 构成回路的边。 非连通图的生成树则组成一个生成森林。若图巾有n 个顶点，m 个连通分量， 则生成森林中有n m 条边1 2 2 。 2 2 最短路径问题 最短路径问题可分为蕾源最短路径1 u j 题及全源最短路径问题两种。其中单源 华东师范大学硕士学位论文求图中受顶点数限制的所有最短路径的算法研究 最短路径问题更具有普遍意义，且可为全源最短路径问题提供良好的借鉴方案。 单源最短路径问题的算法有很多种，从早期的基于限制条件的深度优先搜索 算法，基于有向无环图的动态规划法，基于邻接矩阵的d i j k s t r a 算法，到最大相 关边法，最大相关点法，基于邻接表的d i j k s t r a 算法，a 算法等。针对不同的网 络特征，应用需求及具体的软硬件环境，各种算法在空间复杂度，时间复杂度， 易实现性等方面各具特色。 采用贪心及启发策略的d i j k s t r a 算法是目前已知的理论上最完善的算法，它 以极强的抗差性而得到广泛的应用。d i j k s t r a 算法的执行过程产生了以s 为根结 点的一棵树，随着算法的逐步执行，该树向四面八方延伸，直至达到顶点t 为止。 显然，有些分支的产生无益于最短路径的求得，如果能够及早的删去某些多余的 分支，就可以减少计算最短路径所需要的时间，降低算法时间复杂度 2 3 1 。 加权有向图中的每条路径都有相关的“路径权”，其值为该路径上边的权值 之和。这个基本度量标准使我们能将这种问题描述为“找出两个给定顶点问权值 最小的路径”，并将它称为“最短路径问题”。最短路径问题不仅在许多直接应用 中相当直观，而且还可引导我们进入一个强大而通用的领域，即我们可以寻求高 效算法来解决涵盖大量特定应用的一般问题。 在图中求解最短路径时，其自身存在一些特性，这里以定义和引理的形式给 出，定义都比较简单，在此不再赘述。 定义2 1 在一个网中，两个顶点s 和t 之问的一条最短路径( s p ) 是从s 到t 的一条有向简单路径，而且此路径有以下属性，即不存在另外一条这样的路径且 有更小权值。 定义2 2 源点终点最短路径是给定个起始顶点s 和一个结束顶点t ，在图 中找出从s 到t 的一条最短路径。 定义2 - 3 单源最短路径是指给定一个起始顶点s ，找出从s 到图中其它各顶 点的最短路径。 定义2 4 全源最短路径是指找出连接图中任意一对顶点之间的最短路径。 定义2 5 给定一个网和一个指定的顶点s ，则s 的最短路径树是一个包含s 以及由s 可达的所有顶点的子网，它构成以s 为根的一棵有向树，其中每条树路 径都是嘲中的一条最短路径 2 4 1 1 2 5 1 。 引l 哩2 1m 权图g 中，如果p ( i ) 是v i 到v i 的最短路径，且v i p ( j ) ，则p o ) 是v 】到v i 的一条最短路径。 证明：如果p o ) 不是最短路径，则存在一条最短路径p ( j ) ，使d ( i ) d ( i ) ，这样 d ( i ) = d ( j ) + 如：i ) d ( i ) + 如，i ) ，与p ( i ) 是最短路径矛质1 2 1 1 1 4 】。 8 华东师范大学硕士学位论文求图中受顶点数限制的所有最暂路径的算法研究 2 3 求解最短路径常用算法 最短路径问题的核心就是生成树的计算。目前生成树的计算方法总体来说可 以分为最短路径树算法、最小生成树算法以及s t e i n e r 树的启发式算法。 2 3 1 最短路径树算法 最短路径树算法的思想比较简单，其目的是使最终计算所得的生成树实现从 源点到目的结点的路径都是最短路径。 d i j k s t r a 算法和f l o y d 算法是目静两个比较著名的最短路径算法。当使用最 短路径树算法时，对于有n 个目标结点的生成树计算，只需要应用n 次最短路径 算法即可，可见该算法比较简单。该算法虽然得到源点到目的结点的最短路径， 但是对于整个生成树来说往往在路径共享方面达不到好的效果。 d i j k s t r a 算法又称为标号法，是1 9 5 9 年由荷兰计算机科学家e w d i j k s t r a 提出的关于最短路径的搜索算法。应该说，这种方法至今仍然被公认为是解决从 固定点出发到网络中的任意结点的最短路径问题的较好的方法之一。 d i j k s t r a 算法是解决关于带权图的最短路径问题的一种贪心算法，它要一个 个的找出从源结点s 出发到所有其它结点的最短路径。其本质特征是能够确定路 径顺序，按照加权长度顺序首先找出最短路径，直至最后找出从源结点到所有结 点的最短路径中最长的那一条最短路径1 2 】。现在许多计算机实现的最短路径算 法都是在d i j k s t r a 算法的基础上，运用关联矩阵、邻接矩阵的概念，使得存储网 络数据和运算时，都需要定义n n ( n 为网络结点数) 的矩阵。当网络的结点数 较大时，将占用大量的存储空问，并且运算也很浪费时l - 日j 。d i j k s t r a 算法中共用 到两次循环，总的时问复杂度为o ( n 2 ) 。但若要找出每一对结点间的最短路径， 则需要执行改算法n 次，其时i 日j 复杂度为o ( n 3 ) 。所以，对d i j k s t r a 的改进算法 通常集中在对空| b j 拓扑结构的表示和处理上，如将基于邻接矩阵的算法改进为基 于相关矩阵1 2 6 1 ，对于优先级队列进行处理，采用二叉堆结构代替线性数组等等 1 1 7 1 1 2 3 1 。这样的改进，在没有改变d i j k s t r a 算法的基本思想上，提高了算法的效 率，是进行最短路径搜索的实用算法。 f l o y d 算法是山计算机科学家f o l y d 提出的。该算法能够求得任意结点之| 日j 的最短路径，其基本思想足递推的产生一个矩阵序列a ( m ，a ( ”，a i ，a f ”， a i ”，其中a o ) 为给定的代价矩阵，a ( k ( 1 i ，j n ) 表示从顶点i 到顶点j 的中问 顶点序号不大于k 的最短路径的长度。f l o y d 算法给出的计算a k ( i ，j ) 的递推公式 如下： 9 华东师范丈学硕士学位论文求图中受顶点数限制的所有晟短路径的算法研究 a o ( f ，) = c o s t ( i ，) a a ，) 一m i n o k - 1 ) g ，j ) ，a ( k - 1 ) ( f ，七) + 4 ( k - i ) ( 是，) 1 s k5 n 但是f l o y d 算法需要三层循环，所以总的时间复杂度是0 ( n 3 ) 2 5 。 2 3 2 最小生成树算法 最小生成树算法是针对整个网络结点而言的。p r i m 和k m s k a l 算法是两个较 为著名的最小生成树算法。p r i m 算法的特点是当前形成的集合t 始终是一棵树。 将t 中u 和t e 分别看作红点和红边集，v - u 看作蓝点集。算法的每一步均是在 连接红、蓝点集的紫边中选择一条轻边扩充进t 中。m s t 性质保证了此边是安 全的。t 从任意的根r 开始，并逐渐生长直至u = v ，即t 包含了c 中所有的顶 点为止。m s t 性质确保此时的t 是g 的一棵m s t 。因为每次添加的边是使树中 的权尽可能小，因此这是一种”贪心”的策略【2 7 】。p r i m 算法的时间复杂度为o ( n 2 ) ， 与网中的边数无关，因此适用于求边稠密的网的最小生成树【2 5 】。k r u s k a l 算法的 基本思想是先选取路径代价小的为边，同时以选取路径时不能形成回路为约束。 k r u s k a l 算法的时间复杂度为o ( e l o g e ) ( e 为网中边的数目) ，因此，相对于p r i m 算法而言，适合于求边稀疏的最小生成树。 2 3 3s t e i n e r 树的启发式算法 搜索可以分为盲目搜索和启发式搜索两种。盲目搜索是按照预定的控制策略 进行搜索，在搜索过程中获得的中f 日j 信息不用束改进控制策略。d i j k s t r a 算法和 f l p y d 算法都是盲目搜索算法。 启发式搜索是在搜索中加入了与问题有关的启发性信息，用以指导搜索朝着 最有希望的方向i ；i 进，加速问题的求解过程并找到最优解。启发式搜索有很多算 法，努l 局部择优搜索法、最好优先搜索法等等。对于状态空例搜索问题，启发式 搜索过程就是在状态空问中对每一个搜索的位置进行评估，得到最好的位置，再 从这个位置进行搜索直到目标。对于不同的算法，在搜索过程中选择结点的策略 不同。 当，e 成树的计算以最小化整个生成树的耗费为目标时便归结为寻找s t e i n e r 树问题。一般t 古况下这是个n p 问题，为降低算法难度现在研究的算法基本都 是启发式算法。h 酊的s t c i n e r 树l u j 题的启发式算法有很多，如a + 算法、k m p 算法、m p h 算法、b s m a ( b o u n d e ds h o r t e s tm u l t i c a s ta l g o r i t h m ) 算法、k o m p e l l a 算法和a d h 罅法等等。 1 0 华东师范大学硕上学位论文求图中受顶点数限制的所有最短路径的算法研究 a + 算法作为在最短路径问题中应用的较多的启发式搜索算法，其运行效率 较高，启发函数的设计可以避免大量的无关结点的搜索和回溯，算法的时间复杂 度为o ( n ) 。k m p 算法由k o u ，m a r k o u s k y 和b e r m a n 提出的一种启发式算法1 2 8 】。 k m p 算法首先构造包含成员结点的完全图。然后计算完全图的最小生成树，最 后进行相应的替换来计算组播树。m p h 算法的基本思想是先任选一组需求结点， 然后计算它们到源点的最短路径，设其为t ；在此基础上，不断以到达已经算得 的生成树t 的最短路径为依据来添加树枝，直到把所有的目标结点都添加到生成 树中。m p h 算法与p r i m 算法相似，两者最大不同是m p h 算法是计算生成树， 而p r i m 算法是计算最小生成树。 2 3 4 其他常用方法 最短路径问题是一种最优化问题，而动态规划算法是求解最优化问题的一种 较好的方法，因而可以利用动态规划方法来求解。注意解决路径的分阶段搜索策 略和搜索状态的表示两个问题，就可以利用动态规划方法，进一步改进最短路径 问题的求解算法。 此外，对于最短路径问题的研究，还可以采用遗传算法，蚂蚁算法，神经元 动态规划等多种算法。 2 4 受限制的最短路径算法 前面已经介绍过图的基本概念和最短路径常用算法，但是作为图中研究热点 问题之一，最近还提出了许多新的研究问题，如受限制的最短路径问题、图中所 有最短路径问题和k 短路径问题等。本节：要介绍图中受顶点数限制的最短路 径问题，主要有周经纶等提出若干个受顶点数限制的最短路径问题，下面简称周 算法；孙强等提出的求受顶点数限制的最短路径问题的一个算法，下面简称孙算 法；钟予飞等提出的一种求受顶点数限制的最短路径的新算法，下面简称钟算法 等。 1 周算法 1 9 9 6 年，周经纶i l j 】等较早的提出了受顶点数限制的最短路径问题。周算法 先提出三个受顶点限制的最短路径问题，整篇文章嘲绕这三个问题展丌： ( 1 ) 受顶点数k 限制的最短路径问题。 在g 中找一条从s 剑t 的只，使得c ( 只，) = m ，i 。n ，c ( 只) 而且满足约束 华东师范大学硕士学位论文求图中受顶点数限制的所有最短路径的算法研究 ( 只) 七，其中k 是给定的正整数，p 是g 中所有从s 到t 的路径集合。 ( 2 ) 最小顶点数的最短路径问题。 在g 中找一条从s 到t 的只，使得( 匕) = m 巳。i n ，( 己) 而且满足约束 c ( 只) = m 匕i 。n ，c ( 只) ，其中，p 是g 中所有从s 到t 的路径集合 ( 3 ) 最大顶点数的最短路径问题。 在g 中找一条从s 到t 的只，使得( 只) 2 鼍咎( 只) 而且满足约束 c ( 只) ；m ，i 。n ，c ( 只) ，其中，p 是g 中所有从s 到t 的路径集合。 然后引入非支配路的概念并对其性质定理加以证明，在此基础上用双标号和 取字典序最小方法，给出求解问题的多项式算法；特别值得说明的是周算法还对 算法的可行性进行了理论证明和实例演示。 但是周算法的算法时间复杂度较大，为o ( n 3 l o g n ) ( n 为图中顶点数) 。且周 算法使用了几种标号，存储结构比较复杂，这使得周算法的描述和实现较为复杂。 2 孙算法 2 0 0 2 年，孙强i 1 0 1 等提出一种新的求解受顶点数限制的最短路径问题的算 法。孙算法的核心思想在于下面两个等式。 d i s t l j c o s t s l j 】 ( 1 ) d i s t j 1 = m i n d i s t i ”1 + c o s t l l l j ( 2 ) 其中，1 i n ，1 j n ，0 m k 一2 ；d i s t j ”表示从源点s 出发经过最多n 1 个中问顶点( 不包括源点和终点) 最后到达顶点j 的最短路径的长度。等式( 1 ) 表示从源点s 出发在经过的中l 日j 顶点个数等于0 这个限制条件下到达顶点j 的最 短路径长度为c o s t i j 。等式( 2 ) 的证明可以参考文献 】0 ，借助于等式( 2 ) ， 就可以很容易求解从源点到顶点j 的最短路径。 相对于周算而言，孙算法的特点是： ( 】) 算法效率有明显提高，实际时| 日j 复杂度为0 ( ( k - 2 ) i 1 二) ( k 为受限制顶点 数，k n ) 。 ( 2 ) 比较简单，易于描述、实现和理解。 3 钟算法 2 0 0 4 年，钟子飞1 1 6 】等提出一种求受顶点数限制的最短路径的新算法。钟算 华东师范大学硕上学位论文求图中受顶点数限制的所有屉短路径的算法研究 法的思想是采用逆邻接表作为存储结构，将算法的核心操作建立在有直接通路的 顶点之上，而同类算法大多把算法的核心操作建立在所有顶点之上。由于钟算法 建立在逆邻接表的基础上，因此算法循环只考虑那些与顶点v ；有直接通路的顶 点，从而使得钟算法的时间复杂度为o “k 2 ) w ) ( w 为有向图中弧的总数) 。 对于图中任何一个顶点，在其周边与其直接连通的顶点是不多的，即在网络 系统所对应的一个有向图中，对任意的一个项点v i ，它只与其它少数的顶点有直 接通路，也就是只有很少的顶点v i 能满足使两点之间的路程c o s t i j m a x ( m a x 为一个极大的数，c o s t i l j = m a x 则表示两顶点之闻没有直接通路) 。而在实际网 路系统中，站点总数n 非常庞大，以至于