数学建模-图论篇ppt课件.ppt

《数学建模-图论篇ppt课件.ppt》由会员分享，可在线阅读，更多相关《数学建模-图论篇ppt课件.ppt（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多 1、涉及图论的历年数学建模题目、涉及图论的历年数学建模题目 2、图论简介图论简介 3、图的定义和术语、图的定义和术语4、图的存储结构、图的存储结构5、最短路径算法、最短路径算法 6 图论的应用实例图论的应用实例图图 论论 篇篇(1)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多寒假来临，不少的高

2、中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多图论方法在历年数学建模中的应用经常出现，下面总结如下表2、历年数学建模与图论方法有关题目、历年数学建模与图论方法有关题目寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多Graph Theory in Mathematical Modeling2、图论简介 现实生活中许多问题都可归结为由点和线组成的现实生活中许多问题都

3、可归结为由点和线组成的图形的问题，例如，铁路交通图，公路交通图，图形的问题，例如，铁路交通图，公路交通图，市区交通图，自来水管网系统，甚至电路图在研市区交通图，自来水管网系统，甚至电路图在研究某些问题时也可简化为由点和线组成的图形。究某些问题时也可简化为由点和线组成的图形。如果我们用点表示这些具体事物，用连接两点的如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个就得到了描述这个“图图”的几何形象。的几何形象。图论就是研究这些由点和线组成的图形的问题。图论就是研究这些由点和线组成的图形的问题。寒假来

4、临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2图的定义和术语图的定义和术语ABCDABCDE有向图有向图 G1无向图无向图 G2 结点或结点或 顶点：顶点：有向边（弧）、弧尾或初始结有向边（弧）、弧尾或初始结点、弧头或终止结点点、弧头或终止结点ABAB 有向图：有向图：G1=（V1，A1）V1=A,B,C,D A1=,结点或结点或 顶点：顶点：无向边或边无向边或边AB 无向图：无向图：G2=（V2，A2）V2=A,

5、B,C,D,E A2=(A,B),(A,C),(B,D),(B,E,(C,E),(D,E)AB寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多图的定义和术语图的定义和术语ABCD无无向图向图 G2ABCDACABCD有向图有向图G1的子图的子图ABCDEABDEAABCDABCDE无向图无向图G2的子图的子图有向图有向图 G1寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，

6、目前社会上寒假招工的陷阱很多寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多图的定义和术语图的定义和术语无无向图的连通性向图的连通性ABCDE路径：在无向图路径：在无向图G=(V,E)中由顶点中由顶点v至至v 的顶点序列。的顶点序列。回路或环：第一个顶点和最后一个顶点相同的路径。回路或环：第一个顶点和最后一个顶点相同的路径。简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。连通：顶点连通：顶点v至至v 之间有路径存在之间有路径

7、存在连通图：无向图图连通图：无向图图 G 的任意两点之间都是连通的，则称的任意两点之间都是连通的，则称 G 是连通图。是连通图。连通分量：极大连通子图连通分量：极大连通子图FGIJLHMKABCDEHMFGIJLK无向图无向图G无向图无向图G的三个连通分量的三个连通分量寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多图的定义和术语图的定义和术语有向图的连通性有向图的连通性路径：在有向图路径：在有向图G=(V,E)

8、中由顶点中由顶点v经有向边至经有向边至v 的顶点序列。的顶点序列。回路或环：第一个顶点和最后一个顶点相同的路径。回路或环：第一个顶点和最后一个顶点相同的路径。简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。连通：顶点连通：顶点v至至v 之间有路径存在之间有路径存在强连通图：有向图图强连通图：有向图图 G 的任意两点之间都是连通的，则称的任意两点之间都是连通的，则称 G 是强连通图。是强连通图。强连通分量：极大连通子图强连通分量：极大连通子图有向图有向图G有向图有向图G的两个强连通分量的两个强

9、连通分量ABCDABCD寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多图的定义和术语图的定义和术语生成树：极小连通子图。包含图的所有生成树：极小连通子图。包含图的所有 n 个结点，但只含图的个结点，但只含图的 n-1 条边。在生成树中添条边。在生成树中添 加一条边之后，必定会形成回路或环，但是含有加一条边之后，必定会形成回路或环，但是含有n-1条边的图不一定是生成树条边的图不一定是生成树ABCDEHMABCDE

10、HM无向图无向图G 无向图无向图G的生成树的生成树 有向图的生成树：有若干个有向树组成，含有图中的全部有向图的生成树：有若干个有向树组成，含有图中的全部顶点，但是构成若干个互不相交的有向树顶点，但是构成若干个互不相交的有向树寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多图的定义和术语图的定义和术语完全完全 图：有图：有 n(n-1)/2 条边的无向图。其中条边的无向图。其中 n 是结点个数。是结点个数。有向完全

11、图：有有向完全图：有 n(n-1)条边的有向图。其中条边的有向图。其中 n 是结点个数。是结点个数。边的权值，边有权的图称之为网络。边的权值，边有权的图称之为网络。邻接点：邻接点：边用顶点的无序偶对（边用顶点的无序偶对（vi,vj）来表示，称顶点）来表示，称顶点vi和顶点和顶点vj互为邻接点互为邻接点稠密图、稀疏图。若一个图接近完全图，称为稠密图；称边数很少的图为稀疏图稠密图、稀疏图。若一个图接近完全图，称为稠密图；称边数很少的图为稀疏图 无向图结点的度无向图结点的度:指依附于某顶点指依附于某顶点v的边数的边数 记为记为TD(v)有向图结点的出度和入度有向图结点的出度和入度:顶点顶点v的入度是

12、指以顶点的入度是指以顶点 为终点的弧的数目。记为为终点的弧的数目。记为ID(v)ABCDEHM无向图无向图G1 图图的的其其它它术术语语有向图有向图G2ABCD有向图顶点有向图顶点v出度出度是指以顶点是指以顶点v为为始点的弧始点的弧的数目，的数目，记为记为OD(v)。有有TD(v)=ID(v)OD(v)。n个顶点的个顶点的图中顶点度图中顶点度和边的关系和边的关系寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多图的

13、存储结构图的存储结构图的四种常用的存储形式：图的四种常用的存储形式：数组表示法（邻接矩阵和加权邻接矩阵数组表示法（邻接矩阵和加权邻接矩阵 matrix）邻接表邻接表十字链表十字链表邻接多重表邻接多重表 1、邻接矩阵和加权邻接矩阵（、邻接矩阵和加权邻接矩阵（labeled adjacency matrix）ABCD无权值的有向图的邻接矩阵无权值的有向图的邻接矩阵 设有向图具有设有向图具有 n 个结点，则用个结点，则用 n 行行 n 列的布尔矩阵列的布尔矩阵 A 表示该有向图；表示该有向图；并且并且 Ai,j =1,如果如果i 至至 j 有一条有向边；有一条有向边；Ai,j=0如果如果 i 至至

14、j 没有一条有向边没有一条有向边 注意：注意：Ai,i =0。出度出度:i行之和。入度行之和。入度:j列之和。列之和。表示成右图矩阵表示成右图矩阵0 1 1 00 0 0 00 0 0 11 0 0 0寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多邻接矩阵表示法对求顶点的度很方便。邻接矩阵表示法对求顶点的度很方便。在无向图中：在无向图中：顶点的度数顶点的度数=矩阵中对应该顶点的行矩阵中对应该顶点的行或或列中非列

15、中非零元素的个数。零元素的个数。在有向图中：在有向图中：顶点的出度顶点的出度=矩阵中对应该顶点的矩阵中对应该顶点的行行中非零元中非零元素的个数。素的个数。顶点的入度顶点的入度=矩阵中对应该顶点的矩阵中对应该顶点的列列中非零元中非零元素的个数。素的个数。2023/3/1711寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多V1V3V2V4V1V3V2V4 V1 V2 V3 V4 V1 0 0 1 0 V2 0 0

16、0 1 V3 0 0 0 1 V4 1 0 0 0 V1 V2 V3 V4 V1 0 1 1 1 V2 1 0 0 1 V3 1 0 0 0 V4 1 1 0 0入度入度 出度出度1 11 11 11 12 12 10 10 1度数度数3 3 2 2 1 1 2 2 2023/3/1712寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多图的存储结构图的存储结构 1、邻接矩阵和加权邻接矩阵（、邻接矩阵和加权邻接矩阵

17、（labeled adjacency matrix）（续）（续）无权值的无向图的邻接矩阵无权值的无向图的邻接矩阵 设无向图具有设无向图具有 n 个结点，则用个结点，则用 n 行行 n 列的布尔矩阵列的布尔矩阵 A 表示该无向图；表示该无向图；并且并且 Ai,j =1,如果如果i 至至 j 有一条无向边；有一条无向边；Ai,j=0如果如果 i 至至 j 没有一条无向边没有一条无向边 注意：注意：Ai,i =0。i结点的度结点的度:i行或行或i列之和。上三角矩阵或下三角矩阵。列之和。上三角矩阵或下三角矩阵。表示成右图矩阵表示成右图矩阵0 1 1 0 01 0 0 1 11 0 0 0 10 1 0

18、 0 10 1 1 1 0ABCDE寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多图的存储结构图的存储结构 1、邻接矩阵和加权邻接矩阵（、邻接矩阵和加权邻接矩阵（labeled adjacency matrix）（续）（续）有向图的加权邻接矩阵有向图的加权邻接矩阵 设有向图具有设有向图具有 n 个结点，则用个结点，则用 n 行行 n 列的矩阵列的矩阵 A 表示该有向图；表示该有向图；并且并且 Ai,j =a,如

19、果如果i 至至 j 有一条有向边且它的权值为有一条有向边且它的权值为a。Ai,j=无穷，无穷，如果如果 i 至至 j 没有一条有向边。没有一条有向边。ABCD表示成右图矩阵表示成右图矩阵 a b b b a a aaabbb优点优点：判断任意两点之间是否有边方便，仅耗费：判断任意两点之间是否有边方便，仅耗费 O(1)时间。时间。缺点：即使缺点：即使 j 是否有边，最坏需耗费是否有边，最坏需耗费 O(n)时间。无向图同一条边表示两次时间。无向图同一条边表示两次 边表空间浪费一倍。有向图中寻找进入某结点的边，非常困难。边表空间浪费一倍。有向图中寻找进入某结点的边，非常困难。datafirstarc

20、结点表中的结点的表示结点表中的结点的表示：用数组用数组data:结点的数据场，保存结点的数据值。结点的数据场，保存结点的数据值。firstarc:结点的指针场，给出自该结点出发的结点的指针场，给出自该结点出发的 的第一条边的边结点的地址。的第一条边的边结点的地址。寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多图的存储结构图的存储结构 2、邻接表（、邻接表（adjacency list）datafirstarc结

21、点表中的结点的表示：续结点表中的结点的表示：续 用单链表用单链表data:结点的数据场，保存结点的结点的数据场，保存结点的 数据值。数据值。firstarc:结点的指针场，给出自该结点的指针场，给出自该 结点出发的的第一条边的结点出发的的第一条边的 边结点的地址。边结点的地址。nextvex:结点的指针场，给出该结结点的指针场，给出该结 点的下一结点的地址。点的下一结点的地址。nextvexinfoadjvexnextarc边结点表中的结点的表示：边结点表中的结点的表示：info:边结点的数据场，保存边的边结点的数据场，保存边的 权值等。权值等。adjvex:边边结点的指针场，给出本结点的指针

22、场，给出本 条边依附的另一结点（非条边依附的另一结点（非 出发结点）的地址。出发结点）的地址。nextarc:结点的指针场，给出自该结点的指针场，给出自该 结点出发的的下一条边的结点出发的的下一条边的 边结点的地址。边结点的地址。寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多图的存储结构图的存储结构 2、邻接表（、邻接表（adjacency list）实例实例：ABCD无无向图向图 G2ABCDE向图向图 G1

23、ABCD12030123nullnullnullnull data firstarc adjvex nextvexAB1201234null data firstarc03041412CDE43nullnullnullnullAdjvex 指针场之值为相应结点指针场之值为相应结点 数的组元素的下标数的组元素的下标!六条边却用了六条边却用了 12 个边结点个边结点!改进：建立邻接多重表改进：建立邻接多重表寻找进入结点的边非常困难寻找进入结点的边非常困难!改进：建立逆邻接表或十字链表改进：建立逆邻接表或十字链表 adjvex nextvex寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过

24、一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多图的存储结构图的存储结构 2、邻接表（、邻接表（adjacency list）逆邻接表实例逆邻接表实例：ABCD有向图有向图 G1AB320123l002CD寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多图的存储结构图的存储结构 3、十字链

25、表十字链表datafirstinfirstoutinfotailvex headvex边结点表中的结点的表示：边结点表中的结点的表示：结点表中的结点的表示：结点表中的结点的表示：data:结点的数据结点的数据域域，保存结点的，保存结点的 数据值。数据值。firstin:结点的指针结点的指针域域，给出自该，给出自该 结点出发的的第一条边的结点出发的的第一条边的 边结点的地址。边结点的地址。firstout:结点的指针结点的指针域域，给出进入该，给出进入该 结点的第一条边的结点的第一条边的 边结点的地址。边结点的地址。info:边结点的数据边结点的数据域域，保存边的，保存边的 权值等。权值等。hl

26、inktlinktailvex:本条边的出发结点本条边的出发结点 的的地址。地址。headvex:本条边的终止结点本条边的终止结点 的地址。的地址。hlink:出发结点相同的边出发结点相同的边 中的下一条边的地址。中的下一条边的地址。tlink:终止结点相同的边终止结点相同的边 中的下一条边的地址中的下一条边的地址。寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多图的存储结构图的存储结构 3、十字链表、十字链表实

27、例实例：ABCD向图向图 G10123ABCD01022220033331 data firstin firstouttailvexheadvex hlinktlink用途：用于有向图，用途：用于有向图，查询查询 进入结点和离开结点进入结点和离开结点 的边容易。的边容易。寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多图的存储结构图的存储结构 4、邻接多重表、邻接多重表datafirstedgemarkivexi

28、link边结点表中的结点的表示边结点表中的结点的表示：结点表中的结点的表示结点表中的结点的表示：data:结点的数据结点的数据域域，保存结点的，保存结点的 数据值。数据值。firstedge:结点的指针结点的指针域域，给出自该，给出自该 结点出发的的第一条边的结点出发的的第一条边的 边结点的地址。边结点的地址。info:边结点的数据边结点的数据域域，保存边的，保存边的 权值等。权值等。mark:边结点的标志域，用于标识边结点的标志域，用于标识 该条边是否被访问过。该条边是否被访问过。jvexinfoivex:本条边本条边依附的一依附的一 个个结点的地址结点的地址。ilink:依附于该结点（地依

29、附于该结点（地 址由址由ivex给出）的给出）的 边中的下一条边的边中的下一条边的 的地址。的地址。jlinkjvex:本条边本条边依附的另依附的另 一个一个结点的地址结点的地址。jlink:依附于该结点（地依附于该结点（地 址由址由jvex给出）的给出）的 边中的下一条边的边中的下一条边的 的地址。的地址。寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多图的存储结构图的存储结构 4、邻接多重表、邻接多重表实例：

30、实例：无向图无向图 G2用途：用于无向图，边表中用途：用于无向图，边表中 的边结点只需存放一的边结点只需存放一 次，节约内存。次，节约内存。ABCDEAB01234 data firstedgeCDE012441310234 markivex ilink jvex jlink 寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多练习：给出下图的练习：给出下图的1）邻接矩阵、）邻接矩阵、2）邻接表和）邻接表和3）十字链

31、表表表示）十字链表表表示 ACBFED012345ABCDEFData fin fout01031214253134541)2)邻接表要求出和入边两种邻接表要求出和入边两种2023/3/1723寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多（二）给出右图的邻接多重表（二）给出右图的邻接多重表ADCB01 23 0203122023/3/1724寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而

32、有意义的寒假。但是，目前社会上寒假招工的陷阱很多寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多Graph Theory in Mathematical Modeling5图的最短路径算法图的最短路径算法-Dijkstra算法算法 最短路问题是图论应用的基本问题，很多实际问题，最短路问题是图论应用的基本问题，很多实际问题，如线路的布设、运输安排、运输网络最小费用流等问题如线路的布设、运输安排、运输网络最小费用流等问题,都可通过建立最短路问题模型来求解都可通过建立最短路问题模型来求解.求解最短路问题的两种方法：求解最短路问题的两

33、种方法：Dijkstra和和Floyd算法算法.(1)求赋权图中从给定点到其余顶点的最短路求赋权图中从给定点到其余顶点的最短路;(2)求赋权图中任意两点间的最短路求赋权图中任意两点间的最短路.上级目录上级目录寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多Graph Theory in Mathematical Modeling求赋权图中从给定点到其余顶点的最短路求赋权图中从给定点到其余顶点的最短路Dijkstr

34、aDijkstra算法算法 解决上述问题的一个方法是由解决上述问题的一个方法是由Dijkstra(迪杰斯迪杰斯特拉特拉)于于1959年提出的算法，此算法不仅能求出赋年提出的算法，此算法不仅能求出赋权图指定两点间的最短路，而且能求出从指定点到权图指定两点间的最短路，而且能求出从指定点到其余各顶点的最短路其余各顶点的最短路.目前它是求无负权图最短路的目前它是求无负权图最短路的最好最好方法方法.Dijkstra算法是一种迭代算法，它依据的是一算法是一种迭代算法，它依据的是一个重要而明显的性质：个重要而明显的性质：最短路是一条路，最短路上的任一子段也是最最短路是一条路，最短路上的任一子段也是最短路。短

35、路。寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多Graph Theory in Mathematical ModelingDijkstra算法的算法的基本思想基本思想 按距按距u从近到远为顺序，依次求得从近到远为顺序，依次求得u0到图到图G的的各顶点的最短路和距离，直至顶点各顶点的最短路和距离，直至顶点v(或直至图或直至图G的的所有顶点所有顶点)。步骤步骤:把结点集把结点集V V分割为二子集分割为二子集 S,

36、T.S,T.开始时开始时S=a,T=S=a,T=V-SV-S.步骤步骤:对每结点对每结点 t t T,T,求出求出 D(t)D(t)之后再定出之后再定出x x T T 使得使得 D(x)=D(x)=minD(x)|tminD(x)|t T.T.步骤步骤:置置 S S 为为 S Sxx置置 T T为为T-x.T-x.若若 T=T=则停止则停止,否则转步骤否则转步骤作作下一次循环下一次循环.寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社

37、会上寒假招工的陷阱很多Graph Theory in Mathematical ModelingDijkstraDijkstra算法实现及步骤算法实现及步骤 对每个顶点对每个顶点v，定义两个标号，定义两个标号l(v),z(v),其中其中l(v)为从为从u0到到v的路长；的路长；z(v)为为v的父节点（前一个点）。的父节点（前一个点）。S：具有永久标号的顶集。：具有永久标号的顶集。算法的过程就是在每一步改进这两个标号，最算法的过程就是在每一步改进这两个标号，最终终l(v)为为u0到到v的最短路长。的最短路长。输入带权邻接矩阵（距离矩阵）输入带权邻接矩阵（距离矩阵）w(u,v).寒假来临，不少的高

38、中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多Graph Theory in Mathematical ModelingDijkstra算法的步骤算法的步骤:寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多Graph Theory in Mathe

39、matical ModelingDijkstra算法的步骤算法的步骤:G 中u0点到其它各点的距离及最短路第一步第一步 赋初值：令赋初值：令l(u0)=0，对所有，对所有v V u0，令，令l(v)=，z(v)=u0；S0=u0，i=0。第二步第二步 若若i=n 1，停止；否则令，停止；否则令 =V Si，进行下一步。，进行下一步。第三步第三步 更新标号：对每个更新标号：对每个v ，令，令如果如果l(v)l(ui)+w(ui,v)，则，则z(v)=ui，否则，否则z(v)不变。不变。第四步第四步 计算计算 ，并用，并用 ui1 记达到最小值的顶点，记达到最小值的顶点，置置Si1=Si ui1，

40、i=i1，转第二步。，转第二步。寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多最短路径1、从某个源点到其余各顶点的最短路径（单源最短路径问题）、从某个源点到其余各顶点的最短路径（单源最短路径问题）V1V3V2V5V4 实例实例:加权有向图加权有向图6060100100V0202030301010505010105 5源点源点源点源点终点终点最短路径最短路径路径长度路径长度V0V1无无V2（V0,V2）10V3（

41、V0,V4,V3）50V4（V0，V4）30V5（V0，V4，V3，V5）60 10 30 100 5 50 10 20 60 012345 0 1 2 3 4 5加权邻接矩阵：加权邻接矩阵：寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多最短路径1、从某个源点到其余各顶点的最短路径（单源最短路径问题从某个源点到其余各顶点的最短路径（单源最短路径问题）V1V3V2V5V4 Dijkstra 算法算法:606010

42、0100V03030101050501010源点源点V1V3V2V5V46060100100V0202030301010505010105 5源点源点S100、3010160、242020Dijkstra 算法求单源最短路径：算法求单源最短路径：设设 V 是该有向图的结点的集合、集合是该有向图的结点的集合、集合 S 是是已求得最短路径的结点的集合已求得最短路径的结点的集合,求求 V0 至其至其余各结点的最短距离。余各结点的最短距离。1、S 0 ；/结点结点 V0 最短路径已求得最短路径已求得2、for(i=1;in;i+)3、Di=c 0,i；/V0至至Vi的边长的边长4、for(i=1;in

43、;i+)5、在在 VS 中选择一个结点中选择一个结点VW；使得使得 Dw 最小。将最小。将W 加入集合加入集合 S6、for(每一个在每一个在 VS 中的结点中的结点 V)7、Dv=MIN(Dv,Dw+Cw,v);8、9、90、503605 55 5寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多最短路径1、从某个源点到其余各顶点的最短路径（单源最短路径问题）从某个源点到其余各顶点的最短路径（单源最短路径问题）V

44、1V3V2V5V4 Dijkstra 算法算法:6060100100V030301010505010105 5源点源点2020Dijkstra 算法求单源最短路径：算法求单源最短路径：设设 V 是该有向图的结点的集合、集合是该有向图的结点的集合、集合 S 是已求得最是已求得最短路径的结点的集合短路径的结点的集合,求求 V0 至其余各结点的最短距至其余各结点的最短距离。离。1、S 0 ；/结点结点 V0 最短路径已求得最短路径已求得2、for(i=1;in;i+)3、Di=c 0,i;P v =0;4、for(i=1;in;i+)5、在在 VS 中选择一个结点中选择一个结点VW；使得使得 Dw

45、最小。将最小。将W 加入集合加入集合 S6、for(每一个在每一个在 VS 中的结点中的结点 V)7、Dv=MIN(Dv,Dw+Cw,v);8、if (Dw+Cw,v j 的权值。如果的权值。如果 i=j；那么那么 c i,j =0。如果如果 i 和和 j 之间无有向边；则之间无有向边；则 c i,j =1、使用使用 n 行行 n 列的矩阵列的矩阵 A 用于计算最短路径。用于计算最短路径。初始时，初始时，A i,j =c i,j 2、进行进行 n 次迭代次迭代 在进行第在进行第 k 次迭代时，我们将使用如下的公式：次迭代时，我们将使用如下的公式：Ak-1 i,j Ak i,j =MIN Ak-

46、1 i,k +Ak-1 k,j 注意：第注意：第 k 次迭代时，针对结点次迭代时，针对结点 k 进行。原进行。原 Ak-1 矩阵的第矩阵的第 k 行，第行，第 k 列保持不变。左上至右下的对角线元素也不列保持不变。左上至右下的对角线元素也不变。变。最短路径2、每一对顶点之间的最短路径：、每一对顶点之间的最短路径：Floyd 算法算法V1V2 加加权有向图：权有向图：求各结点之间的最短路径求各结点之间的最短路径V05 53 38 82 2jkiAk-1 i,k Ak-1 k,j Ak-1 i,j 0 8 53 0 2 00 1 2012右图的代价矩阵右图的代价矩阵 c寒假来临，不少的高中毕业生和

47、大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多最短路径2、每一对顶点之间的最短路径：、每一对顶点之间的最短路径：Floyd 算法算法V1V2 实例及求解过程实例及求解过程:V05 53 38 82 2Floyd 算法的求解过程算法的求解过程 设设 C 为为 n 行行 n 列的代价矩阵，列的代价矩阵，c i,j 为为 i-j 的权值。如果的权值。如果 i=j；那么那么 c i,j =0。如果如果 i 和和 j 之间无有向边；则之间无有向边；

48、则 c i,j =1、使用使用 n 行行 n 列的矩阵列的矩阵 D 用于计算最短路径。用于计算最短路径。初始时，初始时，D i,j =c i,j 2、进行进行 n 次迭代次迭代 在进行第在进行第 k 次迭代时，我们将使用如下的公式：次迭代时，我们将使用如下的公式：Dk-1 i,j Dk i,j =M IN dk-1 i,k +dk-1 k,j 注意：第注意：第 k 次迭代时，针对结点次迭代时，针对结点 k 进行。原进行。原 dk-1 矩阵的第矩阵的第 k 行，第行，第 k 列保持不变。左上至右下的对角线元素也不列保持不变。左上至右下的对角线元素也不变。变。0 8 53 0 2 00 1 201

49、20 8 53 0 2 00 8 53 0 8 2 00 7 53 0 8 5 2 00 8 53 0 8 5 2 0D0D2D1D初值初值请看实例请看实例:注意：注意：k=0 (n-1)。如在由如在由 D初值得到初值得到D0时，时，原原D初值的第初值的第0行，第行，第0列不变，仍反应在列不变，仍反应在D0中。中。寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多最短路径2、每一对顶点之间的最短路径：、每一对顶点之

50、间的最短路径：Floyd 算法算法 算法的程序实现算法的程序实现:Floyd 算法的程序的简单描述：算法的程序的简单描述：int i,j，k;/标识标识结点结点 for (i=0;i n;i+)for (j=0;j n;j+)A i,j =C i,j;for (i=0;i n;i+)A i,i =0;for (k=0;k n;k+)for (i=0;i n;i+)for (j=0;j n;j+)if (A i,k +A k,j V1-V0 可以有许多圈。可以有许多圈。寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多寒假来临，不