（计算数学专业论文）最短路径算法分析与应用——城市公交网络咨询系统.pdf

摘要 中文摘要 目前在g i s 领域，对最短路径搜索问题的研究和应用较多，其中最短路径搜 索算法的效率问题是普遍关注和在实际应用中迫切需要解决的问题，图论中的 节点间求解的最短路径问题旨在寻找两个结点问的最短路径。 本文通过对常见的几个有关最短路径算法的分析，即经典的d i j k s t r a 算法、 b e l l m a n - f o r d 算法、f l o y d 算法等。讨论了各个算法的思想、实现方法、数据结 构及算法描述，并从时间和空间的复杂度进行分析比较其优缺点和具体的实用 性。针对交通网络本身的特点的分析与研究，介绍了一些适合道路网络的经典最 短路径算法和数据存储模式，探讨了在交通网络路线优化过程中需要特别处理 的几个问题，并在理论上给出了相应的解决方案。 最后特别针对现代城市交通现状，目前面临着的问题，即城市私家车的增 加和城市交通运输的发展，造成交通拥挤、道路阻塞和交通事故正越来越突出 等诸多，所以积极发展公交事业尤为重要。而考虑乘客乘车出行实际心理，即 尽量缩短时间、缩短路程和缩小费用，最终归结为图论中最短路径问题，即建立 一个交通咨询系统，采用图的结构表示实际的交通网络，图中顶点表示站点， 边表示站点间的交通联系，该系统用来回答乘客提出查询问题。 本文现以张家口局部路段为例，通过对算法的分析，设计运用f l o y d 算法， 以v c + + 为设计平台，建立了一个简单城市公交系统，程序调试成功，基本达到 了简单查询目的，即实现两站点间的最短路径查询，以方便人们的出行。 关键词：交通网络最短路径d i j k s t r a 算法f l o y d 算法 堡堕竺l a b s tr a c t n o w 础【y si nt h ef i e l do fg i s ，p e o p l es p e n dag r e a td e a lo fe n 唧o n 也e r c s e 甜c ha l l da p p l i c a t i o no ft h es e a r c ho f t h es h o r t e s tp a t h ，0 f 、h i c ht h ee f f i c i e n c vo f 也ec a l c u l a t i o no ft h es h o r t e s tp a t hi s g e n e r a l l yf i x e do n 椰r e q u i 川t ob es o l v e d t h es o l u t i o no ft h es h o r t e s tp a t ho nt h ef i g u r ea n dd i a 蹦l m i sm a i n l yb ym e a n so f s e a r c h i n gf o r t h es h o r t e s tp a t hb e t w e e nt w op o i n t s l i lt h l 8c s s a y , a l lt h et h o u g h t s ，m e a n s ，d a t as t r u c t u r e sa n d c a l c u l a t i o nd e s c r i p t i o n a r ed l s c u s s e d t h r o u g hs e v e r a lc o m m o na n a l y s e so f t h ec a l c u l a t i o no f t h es h o r t e s tp a m ， n 锄e l y , d i j k s t r a , b e l l m a n - f o r d ，f l o y da n ds oo n a n dt h ec o m p l i c a t i o ni nt i m ea 1 1 d s p a c e1 sa 1 1 a y z e da n dc o m p a r e di nt h ea d v a n t a g e sa n d p r a c t i c a lp o i l l t s 嘲d n gt h e c n 撇c t e r i s t i c s ，a n a l y s e sa n dr e s e a r c h e so ft r a f f i cn e t w o r ki n t o c o n s i ( 1 e r a t i o n 廿l i s e s s a ym t r o d u c e ss o m et y p i c a lm e a n so ft h ec a l c u l a t i o no f t h es h o r t 髓tp a t ha n dd a t a s t o r c ，d l s c u s s e ss o m ep r o b l e m se x i s t i n gi nt h ec o u r s eo f o p t i m i z i n ga n dg i v e ss 嘞e s c h e m e so f s o l v i n gt h ep r o b l e m si nt h e o r y r 1 n a l l y ，a c c o r d i n gt ot h et r a f f i cc o n d i t i o n sa n dt h ee x i s t i n gp r o b l e i n s ，n 锄e l y t h e m c r e a s eo ft h ep r i v a t ec a r si nc i t i e sa n dt h ed e v e l o p m e n to f t r a n s p o r t a t i o n ，c a u s i n g 啪、砌e d t r a n 8 0 0 pr t a t i o na n dt r a f f i cj a m s ，t h e d e v e l o p m e n to fp u b l i c 椭r sa r e e s p e c l a l l y1 m p o n a n t h o w e v e r , c o n s i d e r i n gt h er e a lt h o u g h t so f t h ep a s s e n g e r s ，t l l a ti s 钍1 el e a s tt i m e t h es h o r t e s tp a t ha n d t h el o w e s tc o s t ，t h ep r o b l 锄c o m e st 0o n e p o i n t ： t h es h o r t e s tp a t hi nt h ef i g u r ea n d d i a g r a m b u i l dat r a f f i cc o u n s e l i n gs y s t 锄a n du s e d l a g r 锄st oi n d i c a t et r a f f i cn e t w o r k ，t h et o p si nt h ed i a g r a m si n d i c a t i n gs t o p s ，e d g e s m d i c a t i n gt r a 伍cc o n n e c t i o n sb e t w e e ns t o p s i nt h i s e s s a y , w et a k ez h a i l 西i a k o u s e e t i o nf o re x a m p l e ，w ed e s i g nf l o y d s y s t e mb ya n a l y z i n gt h ec a l c u l a t i o n s w 曲u i l d as l m p j eu r b a l lp u b l i ct r a n s p o r t a t i o ns y s t e mo nv c + + d e s i g n t h ep r o 伊a mi s 仃i e d s u c c e s s f u l l y , r o u g h l ya c h i e v i n gi t sa i m so fs i m p l ei n t e r r o g a t i o n ，n a m e l ya c h i c v i n gt h e i n t 蛳g a t i o no ft h es h o r t e s tr o u t eb e t w e e nt w o s t o p s ，t ol e t p e o p l e脚e 1 c o n v e n i e n t l y k 叼例o r d s ：t r a f f i cn e t w o r k ；t h es h o r t e s t p a t h ；d i j k s t r aa l g o r i t h m ；f i o y da i g o 枷1 i i l i i + 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者躲榕拇 _ 砷年z 月1 日， 经指导教师同意，本学位论文属于保密，在 年解密后适用本授权书。 指导教师签名：学位论文作者签名： 祷牟韵 解密时间：年月 日 各密级的最长保密年限及书写格式规定如下： 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作善签名： 磷韵 唧年j 月日 第一章引言 第一章引言 二十世纪中后期，随着计算机的出现和发展，图论的研究得到广泛重视， 最短路径问题是图论中的一个典范问题，它已经被应用于计算机科学、运筹学、 地理信息科学等众多领域。最短路径问题最直接的应用当数在地理信息领域， 如：g i s 网络分析、城市规划、电子导航等。在交通咨询方面，寻找交通路网中 两个城市间最短的行车路线就是最短路径问题的一个典型的例子。在网络通信 领域，信息包传递的路径选择问题也与最短路径问题息息相关。举个例子，o p s f 开放路由选择协议，每个o p s f 路由器都维护一个描述自治系统拓扑结构的数据 库，通过这个数据库构建最短路径树来计算路由表，从而跟踪自治系统范围内 到每个目标的最短路径。在图象分割问题中，最短路径也有直接的应用：在语 音识别中，一个主要的问题就是别同音词，例如，t o 、t w o 、t o o 。为解决这个 问题，我们需要建一个图，顶点代表可能的单词，边连接相邻的单词，边上的 权代表相邻的可能行大小。这样图中的最短路径，就是对句子的最好解释。 由于最短路径问题的广泛应用，很多学者都对此进行了深入的研究，也产 生了一些经典的算法。近些年来，对最短路径研究的热度依然不减，并且时间 复杂度降得越来越低。针对串行计算机的最短路径算法，已经几乎到达理论上 的时间复杂度极限1 。在具体的应用中，一个算法的优劣需要考虑的因素包括空 间复杂度，时间复杂度等。文献 2 对当前的最短路径算法体系进行了很好的总 结，从实际意义上来讲，没有哪种算法能够使所有的网络形式都具有很好的空 间和时间复杂性。按照起终节点及路径的数目和特征【2 h 3 1 ，最短路径问题分为 五种类型：即两个节点间的最短路径、所有节点的最短路径、k 则最短路径、实 时最短路径和指定必经点的最短路径问题其中又可衍生出其他一些特殊的最 短路径问题，如限制弧段数目最短路径、含环最短路径等。在交通网络的路径分 析中，单源最短路径问题更具有普遍意义，其算法有很多种，其中采用贪心及 启发策略的d i j k s t r a 算法是目前最完善的【2 】，这是荷兰计算机科学教授e d g e rw d i j k s t r a ( 1 9 3 0 ) 在1 9 5 9 年发现的个算法，它以极强的抗差性而得到普及和应用。 在基于交通网络的路径分析算法中，大都以d i j k s t r a 算法作为基础并根据交通网 络的特性进行改进。再有就是由弗洛伊德( f l o y d ) 提出的另一个算法，又称传 递闭包方法，求每一对结点之间的最短路径，当然还有在此基础上的其他一些 第一章引言 改进算法也很多p 。 本文就从上述几类来分别介绍最短路径的几种常用算法，并介绍最短路径 问题中的算法改进。本文的其它部分组织如下：第二章介绍图论有关的基本知 识，主要是图的基本概念，存储方式。第三章介绍最短路径问题的几种算法； 第四章是最短路径算法的一个重要应用，即城市公交咨询系统；第五章为总结， 提出文章的缺点与不足之处，谈谈自己的想法，并提出发展期望。 2 第二章预备知识 第二章预备知识 图( g r a p h ) 是一种复杂的非线性结构。在人工智能、工程、数学、物理、化 学、生物和计算机科学等领域中，图结构有着广泛的应用。 本章先介绍图的概念，再介绍图的主要存储方法，参看 5 - 7 。 2 1 1图的二元组定义 第一节图的基本概念 图g 由两个集合v 和e 组成，记为：g = ( v ，e ) ，其中：v 是顶点的有穷 非空集合，e 是v 中顶点偶对( 称为边) 的有穷集。 通常，也将图g 的顶点集和边集分别记为v ( g ) 和e ( g ) 。e ( g ) n - - j 以是空集。 若e ( g ) 为空，则图g 只有顶点而没有边。 2 1 2 有向图 若图g 中的每条边都是有方向的，则称g 为有向图( d i g r a p h ) ( 1 ) 有向边的表示 在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括 号表示。有向边也称为弧( a r c ) ，边的始点称为弧尾( t a i l ) ，终点称为弧头( h e a d ) 。 【例】 表示一条有向边，v i 是边的始点( 起点) ，v j 是边的终点。因此， 和 是两条不同的有向边。 ( 2 ) 有向图的表示 【例】下面( a ) 图中g l 是一个有向图。图中边的方向是用从始点指向终点的箭 头表示的，该图的顶点集和边集分别为： v ( g d = v l ，v 2 ，v 3 e ( g 1 ) = ， ， ) 2 1 3 无向图 3 第二章预备知识 若图g 中的每条边都是没有方向的，则称g 为无向图( u n d i g r a p h ) 。 ( 1 ) 无向边的表示 无向图中的边均是顶点的无序对，无序对通常用圆括号表示。 【例】无序对( v i ，v j ) 和“，v i ) 表示同一条边。 ( 2 ) 无向图的表示 【例】下面( b ) 图中的g 2 和( c ) 图中的g 3 均是无向图，它们的顶点集和边集分别 为： v ( g 2 ) - v i ，v 2 ，v 3 ，v 4 e ( g 2 ) = ( v l ，v 2 ) ，( v l ，v 3 ) ，( v l ，v 4 ) ，( v 2 ，v 3 ) ， v ( g 3 ) = v l ，v 2 ，v 3 ，v 4 ，v 5 ，v 6 ，v t e ( g 3 ) = ( v l ，v 2 ) ，( v l ，v 3 ) ，( v 2 ，v 4 ) ，( v 2 ，v 5 ) ， ( v 2 ，v 4 ) ，( v 3 ，v 4 ) ) ( v 3 ，v 6 ) ，( v 3 ，v 7 ) 第二节图的存储结构 图的存储表示方法很多，这里介绍两种最常用的方法。至于具体选择哪一 种表示法，主要取决于具体的应用和欲施加的操作。 为了适合用c 语言描述，以下假定顶点序号从o 开始，即图g 的顶点集 的一般形式是v ( g ) = v 。，v 。，v 。一。) 。 2 2 1图的邻接矩阵表示法 在图的邻接矩阵表示法中： 第二章预备知识 用邻接矩阵表示顶点间的相邻关系 用一个顺序表来存储顶点信息 一 图的邻接矩阵( a d a c e n c ym a t ri ) 设g = ( v ，e ) 是具有1 1 个顶点的图，则g 的邻接矩阵是具有如下性质的n 阶 方阵： 仝吐舻 三喜 z 善耄溉誓京警暑苗篇边 【例】下图中无向图g 4 和有向图g 5 的邻接矩阵分别为a l 和a 2 。 l01 11 i l10 11 4 2 l1 1oo l i1100 翔 v 3 v l 4 = o10 0 0 1o001 olol0 1o o00 o o o10 警2 v 耋v 3 图2 2 无向图g t 有向图g 5 二 网络的邻接矩阵 v 2 若g 是网络，则邻接矩阵可定义为： 雄刃* 荔纛0 ：三：二 其中： w ；，表示边上的权值； 表示一个计算机允许的、大于所有边上权值的数。 【例】下面带权图的两种邻接矩阵分别为a 。和a 4 。 5 第二章预备知识 v 13v 2 一 v 5 兰呈至三毒_ ： 兰主三三圣 2 2 2图的邻接矩阵存储结构形式说明 # d e f i n em a x v e r t e x n u m1 0 0 最大顶点数，应由用户定义 t y p e d e fc h a rv e r t e x t y p e ； 顶点类型应由用户定义 t y p e d e fi n te d g e t y p e ；边上的权值类型应由用户定义 t y p e d e fs t r u c t v e x t e x t y p ev e x s m a x v e r t e x n u m 顶点表 e d e t y p ee d g e s m a x v e r t e x n u m m a x v e r t e x n u m ： 邻接矩阵，可看作边表 i n tn ，e ； 图中当前的顶点数和边数 ) m g r a g h ； 注意： 在简单应用中，可直接用二维数组作为图的邻接矩阵( 顶点表及顶点 数等均可省略) 。 当邻接矩阵中的元素仅表示相应的边是否存在时，e d g e t y p e 可定义为 值为0 和1 的枚举类型。 6 第二章预备知识 无向图的邻接矩阵是对称矩阵，对规模特大的邻接矩阵可压缩存储。 邻接矩阵表示法的空间复杂度s ( n ) = 0 ( n 2 ) 。 2 2 3 图的邻接表表示法 图的邻接表表示法类似于树的孩子链表表示法。对于图g 中的每个顶点v ；， 该方法把所有邻接于v ；的顶点v ，链成一个带头结点的单链表，这个单链表就称 为顶点v ；的邻接表( a d j a c e n c yl i s t ) 。 一邻接表的结点结构 ( 1 ) 表结点结构 邻接表中每个表结点均有两个域： 邻接点域a d j v e x 存放与v ；相邻接的顶点v ，的序号j 。 链域n e x t 将邻接表的所有表结点链在一起。 注意： 若要表示边上的信息( 如权值) ，则在表结点中还应增加一个数据域。 ( 2 ) 头结点结构 i v e r t e x i f i r s t e d g e i 项点v 。邻接表的头结点包含两个域： 顶点域v e r t e x 存放顶点v ；的信息 指针域f i r s t e d g e v ；的邻接表的头指针。 注意： 为了便于随机访问任一顶点的邻接表，将所有头结点顺序存储在 个向量中就构成了图的邻接表表示。 有时希望增加对图的顶点数及边数等属性的描述，可将邻接表和 这些属性放在一起来描述图的存储结构。 7 第二章预备知识 二 无向图的邻接表 对于无向图，v ；的邻接表中每个表结点都对应于与v ；相关联的一条边。因 此，将邻接表的表头向量称为顶点表。将无向图的邻接表称为边表。 【例】对于无向图g 。，其邻接表表示如下面所示，其中顶点v 。的边表上三个表 结点中的顶点序号分别为l 、2 和3 ，它们分别表示关联于v 。的三条边( v 。，v 。) ， ( v o ，v 0 和( v o ，v 3 ) 。 v 3 纷场 v o v l v 2 v 3 顶点袭 巳 卜臣丁卜e 丑勾 臣丑卜臣丁卜e 丑圈 臣丑卜口 勾 臣丑卜巳 圈 边袭 图2 4 无向图g s 邻接表 注意： n 个顶点e 条边的无向图的邻接表表示中有f i 个顶点表结点和2 e 个边表结 点。 三 有向图的邻接表 对于有向图，v i 的邻接表中每个表结点都对应于以v i 为始点射出的一条边。 因此，将有向图的邻接表称为出边表。 【例】有向图g 6 的邻接表表示如下面( a ) 图所示，其中顶点v 1 的邻接表上两个表 结点中的顶点序号分别为0 和4 ，它们分别表示从v l 射出的两条边( 简称为v l 的 出边) ： 和 。 v 2 8 第二章预备知识 四i 3 i 1 詈匪孽i 雾；i ai 箍点瓷国地袭。瑗点澎入边袭 ，( a ) 硒昀邻较裳4 轴) 铂的娆邻壤寝 图2 5 有向图g 。，邻接表及其逆邻接表 注意： n 个顶点e 条边的有向图，它的邻接表表示中有n 个顶点表结点和e 个边表结点。 2 2 4邻接表的形式说明 t y p e d e f s t r u c tn o d e j e - 蔓表结点 i n ta d j v e x ；邻接点域 s t r u c tn o d e * n e x t ；链域，若要表示边上的权，则应增加一个数据域 e d g e n o d e ； t y p e d e f s t r u c tv n o d e 顶点表结点 v e r t e x t y p ev e r t e x ； 顶点域 e d g e n o d e * f i r s t e d g e ；边表头指针 v e r t e x n o d e ； t y p e d e f v e r t e x n o d ea d j l i s t m a x v e r t e x n u m ；a d j l i s t 是邻接表类型 t y p e d e fs t r u c t a d j l i s ta d j l i s t ；邻接表 i n t n ，e ；图中当前顶点数和边数 a l g r a p 对于简单的应用，无须定义此类型，可直接使用a d j l i s t 类型。 注意： 建立有向图的邻接表更简单，每当读入一个顶点对序号 v 。路径长度修改) 向量d ， abcdef s 巨工互匝工卫 d 匡工丑至巨王丑 求得m i n d ： 2 3 ，1 2 ，2 5 ， = 1 2 ，最短路径v p 一 v b 一 v c 以d j 修改( 即v f 一 v b 一 v c 路径长度修改) 向量d ， abcne f s d 求得m i n d = 2 1 ，2 5 ，) = 2 1 ，最短路径v f 一 v b 一 v c 一 v 以d j 修改( 即v f 一 v b 一 v c 一 v 路径长度修改) 向量d ， abcdef s d 求得m i n d ) = 2 5 ，o o ) = 2 5 ，最短路径v f 一 v d 1 3 第三章最短路径常用算法 ( 墨) 以dl j j 修改( 即v r 一 v o 路彳仝长度修改) 向量d ， abcdef s 臣工三正碉 d 巨工丑至叵王珂 求得m i n d = ) = 0 0 ，即v p 一 v e 无路径 经过n 1 次操作，将最后一条路径添加到s 中，结束。 bcnrf s d 三 数据结构 ， 木用邻接矩阵表示图g 木用一维数组d i 存放从源点到i 点的最短路径长度或其上界。( 上面算 法中的p 标号与t 标号实际上存放着源点到某点的最短路径长度或其上界，因 此我们可以统一用d 数组来表示) 。 术用一维数组p ，其中p i 记录到i 点的最短路径中前一个顶点的序号。 五算法描述 v o i ds h o r t e s t p a t h d i j ( m g r a p hg ，i n tv 0 ，p a t h m a t r i x p ，s h o r t p a t h t a b l e & d ) 用d i j k s t r a 算法求有向网g 的v 0 顶点到其余顶点v 的最短路径p v 及其带 权长度d v 若p v w 为t r u e ，则w 是v o 到v 的最短路径上的顶点 f i n a l v 为t r u e 当且仅当v es ，即已经求得v o 到v 的最短路径 f o r ( v = 0 ：v g v e x n u m ：+ + v ) f i n a l v = f a l s e ：d v = g a r c s v 0 v ： f o r ( w = 0 ；w g v e x n u m ；+ + w ) p v 儿w = f a l s e ：设空路径 1 4 第三章最短路径常用算法 i f ( d v ( i n f i n i t y ) p v v o = t r u e ：p v i v = t r u e ： d v o = o ：f i n a l v o = t r u e ：初始化，v 0 顶点属于s 集 开始主循环，每次求得v o 到某个v 顶点的最短路径，并加v 到s 集合 f o r ( i = o ：i g v e x n u m ；+ + i )其余g v e x n u m - 1 个顶点 m i n = i n f i n i t y ：当前所知离v o 顶点的最近距离 f o r ( w = o ：w g v e x n u m ；+ 十w ) i f ( ! f i n a l w )w 顶点在v s 中 i f ( d w m i n ) v = w ：m i n = d w ：)w 顶点离v o 顶点更近 f i n a l v = t r u e ；离v 0 顶点最近的v 加入s f o r ( w ：0 ：w g v e x n u m ；+ + w )更新当前最短路径及距离 i f ( ! f i n a l w & ( m i n + g a r c s v w g r a a r c d 】 o 】【a r c d 】 1 】 ) 1 7 第三章最短路径常用算法 ( d i s a r c j 1 = d i s a r c j 0 + g - g r a a r c j 0 a r c j 1 ； s i 9 1 ：钢e ； )如果边j 起点可达，并且经过这条边的路径小于d i s 边j 的终 点】中存储的值，则把较小的值赋值给d i s 边j 的终点】 当搜索到所有的边都不能在当前状况下提供一条更短的路径时，搜索结束 如果d i s i ! = m a x n u m , 贝, 0d i s i 的值就是起点到该点的最短路径 如果d i s i 一- - - - m a x n u m ，则起点与该点不可达 ) 四算法小结 算法时间复杂度o ( v e ) 。因为算法简单，适用范围又广，虽然复杂度稍高， 但因为它实践中的效果不错，仍不失为一个很实用的算法。 第二节每对结点间的最短路径 我们要讨论找出图中每对结点间最短路径问题。这个问题在实践中常常会 出现。例如，对一公路图，要造表说明其上的每对城市间的距离时就可能出现 这种问题。 对于有向图g ( v ，e ，w ) ，要求每对结点间的最短路径，我们可以把单源 最短路径算法运行lv1 次来解决，每次依序把图中的每个结点作为源点。如果 所有边的权为非负，可以采用d i j k s t r a 算法，算法的运行时间为0 ( v 3 ) ；如 果允许有负权边的存在，我们必须对每个结点运行一次速度较慢的 b e l l m a n - f o r d 算法，其中运行时间为0 ( v 2 e ) ，对稠密图则为0 ( v 4 ) 。 下面我们介绍一种动态程序设计方案来解决可以存在负权边但无负回路 的有向图g = ( v ，e ) ，每对结点间的最短路径问题，所产生的算法称为w a r s h a l l 算法，其运行时间为0 ( v 3 ) 。 3 2 1最短路径的结构 在w a r s h a l l 算法中，考察的是一条最短路径上的”中间”结点，其中某条简 单路径p = 的中间结点是p 中除v 。和v j 以外的任何结点，即任何 1 8 第三章最短路径常用算法 属于集合( v ：，v ，v - ) 的结点。 该算法主要基于下列观察。设g 的结点为v = ( 1 ，2 ，n ) ，并对某个k 考察其结点子集( 1 ，2 ，k ) 。对任意一对结点i ，j v ，考察从i 到j 且其 中间结点皆属于集合 l ，2 ，k ) 的所有路径，设p 是其中一条最小权路径 ( 因为我们假定g 中不包含负权回路，所以p 是简单路径) 。f l o y d w a r s h a l l 算法利用了路径p 与从i 到j 间的最短路径( 所有中间结点皆属于集合 ( 1 ，2 ，k - 1 ) 之间的联系。这一联系取决于k 是否是路径p 的一个中间结 点。 如果k 是路径p 的中间结点，我们把p 分解为p 1 ( i - - ) k ) ，p 2 ( k j j ) 。 由前面可知，p ，是从i 到k 的一条最短路径，且其所有中间结构均属于集合 ( 1 ，2 ，k ) 。 事实上，结点k 不是路径p 。的中间结点，所以p ，是从i 到k 的一条最短路 径，且满足所有中间结点均属于( 1 ，2 ，k - 1 ) 。类似地，p ：是从k 到j 的 一条最短路径，且其中间结点皆属于集合( 1 ，2 ，k 一1 ) 。 3 2 2 解决每对结点间最短路径问题的一种递归方案 基于上述观察，我们将给出定义最短路径估计的一个递归公式。设d ：为从 结点i 到结点j 且满足所有中间均属于集合( 1 ，2 ，k ) 的一条最短路径的 权。当k = 0 时，从结点i 到结点j 的路径中根本不存在中间结点，因此它至多 包含一条边， o = w 日，建立权矩阵d o = d = ( d 日) 。，其中 铲臀削v i 瓣 递归定义由下式给出，计算d 似= ( d ：) 删 夸 哼。砖摧， 矩阵给出了最后解，对所有的。i ，j v 成立一一因为其所有中间点皆属于 1 ，2 ，n ) d 佃= ( d 拿) 。 3 2 3 自底向上计算最短路径的权 1