数模专题：图论模型I

1、下下回回停停Konigsberg Konigsberg 七桥问题七桥问题(Leonhard Euler(Leonhard Euler，1707.4.5-1783.9.18)1707.4.5-1783.9.18)下下回回停停A B D C 转化转化 Euler1736年年 B D CA 图论中讨论的图图论中讨论的图 问题：问题：是否能从四块陆地中是否能从四块陆地中的任一块开始，通过每座桥的任一块开始，通过每座桥恰好一次再回到起点？恰好一次再回到起点？是否能从任意一个顶点是否能从任意一个顶点开始，通过每条边恰好开始，通过每条边恰好一次再回到起点？一次再回到起点？转化转化包含两个要素：对象（陆包含两

2、个要素：对象（陆地）及对象间的二元关系地）及对象间的二元关系（是否有桥连接）（是否有桥连接）欧拉指出：如果每块陆地所连接的桥都是偶数座，则从任一陆欧拉指出：如果每块陆地所连接的桥都是偶数座，则从任一陆地出发，必能通过每座桥恰好一次而回到出发地。地出发，必能通过每座桥恰好一次而回到出发地。下下回回停停 四色问题是世界近代三大数学难题四色问题是世界近代三大数学难题之一。（即费马猜想、四色猜想和哥德之一。（即费马猜想、四色猜想和哥德巴赫猜想）巴赫猜想） 四色问题的内容是：任何一张地图四色问题的内容是：任何一张地图只用四种颜色就能使具有共同边界的国只用四种颜色就能使具有共同边界的国家着上不同的颜色。家

3、着上不同的颜色。 它的提出来自英国。它的提出来自英国。1852年，毕业年，毕业于伦敦大学的弗南西斯于伦敦大学的弗南西斯格思里发现了一格思里发现了一种有趣的现象：种有趣的现象：“看来，每幅地图都可看来，每幅地图都可以用四种颜色着色，使得有共同边界的以用四种颜色着色，使得有共同边界的国家都被着上不同的颜色。国家都被着上不同的颜色。”这个现象这个现象能不能从数学上加以严格证明呢？能不能从数学上加以严格证明呢？四色问题四色问题下下回回停停四色猜想的证明四色猜想的证明于1976年由美国数学家阿佩尔(Kenneth Appel)与哈肯(Wolfgang Haken)借助计算机完成，耗时1200小时。185

4、2年10月23日，他的弟弟就这个问题的证明请教了他的老师、著名数学家德摩尔根，摩尔根也没有能找到解决这个问题的途径，于是写信向自己的好友、著名数学家Hamilton爵士请教，但直到1865年哈密顿逝世为止，问题也没有能够解决。德德摩尔根致哈密顿的信（摩尔根致哈密顿的信（1852年年10月月23日）日） 我的一位学生今天请我解释一个我过去不知道，现在仍不甚了了的事实。他说如果任意划分一个图形并给各部分着上颜色，使任何具有公共边界的部分颜色不同，那么需要且仅需要四种颜色就够了下下回回停停 Hamilton问题源于问题源于1856年，英国数学家年，英国数学家Hamilton设计了一个名为周游世界的游

5、戏：他用一个正十二面设计了一个名为周游世界的游戏：他用一个正十二面体的二十个端点表示世界上的二十座大城市（见图），体的二十个端点表示世界上的二十座大城市（见图），提出的问题是要求游戏者找一条沿着十二面体的棱通提出的问题是要求游戏者找一条沿着十二面体的棱通过每个端点恰好一次的行走路线。反映到图论上就是过每个端点恰好一次的行走路线。反映到图论上就是判断一个给定的图是否存在一条含所有顶点的回路。判断一个给定的图是否存在一条含所有顶点的回路。Hamilton回路问题回路问题下下回回停停 18471847年基尔霍夫运用图论解决了电路理论中求解联立年基尔霍夫运用图论解决了电路理论中求解联立方程的问题，引进

6、了方程的问题，引进了“树树”概念。概念。 18571857年年CayleyCayley非常自然在有机化学领域发现了一种重非常自然在有机化学领域发现了一种重要的图，称为要的图，称为“树树”，解决了计算饱和氢化物同分异，解决了计算饱和氢化物同分异构体的数目。构体的数目。 19361936年年, ,哥尼格的第一本图论专著问世哥尼格的第一本图论专著问世, ,才使得图论成才使得图论成为一门独立的数学学科为一门独立的数学学科. . 1946 1946年年, ,随着世界上第一台计算机的问世随着世界上第一台计算机的问世, ,使图论的发使图论的发展突飞猛进展突飞猛进. .下下回回停停 以往数学家习惯将纯数学应用

7、于其以往数学家习惯将纯数学应用于其它学科，它学科，Gowers将图论和组合数学中的将图论和组合数学中的Ramsey理论应用于泛函分析的研究，理论应用于泛函分析的研究，获得了获得了1998年的年的Fields奖。奖。下下回回停停 问题一问题一 （图的几何表示）（图的几何表示） 现有现有6 6个人，任意个人，任意两人之间或者相互认识，或者相互不认识，证两人之间或者相互认识，或者相互不认识，证明这明这6 6个人中，或者有个人中，或者有3 3个人彼此都认识，或者个人彼此都认识，或者有有3 3个人彼此都不认识个人彼此都不认识. .下下回回停停思路思路一一只有只有6个人，人数非常少，可以枚举任意两人之间的

8、个人，人数非常少，可以枚举任意两人之间的关系，然后判断每一种情况是否符合题意。如果所有关系，然后判断每一种情况是否符合题意。如果所有情况都满足，则命题成立。情况都满足，则命题成立。虽然只有虽然只有6个人，但是这样做的时间复杂度可不低，个人，但是这样做的时间复杂度可不低，枚举次数为枚举次数为215 只能借助计算机了。只能借助计算机了。有没有可以直接证明的办法呢？有没有可以直接证明的办法呢？下下回回停停思路二思路二有了图论这个强大的工具有了图论这个强大的工具我们还是像往常一样，以人为顶点，关系为边，建图我们还是像往常一样，以人为顶点，关系为边，建图但是为了以后的直观，这里图的建立有一点小小的不但是

9、为了以后的直观，这里图的建立有一点小小的不同：同：如果两个人之间相互认识，则在这两个人如果两个人之间相互认识，则在这两个人(顶点顶点)间连一间连一条红色边，如果两个人不认识，则在这两个人条红色边，如果两个人不认识，则在这两个人(顶点顶点)间间连一条蓝色边连一条蓝色边(下面会看到这样做的好处下面会看到这样做的好处)那么这样我们就得到了一个由红边和蓝边组成的那么这样我们就得到了一个由红边和蓝边组成的6阶完阶完全图全图我们实际上要证明的就是这个图中或者存在一个红三我们实际上要证明的就是这个图中或者存在一个红三角形角形(认识认识)，或者存在一个蓝三角形，或者存在一个蓝三角形(不认识不认识)下下回回停停

10、任取一个顶点任取一个顶点v0，由它连出，由它连出5条边到其它的顶点，这五条边只有红色和蓝条边到其它的顶点，这五条边只有红色和蓝色两种色两种根据抽屉原理，肯定有一种颜色的边有根据抽屉原理，肯定有一种颜色的边有3条或条或3条以上条以上,不妨设为红色不妨设为红色viv0vjvk如果如果vi,vj,vk之间的边都是蓝边，则图中存在一个蓝三角形之间的边都是蓝边，则图中存在一个蓝三角形如果至少有如果至少有1条为红边，那么它总会与条为红边，那么它总会与v0发出的两条红边组成发出的两条红边组成一个红三角形。一个红三角形。这样就证明了这个命题这样就证明了这个命题下下回回停停问题二（图的代数表示）问题二（图的代数

11、表示） 设某小航空公司在设某小航空公司在4 4城城市之间的航行路线如图所示。某记者从城市市之间的航行路线如图所示。某记者从城市d d出发，问有几条经三次航行到达城市出发，问有几条经三次航行到达城市c c的线路？的线路？下下回回停停解：考察图的邻接矩阵：解：考察图的邻接矩阵：22011111102202011A则则a41(2) = A的第四行与的第四行与A的第一列的乘积的第一列的乘积 = （0 1 1 0）（）（0 1 1 0）T d到到c有航班有航班d到到b有航班有航班b到到a有航班有航班c到到a有航班有航班 =d b a航班航班 d c a航班航班0110101010010110abcdaA

12、bcd下下回回停停一般地一般地aij(k) =从城市从城市i出发经出发经k次航行到达次航行到达j的线路数。的线路数。31331223140221331A于是从于是从d出发经三次航行到达出发经三次航行到达c的线路数为的线路数为a43(3)=3 条条下下回回停停问题三问题三( (关键路径问题关键路径问题) ) 一项工程任务,大到建造一座大坝,一座体育中心,小至组装一台机床,一架电视机, 都要包括许多工序.这些工序相互约束,只有在某些工序完成之后, 一个工序才能开始. 即它们之间存在完成的先后次序关系,一般认为这些关系是预知的, 而且也能够预计完成每个工序所需要的时间. 这时工程领导人员迫切希望了解

13、最少需要多少时间这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目才能够完成整个工程项目, , 影响工程进度的要害工序是影响工程进度的要害工序是哪几个？哪几个？ 图论的基本概念图论的基本概念1) 图的概念图的概念2) 赋权图与子图赋权图与子图3) 图的矩阵表示图的矩阵表示4) 图的顶点度图的顶点度5) 路和连通路和连通1) 1) 图的概念图的概念 定义定义 一个一个图图G是指一个二元组是指一个二元组(V(G),E(G)，其中，其中: 其中元素称为图其中元素称为图G的的顶点顶点.组成的集合，即称为组成的集合，即称为边集边集,其中元素称为其中元素称为边边.),(jivv 定义定义

14、图图G的的阶阶是指图的顶点数是指图的顶点数|V(G)|, 用用来表示；来表示；v图的边的数目图的边的数目|E(G)|用用 来表示来表示. 也用也用来表示边来表示边jivv).,(jivv,)(21vvvGV是非空有限集，称为是非空有限集，称为顶顶点集点集，1)2) E(G)是顶点集是顶点集V(G)中的无序或有序的元素偶对中的无序或有序的元素偶对).,(EVG )(),(GEGVG 表示图，表示图，简记简记 用用 定义 若一个图的顶点集和边集都是有限集，则称若一个图的顶点集和边集都是有限集，则称 其为其为有限图有限图. 只有一个顶点的图称为只有一个顶点的图称为平凡图平凡图，其他的，其他的 所有图

15、都称为所有图都称为非平凡图非平凡图. 定义若若图图G中的边均为有序偶对中的边均为有序偶对,称称G为为有向有向),(jivv边边 为为无向边无向边，称，称e连接连接 和和 ，顶点，顶点 和和 称称图图. 称边称边为为有向边有向边或或弧弧,称称),(jivve 是从是从),(jivve iv连接连接jv，称，称 为为e的的尾尾，称，称 为为e的的头头. ivjv 若图若图G中的边均为无序偶对中的边均为无序偶对 ，称，称G为为无向图无向图.称称jivv为为e的的端点端点. jivve ivjvivjv 既有无向边又有有向边的图称为既有无向边又有有向边的图称为混合图混合图. 常用术语常用术语1) 边和

16、它的两端点称为互相边和它的两端点称为互相关联关联.2)与同一条边关联的两个端点称与同一条边关联的两个端点称为为相邻相邻的顶点，与同一个顶点的顶点，与同一个顶点 点关联的两条边称为点关联的两条边称为相邻相邻的边的边. 3) 端点重合为一点的边称为端点重合为一点的边称为环环， 端点不相同的边称为端点不相同的边称为连杆连杆.4) 若一对顶点之间有两条以上的边联结，则这些边若一对顶点之间有两条以上的边联结，则这些边 称为称为重边重边5) 既没有环也没有重边的图，称为既没有环也没有重边的图，称为简单图简单图 常用术语常用术语6) 任意两顶点都相邻的简单图任意两顶点都相邻的简单图,称为完全图称为完全图.

17、记为记为Kv. 7) 若若 ， ，且且X 中任意两顶点不中任意两顶点不YXGV)(YX ， 相邻，相邻，Y 中任意两顶点不相邻，则称为中任意两顶点不相邻，则称为二部图二部图或或 偶图偶图；若；若X中每一顶点皆与中每一顶点皆与Y 中一切顶点相邻中一切顶点相邻,称为称为完全二部图完全二部图或或完全偶图完全偶图,记为记为 (m=|X|,n=|Y|)nmK,8) 图图 叫做叫做星星.nK, 1:X1x2x3x:Y1y2y3y4y二部图二部图6K:X1x2x3x:Y1y2y3y4y4 , 1K4 , 3K2) 2) 赋权图与子图赋权图与子图 定义定义 若图若图 的每一条边的每一条边e 都赋以都赋以)()

18、,(GEGVG 一个实数一个实数w(e)，称，称w(e)为边为边e的的权权，G 连同边上的权连同边上的权称为称为赋权图赋权图. 定义定义 设设 和和 是两个图是两个图.),(EVG ),(EVG 1) 若若 ,称称 是是 的一个的一个子图子图,记记 EEVV,GG.GG 2) 若若 ， ，则称，则称 是是 的的生成子图生成子图.VV EE GG 3) 若若 ，且，且 ，以，以 为顶点集，以两端点为顶点集，以两端点 VV VV 均在均在 中的边的全体为边集的图中的边的全体为边集的图 的子图，称的子图，称 VG 为为 的的由由 导出的子图导出的子图，记为，记为 .GVVG4) 若若 ，且，且 ，以

19、，以 为边集，以为边集，以 的端点的端点EE EEE 集为顶点集的图集为顶点集的图 的子图，称为的子图，称为 的的由由 导出的导出的GGE 边导出的子图边导出的子图，记为，记为 . EG,321vvvG,6543eeeeG 3) 若若 ，且，且 ，以，以 为顶点集，以两端点为顶点集，以两端点 VV VV 均在均在 中的边的全体为边集的图中的边的全体为边集的图 的子图，称的子图，称 VG4) 若若 ，且，且 ，以，以 为边集，以为边集，以 的端点的端点EE EEE 集为顶点集的图集为顶点集的图 的子图，称为的子图，称为 的的由由 导出的导出的GGE 边导出的子图边导出的子图，记为，记为 . EG

20、GVVG 为为 的的由由 导出的子图导出的子图，记为，记为 .3) 3) 图的矩阵表示图的矩阵表示 邻接矩阵邻接矩阵:1) 对无向图对无向图 ，其邻接矩阵，其邻接矩阵 ，其中：，其中： G)(ijaA., 0, 1不相邻与若相邻与若jijiijvvvva54321543210010000100110110010100110vvvvvAvvvvv(以下均假设图为简单图以下均假设图为简单图).2) 对有向图对有向图 ,其邻接矩阵其邻接矩阵 ,其中：其中： )(ijaA),(EVG .),(, 0,),(, 1EvvEvvajijiij若若432143210100001000001110uuuuAu

21、uuu其中：其中：3) 对有向赋权图对有向赋权图 , 其邻接矩阵其邻接矩阵 ,)(ijaA),(EVG .),(,0,),(,EvvjiwEvvwajiijjiijij若，为其权，且若43214321040608730uuuuAuuuu对于无向赋权图的邻接矩阵可类似定义对于无向赋权图的邻接矩阵可类似定义. 关联矩阵关联矩阵 1) 对无向图对无向图 ，其关联矩阵，其关联矩阵 ,),(EVG )(ijmM其中：其中：., 0, 1不关联与若相关联与若jijiijevevm54321543211000001000111100010100011vvvvvMeeeee2) 对有向图对有向图 ，其关联矩阵

22、，其关联矩阵 ,),(EVG )(ijmM., 0, 1, 1的头与尾不是若的头是若的尾是若jijijiijevevevm其中：其中：43215432111000101100001101101uuuuMeeeee4) 图的顶点度图的顶点度定义定义 1) 在无向图在无向图G中，与顶点中，与顶点v关联的边的数目关联的边的数目(环环算两次算两次),称为顶点称为顶点v的的度度或或次数次数，记为，记为d(v)或或 dG(v).称度为奇数的顶点为称度为奇数的顶点为奇点奇点，度为偶数的顶点为，度为偶数的顶点为偶点偶点.2) 在有向图中，从顶点在有向图中，从顶点v引出的边的数目称为顶点引出的边的数目称为顶点

23、v的的出度出度，记为，记为d+(v)，从顶点，从顶点v引入的边的数目称为引入的边的数目称为 v的的入度入度，记为，记为d -(v). 称称d(v)= d+(v)+d -(v)为顶点为顶点v的的 度度或或次数次数定理定理.2)(Vvvd的个数为偶数的个数为偶数推论推论 任何图中奇点任何图中奇点4)(1vd1)(3ud2)(3ud3)(3ud5) 路和连通路和连通定义定义 1) 无向图无向图G的一条的一条途径途径（或（或通道通道或或链链）是指）是指一个有限非空序列一个有限非空序列 ，它的项交替，它的项交替kkveevevW2110 地为顶点和边，使得对地为顶点和边，使得对 ， 的端点是的端点是 和

24、和 ,ki 1ie1iviv称称W是从是从 到到 的一条的一条途径途径，或一条，或一条 途径途径. 整整0vkv),(0kvv数数k称为称为W的的长长. 顶点顶点 和和 分别称为的分别称为的起点起点和和终点终点 ,0vkv而而 称为称为W的的内部顶点内部顶点.121,kvvv 2) 若途径若途径W的边互不相同但顶点可重复，则称的边互不相同但顶点可重复，则称W为为迹迹或或简单链简单链. 3) 若途径若途径W的顶点和边均互不相同，则称的顶点和边均互不相同，则称W为为路路或或路径路径. 一条起点为一条起点为 ,终点为终点为 的路称为的路称为 路路0vkv),(0kvv记为记为).,(0kvvP 定义

25、定义 1) 途径途径 中由相继项构成子序列中由相继项构成子序列kkvevevW.110 称为途径称为途径W的的节节.jjiiivevev.11 2) 起点与终点重合的途径称为起点与终点重合的途径称为闭途径闭途径. 3) 起点与终点重合的的路称为起点与终点重合的的路称为圈圈(或或回路回路)，长，长为为k的圈称为的圈称为k阶圈阶圈，记为，记为Ck. 4) 若在图若在图G中存在中存在(u,v)路，则称顶点路，则称顶点u和和v在图在图G中中连通连通. 5) 若在图若在图G中顶点中顶点u和和v是连通的，则顶点是连通的，则顶点u和和v之之之间的之间的距离距离d(u,v)是指图是指图G中最短中最短(u,v)

26、路的长；若没路的长；若没没有路连接没有路连接u和和v，则定义为无穷大，则定义为无穷大. 6) 图图G中任意两点皆连通的图称为中任意两点皆连通的图称为连通图连通图 7) 对于有向图对于有向图G，若，若 ，且，且 有有kkveevevW2110ie 类似地，可定义类似地，可定义有向迹有向迹，有向路有向路和和有向圈有向圈.头头 和尾和尾 ，则称，则称W为为有向途径有向途径.iv1iv 例例 在右图中：在右图中： 途径或链：途径或链： 迹或简单链：迹或简单链： 路或路径：路或路径： 圈或回路：圈或回路：wugyexeyfxcyvbwcxdvauguavdxcwuuavbwcxfyg例例 一摆渡人欲将一

27、只狼，一头羊，一篮菜从一摆渡人欲将一只狼，一头羊，一篮菜从河西渡过河到河东，由于船小，一次只能带一物河西渡过河到河东，由于船小，一次只能带一物过河，并且，狼与羊，羊与菜不能独处，给出渡过河，并且，狼与羊，羊与菜不能独处，给出渡河方法。河方法。解：解：用四维用四维0-1向量表示（人，狼，羊，菜）的在西岸向量表示（人，狼，羊，菜）的在西岸状态，（在西岸则分量取状态，（在西岸则分量取1，否则取，否则取0.）共共24=16种状态，种状态，由题设，状态（由题设，状态（0,1,1,0）,(0,0,1,1),(0,1,1,1)是不是不允许的，允许的，从而对应状态（从而对应状态（1,0,0,1），），(1,1

28、,0,0),(1,0,0,0)也是也是不允许的，不允许的，人在河西：（1,1,1,1） （1,1,1,0）（1,1,0,1） （1,0,1,1）（1,0,1,0）（0,1,0,1） （0,1,0,0）（0,0,1,0） （0,0,0,1）（0,0,0,0）人在河东：以十个向量作为顶点，将可能互相转移的状态连线，则得10个顶点的偶图。问题：如何从状态（1,1,1,1）转移到（0,0,0,0）？方法方法：从（1,1,1,1）开始，沿关联边到达没有到达的相邻顶点，到（0,0,0,0）终止，得到有向图即是。3最短路问题及算法最短路问题及算法 最短路问题是图论应用的基本问题，很多实际最短路问题是图论应用

29、的基本问题，很多实际问题，如线路的布设、运输安排、运输网络最小费问题，如线路的布设、运输安排、运输网络最小费用流等问题用流等问题,都可通过建立最短路问题模型来求解都可通过建立最短路问题模型来求解.最短路的定义最短路的定义最短路问题的两种方法：最短路问题的两种方法：Dijkstra和和Floyd算法算法 .1) 求赋权图中从给定点到其余顶点的最短求赋权图中从给定点到其余顶点的最短路路. .2) 求赋权图中任意两点间的最短路求赋权图中任意两点间的最短路. 2) 在赋权图在赋权图G中，从顶点中，从顶点u到顶点到顶点v的具有最小权的具有最小权定义定义 1) 若若H是赋权图是赋权图G的一个子图，则称的一

30、个子图，则称H的各的各边的权和边的权和 为为H的的权权. 类似地，若类似地，若)()()(HEeewHw称为路称为路P的的权权若若P(u,v)是赋权图是赋权图G中从中从u到到v的路的路,称称)()()(PEeewPw 的路的路P*(u,v)，称为，称为u到到v的的最短路最短路 3) 把赋权图把赋权图G中一条路的权称为它的中一条路的权称为它的长长，把，把(u,v)路的最小权称为路的最小权称为u和和v之间的之间的距离距离，并记作，并记作 d(u,v). 1) 赋权图中从给定点到其余顶点的最短路赋权图中从给定点到其余顶点的最短路 假设假设G为赋权有向图或无向图，为赋权有向图或无向图，G边上的权均非边

31、上的权均非负若负若 ，则规定，则规定 )(),(GEvu.),(vuw最短路是一条路，且最短路的任一节也是最短路最短路是一条路，且最短路的任一节也是最短路求下面赋权图中顶点求下面赋权图中顶点u0到其余顶点的最短路到其余顶点的最短路Dijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为

32、 ，置，置1iu.11iiiuSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i替替i，并转，并转2). 7,.,2 , 1,)(,00juluSj01Su 10 ,min)(1ulDijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.1

33、1iiiuSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i替替i，并转，并转2). 7,.,2 , 1,)(,00juluSj01Su 1)(1ul02Su Dijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3)

34、若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i替替i，并转，并转2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul03Su )(3ulDijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 若若 ，则

35、停止；若，则停止；若 ，则用，则用 i+1 代代1i1i替替i，并转，并转2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul04Su )(3ulDijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 若若 ，则停止；若，

36、则停止；若 ，则用，则用 i+1 代代1i1i替替i，并转，并转2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul7)(4ul05Su )(3ulDijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 若若 ，则停止；若

37、，则停止；若 ，则用，则用 i+1 代代1i1i替替i，并转，并转2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul7)(4ul)(5ul06Su )(3ulDijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 若若

38、，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i替替i，并转，并转2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul7)(4ul)(5ul4)(6ul07Su Dijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS

39、 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i替替i，并转，并转2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul)(3ul7)(4ul)(5ul4)(6ul8)(7ulDijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，

40、置1iu.11iiiuSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i替替i，并转，并转2). 7,.,2 , 1,)(,00juluSj1)(1ul2)(2ul)(3ul7)(4ul)(5ul4)(6ul)()(min10ulvlSv8)(7ulDijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(

41、vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i替替i，并转，并转2).,101uuS 1)(1ul2)(2ul)(3ul7)(4ul)(5ul4)(6ul8)(7ul12Su 21 , 2min)(2ul2)(2ulDijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(minvuwulvlii代替代替 ，计算，计算

42、，并把达到这个最小值的，并把达到这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i替替i，并转，并转2).,101uuS 1)(1ul2)(2ul)(3ul7)(4ul)(5ul4)(6ul8)(7ul12Su 21 , 2min)(2ul2)(2ulDijkstra算法算法: 求求G中从顶点中从顶点u0到其余顶点的最短路到其余顶点的最短路. 1) 置置 ，对，对 ， ， 且且 .0)(0ul0uv )(vl00uS 0i 2) 对每个对每个 ，用，用iSv),()(),(

43、minvuwulvlii代替代替 ，计算，计算 ，并把达到这个最小值的，并把达到这个最小值的)(vl)(minvliSv一个顶点记为一个顶点记为 ，置，置1iu.11iiiuSS 3) 若若 ，则停止；若，则停止；若 ，则用，则用 i+1 代代1i1i替替i，并转，并转2).定义 根据顶点根据顶点v的标号的标号l(v)的取值途径，使的取值途径，使 到到v0u的最短路中与的最短路中与v相邻的前一个顶点相邻的前一个顶点w，称为，称为v的的先驱先驱点点，记为，记为z(v), 即即z(v)=w.先驱点可用于追踪最短路径先驱点可用于追踪最短路径. Dijkstra算法：算法：求求G中从顶点中从顶点u0到

44、其余顶点的最短路到其余顶点的最短路设设G为赋权有向图或无向图，为赋权有向图或无向图，G边上的权均均非负边上的权均均非负. 对每个顶点，定义两个标记（对每个顶点，定义两个标记（l(v)，z(v)），其中），其中: l(v) ：表从顶点表从顶点u0到到v的一条路的权的一条路的权 z(v) ：v的先驱点，用以确定最短路的路线的先驱点，用以确定最短路的路线.l(v)为从顶点为从顶点u0到到v的最短路的权的最短路的权算法的过程就是在每一步改进这两个标记，使最终算法的过程就是在每一步改进这两个标记，使最终S：具有永久标号的顶点集：具有永久标号的顶点集.输入输入: G的带权邻接矩阵的带权邻接矩阵 w(u,v

45、)将求最短路与最短路径结合起来将求最短路与最短路径结合起来:算法步骤：算法步骤：l(v)u0vl(u)uw(u,v)首先写出带权邻接矩阵首先写出带权邻接矩阵024782063446046340357630135102273201847210W例例 求下图从顶点求下图从顶点u0到到其余顶点的最短路其余顶点的最短路因因G是无向图，故是无向图，故W是对称阵是对称阵1u0u6u7u2u4u3u5u2) 求赋权图中任意两顶点间的最短路求赋权图中任意两顶点间的最短路 算法的基本思想算法的基本思想 （I）求距离矩阵的方法）求距离矩阵的方法.（II）求路径矩阵的方法）求路径矩阵的方法.（III）查找最短路路径的方法）查找最短路路径的方法. Floyd算法：求任意两顶点间的最短路算法：求任意两顶点间的最短路. 举例说明举例说明算法的基本思想算法的基本思想（I）求距离矩阵的方法）求距离矩阵的方法.（II）求路径矩阵的方法）求路径矩阵的方法.在建立距离矩阵的同时可建立路径矩阵在建立距离矩阵的同时可建立路径矩阵R ivjv（III）查找最短路路径的方法）查找最短路路径的方法.然后用同样的方法再分头查找若：然后用同样的方法再分头查找若：1av2av3avkav1bv2bvmbv（IV）Floyd算法：求任意两顶点