《第六章图与网络分析精选文档.ppt》由会员分享，可在线阅读，更多相关《第六章图与网络分析精选文档.ppt（96页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第六章图与网络分析本讲稿第一页，共九十六页第第6 6章章 网络模型网络模型本讲稿第二页，共九十六页概述概述l l图图图图论论论论是是是是应应应应用用用用非非非非常常常常广广广广泛泛泛泛的的的的运运运运筹筹筹筹学学学学分分分分支支支支，它它它它已已已已经经经经广广广广泛泛泛泛地地地地应应应应用用用用于于于于物物物物理理理理学学学学控控控控制制制制论论论论，信信信信息息息息论论论论，工工工工程程程程技技技技术术术术，交交交交通通通通运运运运输输输输，经经经经济济济济管管管管理理理理，电电电电子子子子计计计计算算算算机机机机等等等等各各各各项项项项领领领领域域域域。对对对对于于于于科科科科学学学学研
2、研研研究究究究，市市市市场场场场和和和和社社社社会会会会生生生生活活活活中的许多问题，可以用图论的理论和方法来加以解决。中的许多问题，可以用图论的理论和方法来加以解决。中的许多问题，可以用图论的理论和方法来加以解决。中的许多问题，可以用图论的理论和方法来加以解决。l l例例如如，各各种种通通信信线线路路的的架架设设，输输油油管管道道的的铺铺设设，铁铁路路或或者者公公路路交交通通网网络络的的合合理理布布局局等等问问题题，都都可可以以应应用用图图论的方法，简便、快捷地加以解决。论的方法，简便、快捷地加以解决。本讲稿第三页，共九十六页学习内容学习内容l一、图的基本概念与模型一、图的基本概念与模型l二
3、、树图和图的最小部分树二、树图和图的最小部分树l三、最短路径问题三、最短路径问题l四、网络的最大流四、网络的最大流l五、最小费用流五、最小费用流本讲稿第四页，共九十六页一、图的基本概念与模型一、图的基本概念与模型l l1.1 1.1 1.1 1.1 哪些研究对象我们可以用图来表示哪些研究对象我们可以用图来表示哪些研究对象我们可以用图来表示哪些研究对象我们可以用图来表示-问题的提出问题的提出问题的提出问题的提出著名的哥尼斯堡七桥问题：欧拉在著名的哥尼斯堡七桥问题：欧拉在1736年发表年发表图论方面的第一篇论文解决了哥尼斯堡七桥问图论方面的第一篇论文解决了哥尼斯堡七桥问题。题。应用：生产组织，邮递
4、员问题，通讯网络等。应用：生产组织，邮递员问题，通讯网络等。本讲稿第五页，共九十六页ABCDl l著名的哥尼斯堡七桥问题著名的哥尼斯堡七桥问题著名的哥尼斯堡七桥问题著名的哥尼斯堡七桥问题 哥尼斯堡城中有一条河叫普雷格尔河，河中有两个岛，哥尼斯堡城中有一条河叫普雷格尔河，河中有两个岛，哥尼斯堡城中有一条河叫普雷格尔河，河中有两个岛，哥尼斯堡城中有一条河叫普雷格尔河，河中有两个岛，河上有七座桥。河上有七座桥。河上有七座桥。河上有七座桥。问题：一个散步者能否走过七座桥，且每座桥只走过问题：一个散步者能否走过七座桥，且每座桥只走过问题：一个散步者能否走过七座桥，且每座桥只走过问题：一个散步者能否走过七
5、座桥，且每座桥只走过一次，最后回到出发点一次，最后回到出发点一次，最后回到出发点一次，最后回到出发点A A A A。ADCB欧拉证明了这欧拉证明了这是不可能的！是不可能的！本讲稿第六页，共九十六页l“环球旅行环球旅行”问题问题在图中找一条经过每个点一次且仅一次的路在图中找一条经过每个点一次且仅一次的路在图中找一条经过每个点一次且仅一次的路在图中找一条经过每个点一次且仅一次的路哈哈哈哈密尔顿回路。密尔顿回路。密尔顿回路。密尔顿回路。l“中国邮路问题中国邮路问题”在图中找一条经过每边的最短路在图中找一条经过每边的最短路在图中找一条经过每边的最短路在图中找一条经过每边的最短路类似带权的欧拉类似带权的
6、欧拉类似带权的欧拉类似带权的欧拉回路。回路。回路。回路。l“货郎担问题货郎担问题”在图中找一条经过每个点一次且仅一次的最短路在图中找一条经过每个点一次且仅一次的最短路带权的哈密尔顿回路。带权的哈密尔顿回路。本讲稿第七页，共九十六页一、图的基本概念与模型一、图的基本概念与模型l l1.1 1.1 1.1 1.1 哪些研究对象我们可以用图来表示哪些研究对象我们可以用图来表示哪些研究对象我们可以用图来表示哪些研究对象我们可以用图来表示-问题的提问题的提问题的提问题的提出出出出l l例例 6-1:6-1:铁路交通图铁路交通图太原重庆武汉南京徐州连云港上海郑州石家庄塘沽青岛济南天津北京诸如此类的还有：电
7、诸如此类的还有：电话线分布图、煤气管话线分布图、煤气管道图、航空线图等道图、航空线图等本讲稿第八页，共九十六页l l例例例例 6-2:6-2:6-2:6-2:球队比赛图球队比赛图球队比赛图球队比赛图l l有有有有六六六六支支支支球球球球队队队队进进进进行行行行足足足足球球球球比比比比赛赛赛赛，我我我我们们们们分分分分别别别别用用用用点点点点v v v v1 1 1 1vvvv6 6 6 6表表表表示示示示这这这这六六六六支支支支球球球球队队队队，它它它它们们们们之之之之间间间间的的的的比比比比赛赛赛赛情情情情况况况况，也也也也可可可可以以以以用用用用图图图图反反反反映映映映出出出出来来来来，已
8、已已已知知知知v v1 1队队队队战战战战胜胜胜胜v v v v2 2 2 2队队队队，v v2 2队队战战胜胜v v v v3 3 3 3队队，v v3 3 3 3队队队队战战战战胜胜胜胜v v v v5 5 5 5队队，如如此此等等等等。这这个个胜胜负负情情况况，可可以以用用图图所所示示的的有有向向图图反映出来。反映出来。v3v1v2v4v6v5本讲稿第九页，共九十六页1.2 1.2 1.2 1.2 图的基本概念图的基本概念图的基本概念图的基本概念l l点点点点:表示研究对象。表示研究对象。表示研究对象。表示研究对象。l l连线（边或弧）：表示两个对象之间的某种特定关系。连线（边或弧）：表
9、示两个对象之间的某种特定关系。连线（边或弧）：表示两个对象之间的某种特定关系。连线（边或弧）：表示两个对象之间的某种特定关系。l l边：不带箭头的连线，表示对称关系。边：不带箭头的连线，表示对称关系。边：不带箭头的连线，表示对称关系。边：不带箭头的连线，表示对称关系。l l弧：带箭头的连线，表示不对称关系。弧：带箭头的连线，表示不对称关系。弧：带箭头的连线，表示不对称关系。弧：带箭头的连线，表示不对称关系。l l无向图：简称图，有无向图：简称图，有无向图：简称图，有无向图：简称图，有点和边点和边点和边点和边组成。组成。组成。组成。表示为：表示为：表示为：表示为：G=(V G=(V G=(V G
10、=(V，E)E)E)E)V-V-V-V-点集合点集合点集合点集合 E-E-E-E-边集合边集合边集合边集合 例：右图例：右图例：右图例：右图V=v1V=v1，v2v2，v3v3，v4v4E=e1E=e1，e2e2，,e7,e7e1=v1,v2 e1=v1,v2，e2=v1,v2e2=v1,v2，,e7=v4,v4 ,e7=v4,v4本讲稿第十页，共九十六页 l l 1.2 1.2 1.2 1.2 图的基本概念图的基本概念图的基本概念图的基本概念l l有向图：由点和弧组成。表示为：有向图：由点和弧组成。表示为：有向图：由点和弧组成。表示为：有向图：由点和弧组成。表示为：D=(VD=(VD=(VD
11、=(V，A)A)A)A)V-V-V-V-点集合点集合点集合点集合 A-A-A-A-弧集合弧集合弧集合弧集合v1v2v3v4v5例：右图例：右图V=v1V=v1，v2,v5v2,v5A=a1A=a1，a2,a7a2,a7a1=(v1,v5),a2=(v5,v4),a1=(v1,v5),a2=(v5,v4),a7=(v1,v4)a7=(v1,v4)本讲稿第十一页，共九十六页l l 1.2 1.2 1.2 1.2 图的基本概念图的基本概念图的基本概念图的基本概念l l无向图的有关概念无向图的有关概念无向图的有关概念无向图的有关概念l l端点端点端点端点:e=u,vE,e=u,vE,e=u,vE,e=
12、u,vE,则则则则u,vu,vu,vu,v是是是是e e e e的端点的端点的端点的端点,称称称称u,vu,vu,vu,v相邻。相邻。相邻。相邻。l l关联边关联边关联边关联边:e e e e是端点是端点是端点是端点u,vu,vu,vu,v的关联边。的关联边。的关联边。的关联边。l l环环环环:若若若若u=v,eu=v,eu=v,eu=v,e是环。是环。是环。是环。l l多重边多重边多重边多重边:两点之间多于一条边。两点之间多于一条边。两点之间多于一条边。两点之间多于一条边。l l简单图简单图简单图简单图:无环无环无环无环,无多重边的图。无多重边的图。无多重边的图。无多重边的图。l l多重图多
13、重图多重图多重图:无环无环无环无环,允许有多重边的图。允许有多重边的图。允许有多重边的图。允许有多重边的图。一、图的基本概念与模型一、图的基本概念与模型本讲稿第十二页，共九十六页 l l 1.2 1.2 1.2 1.2 图的基本概念图的基本概念图的基本概念图的基本概念l l次次次次:以点以点以点以点v v v v为端点的边的个数称为为端点的边的个数称为为端点的边的个数称为为端点的边的个数称为v v v v的次。表示为的次。表示为的次。表示为的次。表示为:d(v):d(v):d(v):d(v)。l l悬挂点悬挂点悬挂点悬挂点:次为次为次为次为1 1 1 1的点。的点。的点。的点。l l悬挂边悬挂
14、边悬挂边悬挂边:悬挂点的关联边。悬挂点的关联边。悬挂点的关联边。悬挂点的关联边。l l孤立点孤立点孤立点孤立点:次为次为次为次为0 0 0 0的点。的点。的点。的点。l l奇点奇点奇点奇点:次为奇数的点。次为奇数的点。次为奇数的点。次为奇数的点。l l偶点偶点偶点偶点:次为偶数的点。次为偶数的点。次为偶数的点。次为偶数的点。孤立点悬挂边本讲稿第十三页，共九十六页l l 1.2 1.2 1.2 1.2 图的基本概念图的基本概念图的基本概念图的基本概念 无向图的有关概念（续）无向图的有关概念（续）无向图的有关概念（续）无向图的有关概念（续）l l定理定理定理定理1:1:1:1:图图图图G=(V,E
15、)G=(V,E)G=(V,E)G=(V,E)中中中中,所有点的次之和是边数的两倍所有点的次之和是边数的两倍所有点的次之和是边数的两倍所有点的次之和是边数的两倍,即即即即:l l定理定理定理定理2:2:2:2:任意一图中任意一图中任意一图中任意一图中,奇点的个数为偶数。奇点的个数为偶数。奇点的个数为偶数。奇点的个数为偶数。证明证明:设设 V1-V1-奇点的集合奇点的集合,V2-V2-偶点的集合偶点的集合偶数偶数偶数本讲稿第十四页，共九十六页l l链：点边交错系列，链：点边交错系列，链：点边交错系列，链：点边交错系列，记为：记为：记为：记为：l l圈：起点和终点重合的的链。圈：起点和终点重合的的链
16、。圈：起点和终点重合的的链。圈：起点和终点重合的的链。l l路：点路：点路：点路：点 均不相均不相均不相均不相同。同。同。同。l l回路：回路：回路：回路：起点和终点重合的路。起点和终点重合的路。起点和终点重合的路。起点和终点重合的路。各边互不相同各边互不相同任意这两点相邻任意这两点相邻本讲稿第十五页，共九十六页 l l 1.2 1.2 1.2 1.2 图的基本概念图的基本概念图的基本概念图的基本概念l l无向图的有关概念（续）无向图的有关概念（续）无向图的有关概念（续）无向图的有关概念（续）l l连通图：任意两点之间至少有一条链。连通图：任意两点之间至少有一条链。l l完全图：图中任意两点之
17、间都有边相连。完全图：图中任意两点之间都有边相连。完全图：图中任意两点之间都有边相连。完全图：图中任意两点之间都有边相连。N N N N个顶点的图，个顶点的图，个顶点的图，个顶点的图，边的条数为边的条数为边的条数为边的条数为l l偶图：将图的顶点分成两个互不相交的非空集合偶图：将图的顶点分成两个互不相交的非空集合偶图：将图的顶点分成两个互不相交的非空集合偶图：将图的顶点分成两个互不相交的非空集合V1V1V1V1和和和和V2V2V2V2，使在同一集合中任意两个顶点均不相邻，称这样，使在同一集合中任意两个顶点均不相邻，称这样，使在同一集合中任意两个顶点均不相邻，称这样，使在同一集合中任意两个顶点均
18、不相邻，称这样的图为偶图或二分图。的图为偶图或二分图。的图为偶图或二分图。的图为偶图或二分图。l l子图：图子图：图子图：图子图：图G1=V1,E1G1=V1,E1G1=V1,E1G1=V1,E1和图和图和图和图G2=V2G2=V2G2=V2G2=V2，E2E2E2E2，若，若，若，若V1V1V1V1是是是是V2V2V2V2的子集的子集的子集的子集和和和和E1E1E1E1是是是是E2E2E2E2的子集，称的子集，称的子集，称的子集，称G1G1G1G1是是是是G2G2G2G2的子图的子图的子图的子图l l部分图：若部分图：若部分图：若部分图：若V1=V2V1=V2V1=V2V1=V2，E1E1E
19、1E1是是是是E2E2E2E2的真子集，则的真子集，则的真子集，则的真子集，则G1G1G1G1是是是是G2G2G2G2的部分的部分的部分的部分图。图。图。图。本讲稿第十六页，共九十六页二、树与最小树问题二、树与最小树问题l l2.1 2.1 2.1 2.1 树的概念树的概念树的概念树的概念l l一个一个一个一个无圈并且连通无圈并且连通无圈并且连通无圈并且连通的无向图称为树图或简称树的无向图称为树图或简称树的无向图称为树图或简称树的无向图称为树图或简称树(Tree)(Tree)(Tree)(Tree)。组织机构、家谱、学科分支、因特网络、通讯网络及高组织机构、家谱、学科分支、因特网络、通讯网络及
20、高组织机构、家谱、学科分支、因特网络、通讯网络及高组织机构、家谱、学科分支、因特网络、通讯网络及高压线路网络等都能表达成一个树图压线路网络等都能表达成一个树图压线路网络等都能表达成一个树图压线路网络等都能表达成一个树图 。可以证明：可以证明：（1 1）一棵树的边数等于点数减）一棵树的边数等于点数减1 1；（2 2）在树中任意两个点之间添加一条边就形成圈；）在树中任意两个点之间添加一条边就形成圈；（3 3）在树中去掉任意一条边图就变为不连通。）在树中去掉任意一条边图就变为不连通。v1v2v3v4v5v643217本讲稿第十七页，共九十六页在一个连通图在一个连通图G G中，取部分边连接中，取部分边
21、连接G G的所有点组成的树称的所有点组成的树称为为G G的部分树或支撑树的部分树或支撑树(Spanning Tree)(Spanning Tree)。图图2 2是图是图1 1的部分树。的部分树。2.1 2.1 2.1 2.1 树的概念树的概念树的概念树的概念v1v2v3v4v5v64321图图275v1v2v3v4v5v6843752618图图1本讲稿第十八页，共九十六页2.2 2.2 最小部分树概念最小部分树概念 将网络图将网络图G G边上的权看作两点间的长度（距离、费用、时间），定义边上的权看作两点间的长度（距离、费用、时间），定义G G的部分树的部分树T T的长度等于的长度等于T T中每
22、条边的长度之和，记为中每条边的长度之和，记为w(T)w(T)。G G的所有部分树中长度最小的部分树称为的所有部分树中长度最小的部分树称为最小部分树最小部分树，或简称，或简称为为最小树最小树。赋权图赋权图赋权图赋权图(网络）网络）网络）网络）:给图给图给图给图G=(V,E),G=(V,E),G=(V,E),G=(V,E),对对对对G G G G中的每一条边中的每一条边中的每一条边中的每一条边vi,vj,vi,vj,vi,vj,vi,vj,相应地有相应地有相应地有相应地有一个数一个数一个数一个数wij,wij,wij,wij,则称这样的图为赋权图则称这样的图为赋权图则称这样的图为赋权图则称这样的图
23、为赋权图,wij,wij,wij,wij 称为边称为边称为边称为边vi,vjvi,vjvi,vjvi,vj上的权。上的权。上的权。上的权。本讲稿第十九页，共九十六页二、树与最小树问题二、树与最小树问题l l2.3 2.3 2.3 2.3 如何从赋权图中获得最小部分树如何从赋权图中获得最小部分树如何从赋权图中获得最小部分树如何从赋权图中获得最小部分树l l1 1、获得最小部分树的依据：、获得最小部分树的依据：l l定理定理定理定理1 1 1 1 图中任一个点图中任一个点i i，若，若j j是与是与i i相邻点中距离最近相邻点中距离最近的，则边的，则边i,ji,j一定必含在该图的最小部分树内。一定
24、必含在该图的最小部分树内。l l推论：推论：推论：推论：把图的所有点分成把图的所有点分成把图的所有点分成把图的所有点分成V V V V和和和和VVVV两个集合，则两集合之两个集合，则两集合之两个集合，则两集合之两个集合，则两集合之间连线的最短边一定包含在最小部分树内。间连线的最短边一定包含在最小部分树内。间连线的最短边一定包含在最小部分树内。间连线的最短边一定包含在最小部分树内。l l2 2 2 2、求最小部分树的方法：破圈法和避圈法、求最小部分树的方法：破圈法和避圈法、求最小部分树的方法：破圈法和避圈法、求最小部分树的方法：破圈法和避圈法本讲稿第二十页，共九十六页二、树与最小树问题二、树与最
25、小树问题l l2 2 2 2、求最小支撑树的方法、求最小支撑树的方法、求最小支撑树的方法、求最小支撑树的方法l l（1 1 1 1）破圈法）破圈法）破圈法）破圈法l l方法：从网络图方法：从网络图方法：从网络图方法：从网络图N N N N中任取一回路，去掉这个回路中权数最中任取一回路，去掉这个回路中权数最中任取一回路，去掉这个回路中权数最中任取一回路，去掉这个回路中权数最大的一条边，得一子网络图大的一条边，得一子网络图大的一条边，得一子网络图大的一条边，得一子网络图N1N1N1N1。在。在。在。在N1N1N1N1中再任取一回路，再中再任取一回路，再中再任取一回路，再中再任取一回路，再去掉回路中
26、权数最大的一条边，得去掉回路中权数最大的一条边，得去掉回路中权数最大的一条边，得去掉回路中权数最大的一条边，得N2N2N2N2。如此继续下去，一。如此继续下去，一。如此继续下去，一。如此继续下去，一直到剩下的子图不再含回路止。该子图就是直到剩下的子图不再含回路止。该子图就是直到剩下的子图不再含回路止。该子图就是直到剩下的子图不再含回路止。该子图就是N N N N的最小部分的最小部分的最小部分的最小部分树。树。树。树。本讲稿第二十一页，共九十六页二、树与最小树问题二、树与最小树问题l l2 2 2 2、求最小支撑树的方法、求最小支撑树的方法、求最小支撑树的方法、求最小支撑树的方法l l（1 1
27、1 1）破圈法）破圈法）破圈法）破圈法本讲稿第二十二页，共九十六页5v1v2v3v4v5v6843752618图图61例例6-1 6-1 用破圈法求图用破圈法求图6 61 1的最小树。的最小树。图图62图图6 62 2就是图就是图6 61 1的最小部分树，最小树长为的最小部分树，最小树长为 w(T)=4+3+5+2+1=15 w(T)=4+3+5+2+1=15。当一个圈中有多个相同的最长边时，不能同时都去掉，只能去掉其中任意当一个圈中有多个相同的最长边时，不能同时都去掉，只能去掉其中任意一条边。一条边。最小部分树有可能不唯一，但最小树的长度相同最小部分树有可能不唯一，但最小树的长度相同 本讲稿
28、第二十三页，共九十六页（2 2）避圈法：取图）避圈法：取图G G的的n n个孤立点个孤立点v v1 1，v v2 2，v vn n 作为一作为一个支撑图，从最短边开始往支撑图中添加，见圈回避，直到连个支撑图，从最短边开始往支撑图中添加，见圈回避，直到连通（有通（有n n1 1条边）条边）v1v2v3v4v5v643521图图63在图在图6 63 3中，如果添加边中，如果添加边 v v1 1,v v2 2 就形成圈就形成圈v v1 1,v v2 2,v v4 4，这时，这时就应避开添加边就应避开添加边 v v1 1,v v2 2，添加下一条最短边，添加下一条最短边 v v3 3,v v6 6。破
29、圈法。破圈法和避圈法得到树的形状可能不一样，但最小树的长度相等和避圈法得到树的形状可能不一样，但最小树的长度相等 5v1v3v515v2v4v684375268Min w(T)=15本讲稿第二十四页，共九十六页二、树与最小树问题二、树与最小树问题l l2 2 2 2、求最小支撑树的方法、求最小支撑树的方法、求最小支撑树的方法、求最小支撑树的方法l l练习：练习：某六个城市之间的道路网如图所示，要求某六个城市之间的道路网如图所示，要求沿着已知长度的道路联结六个城市的电话线网，使沿着已知长度的道路联结六个城市的电话线网，使得电话线的总长度最短。得电话线的总长度最短。v6v5v2v3v4v16275
30、35441v3v2v1v4v6v553142本讲稿第二十五页，共九十六页 三、三、最短路问题最短路问题l l3.1 3.1 3.1 3.1 引言引言引言引言l l最短路问题，就是从给定的网络图中找出一点到各点最短路问题，就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路。或任意两点之间距离最短的一条路。l l最短路径问题是图论中十分重要的最优化问题之一，它作为最短路径问题是图论中十分重要的最优化问题之一，它作为最短路径问题是图论中十分重要的最优化问题之一，它作为最短路径问题是图论中十分重要的最优化问题之一，它作为一个经常被用到的基本工具，可以解决生产实际中的许多问一个经常被用到的
31、基本工具，可以解决生产实际中的许多问一个经常被用到的基本工具，可以解决生产实际中的许多问一个经常被用到的基本工具，可以解决生产实际中的许多问题，比如城市中的管道铺设，线路安排，工厂布局，设备更题，比如城市中的管道铺设，线路安排，工厂布局，设备更题，比如城市中的管道铺设，线路安排，工厂布局，设备更题，比如城市中的管道铺设，线路安排，工厂布局，设备更新等等。也可以用于解决其它的最优化问题。新等等。也可以用于解决其它的最优化问题。新等等。也可以用于解决其它的最优化问题。新等等。也可以用于解决其它的最优化问题。本讲稿第二十六页，共九十六页三、三、最短路问题最短路问题l l3.1 3.1 3.1 3.1
32、 引言引言引言引言l l例例6-2 6-2 如图所示的单行线交通网，每个弧旁边的数如图所示的单行线交通网，每个弧旁边的数字表示这条单行线的长度。现在有一个人要从字表示这条单行线的长度。现在有一个人要从v v1 1 1 1出出出出发，经过这个交通网到达发，经过这个交通网到达发，经过这个交通网到达发，经过这个交通网到达v v v v8 8 8 8，要寻求是总路程最短的线路。，要寻求是总路程最短的线路。，要寻求是总路程最短的线路。，要寻求是总路程最短的线路。V1V1V2V2V3V3V4V4V6V6V7V7V8V8V9V9V5V56 63 31 12 21 12 23 34 42 210106 64
33、410103 36 62 2本讲稿第二十七页，共九十六页三、三、最短路问题最短路问题l l3.1 3.1 引言引言l l最短路问题的一般描述：最短路问题的一般描述：l l对对对对D=D=D=D=（V V V V，A A A A），），），），a=a=a=a=（vivivivi，vjvjvjvj），），），），w w w w（a a a a）=wij=wij=wij=wij，P P P P是是是是vsvsvsvs到到到到vtvtvtvt的路，定义路的路，定义路的路，定义路的路，定义路P P P P的权是的权是的权是的权是P P P P中所有弧的权的和，记为中所有弧的权的和，记为中所有弧的权的和，
34、记为中所有弧的权的和，记为w w w w（P P P P）l l则最短路问题为：则最短路问题为：l l路路路路P0P0P0P0的权称为从的权称为从的权称为从的权称为从vsvsvsvs到到到到vtvtvtvt的距离，记为：的距离，记为：的距离，记为：的距离，记为：d d（vs vs，vt vt）本讲稿第二十八页，共九十六页l l3.23.23.23.2最短路算法最短路算法最短路算法最短路算法l l求最短路有两种算法：求最短路有两种算法：求最短路有两种算法：求最短路有两种算法：一是求从某一点至其它各点之间最短离的狄克斯屈拉一是求从某一点至其它各点之间最短离的狄克斯屈拉一是求从某一点至其它各点之间最
35、短离的狄克斯屈拉一是求从某一点至其它各点之间最短离的狄克斯屈拉(Dijkstra)(Dijkstra)(Dijkstra)(Dijkstra)算法算法算法算法 另一种是求网络图上任意两点之间最短路的另一种是求网络图上任意两点之间最短路的另一种是求网络图上任意两点之间最短路的另一种是求网络图上任意两点之间最短路的Floyd(Floyd(Floyd(Floyd(弗洛伊德弗洛伊德弗洛伊德弗洛伊德)矩阵算法。矩阵算法。矩阵算法。矩阵算法。l l下下下下面面面面介介介介绍绍绍绍在在在在一一一一个个个个赋赋赋赋权权权权有有有有向向向向图图图图中中中中寻寻寻寻求求求求最最最最短短短短路路路路的的的的方方方方
36、法法法法DijkstraDijkstraDijkstraDijkstra算算算算法法法法，它它它它是是是是在在在在1959195919591959年年年年提提提提出出出出来来来来的的的的。目目目目前前前前公公公公认认认认，在在在在所所所所有有有有的的的的权权权权wwwwij ij ij ij 0000时时时时，这这这这个个个个算算算算法法法法是是是是寻寻寻寻求求求求最最最最短短短短路路路路问问问问题题题题最最最最好好好好的的的的算算算算法法法法。并并并并且且且且，这这这这个个个个算算算算法法法法实实实实际上也给出了寻求从一个始定点际上也给出了寻求从一个始定点际上也给出了寻求从一个始定点际上也给
37、出了寻求从一个始定点v v v vs s s s到任意一个点到任意一个点到任意一个点到任意一个点v v v vj j j j的最短路。的最短路。的最短路。的最短路。本讲稿第二十九页，共九十六页三、三、最短路问题最短路问题l l3.23.23.23.2最短路算法最短路算法最短路算法最短路算法l l1 1 1 1、DijkstraDijkstraDijkstraDijkstra算法算法算法算法l l基本思路：基本思路：基本思路：基本思路：本讲稿第三十页，共九十六页点标号：点标号：b b(j j)起点起点v vs s到点到点v vj j的最短路长；的最短路长；边标号：边标号：k k(i i，j j)
38、=)=b b(i i)+)+c cijij，步骤：步骤：(1)(1)令起点的标号；令起点的标号；b b(s s)0 0。先求有向图的最短路，设网络图的起点是先求有向图的最短路，设网络图的起点是v vs s,终点是终点是v vt t ,以以v vi i为起点为起点v vj j为终点的弧记为（为终点的弧记为（i i，j j）,距离为距离为c cijij(2)(2)找出所有找出所有v vi i已标号已标号v vj j未标号的弧集合未标号的弧集合 B=(B=(i i，j j)，如果这样的弧不，如果这样的弧不存在或存在或v vt t已标号则计算结束；已标号则计算结束；(3)(3)计算集合计算集合B B中
39、弧中弧k k(i i，j j)=)=b b(i i)+)+c cijij的标号的标号(4)(4)选一个点标号选一个点标号 返回到第返回到第(2)(2)步。步。l l3.23.23.23.2最短路算法最短路算法最短路算法最短路算法 1 1 1 1、DijkstraDijkstraDijkstraDijkstra算法算法算法算法本讲稿第三十一页，共九十六页610123214675811165图图6490610129209186161217162432182929例例6-3 用用Dijkstra算法求图算法求图64 所示所示v1到到v7的最短路及最短路长的最短路及最短路长 v1 到到v7的最短路为：
40、的最短路为：p17=v1,v2,v3,v5,v7，最短路长为，最短路长为L17=29 14本讲稿第三十二页，共九十六页l l从例从例从例从例6-36-36-36-3的计算过程可以看出：的计算过程可以看出：的计算过程可以看出：的计算过程可以看出：l l（1 1 1 1）DijkstraDijkstraDijkstraDijkstra算法可以求某一点算法可以求某一点算法可以求某一点算法可以求某一点vi vi vi vi到其他各点到其他各点到其他各点到其他各点vj vj vj vj的最短路，的最短路，的最短路，的最短路，只要把只要把只要把只要把vj vj vj vj看做路线的终点，使看做路线的终点，
41、使看做路线的终点，使看做路线的终点，使vj vj vj vj得到标号，如果得到标号，如果得到标号，如果得到标号，如果vj vj vj vj不能得到不能得到不能得到不能得到标号，说明标号，说明标号，说明标号，说明vi vi vi vi不可到达不可到达不可到达不可到达vj vj vj vj。（。（。（。（vi vi vi vi到到到到vj vj vj vj不连通）不连通）不连通）不连通）l l（2 2 2 2）DijkstraDijkstraDijkstraDijkstra算法可以求任意两点之间的最短路（最短路算法可以求任意两点之间的最短路（最短路算法可以求任意两点之间的最短路（最短路算法可以求任
42、意两点之间的最短路（最短路存在的话），只要将两个点看做路线的起点和终点，然后存在的话），只要将两个点看做路线的起点和终点，然后存在的话），只要将两个点看做路线的起点和终点，然后存在的话），只要将两个点看做路线的起点和终点，然后进行标号。进行标号。进行标号。进行标号。l l（3 3 3 3）最短路线可能不唯一，但是最短路长相等。）最短路线可能不唯一，但是最短路长相等。）最短路线可能不唯一，但是最短路长相等。）最短路线可能不唯一，但是最短路长相等。l l（4 4 4 4）DijkstraDijkstraDijkstraDijkstra算法的条件是弧长非负，问题求最小值，对于最大算法的条件是弧长非负
43、，问题求最小值，对于最大算法的条件是弧长非负，问题求最小值，对于最大算法的条件是弧长非负，问题求最小值，对于最大值问题无效。值问题无效。值问题无效。值问题无效。本讲稿第三十三页，共九十六页l l练习：用练习：用练习：用练习：用DijkstraDijkstraDijkstraDijkstra求下列有向图求下列有向图求下列有向图求下列有向图V1V1V1V1到到到到V8V8V8V8的最短路径。的最短路径。的最短路径。的最短路径。V1V1V2V2V3V3V4V4V6V6V7V7V8V8V9V9V5V56 63 31 12 21 12 23 34 42 210106 64 410103 36 62 2本
44、讲稿第三十四页，共九十六页无向图最短路的求法无向图最短路的求法无向图最短路的求法只将上述步骤（无向图最短路的求法只将上述步骤（2 2）改动一下即可。）改动一下即可。点标号：点标号：b b(i i)起点起点v vs s到点到点v vj j的最短路长；的最短路长；边标号：边标号：k k(i i，j j)=)=b b(i i)+)+c cijij，步骤：步骤：(1)(1)令起点的标号；令起点的标号；b b(s s)0 0。(3)(3)计算集合计算集合B B中边标号：中边标号：k k i i，j j=b b(i i)+)+c cijij(4)(4)选一个点标号选一个点标号:返回到第返回到第(2)(2)
45、步。步。(2)(2)找出所有一端找出所有一端v vi i已标号另一端已标号另一端v vj j未标号的边集合未标号的边集合 B=B=i i，j j如果这如果这样的边不存在或样的边不存在或v vt t已标号则计算结束；已标号则计算结束；本讲稿第三十五页，共九十六页例例6-4 6-4 求图求图6-56-5所示所示v v1 1到各点的最短路及最短距离到各点的最短路及最短距离4526178393261216180452231039612641166188122482418所有点都已标号，点上的标号就是所有点都已标号，点上的标号就是v1到该点的最短距离，最短路线就是到该点的最短距离，最短路线就是红色的链。
46、红色的链。图图6-5本讲稿第三十六页，共九十六页l练练习习：用用DijkstraDijkstra求求P125P125图图6-106-10中中V1V1到到V7V7的的最短路。（无向图）最短路。（无向图）本讲稿第三十七页，共九十六页三、最短路问题三、最短路问题l l3.23.23.23.2最短路算法最短路算法最短路算法最短路算法l l1 1 1 1、DijkstraDijkstraDijkstraDijkstra算法算法算法算法l l2 2 2 2、求任意两点间最短距离的矩阵算法、求任意两点间最短距离的矩阵算法、求任意两点间最短距离的矩阵算法、求任意两点间最短距离的矩阵算法l lDijkstraD
47、ijkstraDijkstraDijkstra算法提供了从网络图中某一点到其他点的最短算法提供了从网络图中某一点到其他点的最短算法提供了从网络图中某一点到其他点的最短算法提供了从网络图中某一点到其他点的最短距离。但实际问题中往往要求网络任意两点之间的最短距离。但实际问题中往往要求网络任意两点之间的最短距离。但实际问题中往往要求网络任意两点之间的最短距离。但实际问题中往往要求网络任意两点之间的最短距离，如果仍采用距离，如果仍采用距离，如果仍采用距离，如果仍采用DijkstraDijkstraDijkstraDijkstra算法对各点分别计算，就显算法对各点分别计算，就显算法对各点分别计算，就显算
48、法对各点分别计算，就显得很麻烦。得很麻烦。得很麻烦。得很麻烦。l l我们介绍网络各点之间最短距离的矩阵计算法。我们介绍网络各点之间最短距离的矩阵计算法。本讲稿第三十八页，共九十六页l l例例例例6-5 6-5 6-5 6-5 在图中用矩阵算法求各点之间的最短距离。在图中用矩阵算法求各点之间的最短距离。在图中用矩阵算法求各点之间的最短距离。在图中用矩阵算法求各点之间的最短距离。v1v1v2v2v5v5v7v7v6v6v3v3v4v45 52 27 72 27 76 61 12 23 36 64 4l l例例例例6-5 6-5 6-5 6-5【解】【解】【解】【解】l l定义定义定义定义dijdi
49、jdijdij为图中两相为图中两相为图中两相为图中两相邻点的距离，若邻点的距离，若邻点的距离，若邻点的距离，若i i i i与与与与j j j j不相邻，令不相邻，令不相邻，令不相邻，令dij=dij=dij=dij=，由此，由此，由此，由此本讲稿第三十九页，共九十六页l l上页的邻接矩阵表示上页的邻接矩阵表示上页的邻接矩阵表示上页的邻接矩阵表示vivivivi一步到达一步到达一步到达一步到达vjvjvjvj的最短距离矩阵。的最短距离矩阵。的最短距离矩阵。的最短距离矩阵。l l但从但从但从但从vivivivi到到到到vjvjvjvj的最短路不一定是的最短路不一定是的最短路不一定是的最短路不一定
50、是vivivivi直接到达直接到达直接到达直接到达vjvjvjvj的，可能是的，可能是的，可能是的，可能是通过通过通过通过vivivivi与与与与vjvjvjvj之间的一个或多个中间点实现最短路。之间的一个或多个中间点实现最短路。之间的一个或多个中间点实现最短路。之间的一个或多个中间点实现最短路。l l所以，在一步到达的邻接矩阵的基础上，计算所以，在一步到达的邻接矩阵的基础上，计算vivi两两步到达步到达vjvj的最短距离矩阵：的最短距离矩阵：vivjvivj经两步到达的最短路：经两步到达的最短路：第第i i行行+第第j j行对应元素中的行对应元素中的minmin本讲稿第四十页，共九十六页构造