《图论与网络分析幻灯片.ppt》由会员分享，可在线阅读，更多相关《图论与网络分析幻灯片.ppt（50页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、图论与网络分析图论与网络分析第1页，共50页，编辑于2022年，星期五1818世纪，哥尼斯堡城中有一条普雷格尔河，河上有七座桥将河中的两个小岛与世纪，哥尼斯堡城中有一条普雷格尔河，河上有七座桥将河中的两个小岛与河岸连接起来。人们提出了这样的问题：一个散步者能否从某地出发，走遍七桥且河岸连接起来。人们提出了这样的问题：一个散步者能否从某地出发，走遍七桥且每座桥恰好经过一次，最后回到原地？每座桥恰好经过一次，最后回到原地？陆地A陆地B岛D岛CAD B C 17361736年年瑞瑞士士数数学学家家欧欧拉拉将将两两岸岸和和小小岛岛抽抽象象为为四四个个点点，将将桥抽象为七条边，此问题归结为一笔画问题。桥
2、抽象为七条边，此问题归结为一笔画问题。图论起源图论起源第2页，共50页，编辑于2022年，星期五第一节第一节 图论的概念图论的概念图论的图与一般几何图形或函数图形是完全不同的图论的图与一般几何图形或函数图形是完全不同的p图论中的图图论中的图:由一些点和连接点的线所组成的由一些点和连接点的线所组成的“图形图形”p点和线的位置是任意的点和线的位置是任意的p线的曲直、长短与实际无关，代表的只是点与点之间的相线的曲直、长短与实际无关，代表的只是点与点之间的相互关系互关系v1v2v3 v4v1v2v3 v4第3页，共50页，编辑于2022年，星期五34512无向图的基本概念无向图的基本概念 G=(V,E
3、)V=viG的顶点集合的顶点集合E=ek G的边集合的边集合，且且ek=（vi,vj）为无序二元组）为无序二元组,表示表示ek连接连接vi,vjn(G)=|V|=nG的顶点数的顶点数m(G)=|E|=mG的边数的边数顶点相邻顶点相邻 两顶点之间有一条边，顶点两顶点之间有一条边，顶点为该边的端点，边与其端点为该边的端点，边与其端点关联。关联。边相邻边相邻e1e2e3e4e5e6e7 两边与同一顶点关联，两边与同一顶点关联，即两边有共同的端点。即两边有共同的端点。环环两端点重合为一点的边，如两端点重合为一点的边，如e1多重边多重边两点之间多于一条边，如两点之间多于一条边，如e6，e7简单图简单图不
4、含环和多重边的图，去掉不含环和多重边的图，去掉e1和和e7.（不特指都是简（不特指都是简单图）单图）完全图完全图每对顶点之间都有边相连每对顶点之间都有边相连的无向简单图，的无向简单图，n个顶点个顶点的无向完全图记为的无向完全图记为Kn次次与顶点与顶点v相关联的边数，即相关联的边数，即以以v为顶点的边数记为为顶点的边数记为d(v),环记环记2次。次。d(1)=4.奇点，偶点奇点，偶点次为奇数的点为奇点，次为次为奇数的点为奇点，次为偶数的点为偶点。偶数的点为偶点。次为次为1的点为悬挂点。的点为悬挂点。若若4，5之间有一条边，则之间有一条边，则5为悬挂点。为悬挂点。孤立点孤立点次为次为0的点为孤立点
5、，的点为孤立点，5为孤为孤立点。立点。Kn有边有边 条条悬挂点悬挂点第4页，共50页，编辑于2022年，星期五无向图的基本概念无向图的基本概念 二部图：图G=(V,E)，顶点集合V可分为两个非空子集X,Y，知XY=V，XY=，E中每条边的两个端点，一个在X中，一个在Y中，则称G为二部图，记为G=（X,Y,E）v1v2v3 v4v2v4v3 v1第5页，共50页，编辑于2022年，星期五有向图的基本概念有向图的基本概念 G=(V,E)V=vi：G的顶点集合的顶点集合E=ek：G的有向边的有向边(弧弧)集合集合，且且ek=（vi,vj）为有序二元组）为有序二元组,表示弧表示弧ek从从vi（始点）（
6、始点）指向指向vj（终点）（终点）环环有向图中，始点、终点重合的有向图中，始点、终点重合的弧为环，如弧为环，如e1多重边多重边始点和终点都相同的弧为始点和终点都相同的弧为多重边，如多重边，如e6，e7非多非多重边。重边。简单有向图简单有向图不含环和多重边的有向图，不含环和多重边的有向图，去掉去掉e1有向完全图有向完全图以任意点为始点，另一点为终点以任意点为始点，另一点为终点都有一条弧的简单有向图，都有一条弧的简单有向图，n个顶点的有向完全图有弧个顶点的有向完全图有弧n(n-1)条条出次，入次，次出次，入次，次34512e1e2e3e4e5e6e7以顶点以顶点v为始点的弧数为为始点的弧数为v的出
7、次，记的出次，记为为 ；以顶点；以顶点v为终点的弧数为为终点的弧数为v的入次，记为的入次，记为 ；顶点；顶点v的出次的出次与入次之和为点与入次之和为点v的次。的次。第6页，共50页，编辑于2022年，星期五网络（赋权图）网络（赋权图）在无向图的边（或有向图的弧）上标上实数，称在无向图的边（或有向图的弧）上标上实数，称为该边（或弧）的权，无向（有向）图连同它边为该边（或弧）的权，无向（有向）图连同它边上的权称为一个网络赋权图，简称网络。（无向上的权称为一个网络赋权图，简称网络。（无向网络，有向网络）网络，有向网络）第7页，共50页，编辑于2022年，星期五子图子图34512e1e2e3e4e5e
8、6e7412e2e3e4e53412e2e3e4e5第8页，共50页，编辑于2022年，星期五道路，回路道路，回路34512e1e2e3e4e5e6e734512e1e2e3e4e5e6e7第9页，共50页，编辑于2022年，星期五连通图连通图p点点i和和j点是连通的：点是连通的：i,j之间存在一条链之间存在一条链pG是连通的：是连通的：G中任意两点都是连通的中任意两点都是连通的 p不连通图可以分为若干连通子图，每个称为不连通图可以分为若干连通子图，每个称为原图的分图。原图的分图。第10页，共50页，编辑于2022年，星期五关联矩阵关联矩阵图的矩阵表示图的矩阵表示第11页，共50页，编辑于20
9、22年，星期五关联矩阵示例关联矩阵示例右图的关联矩阵是右图的关联矩阵是 右图的关联矩阵是右图的关联矩阵是 134521342e1e2e4e7e6e5e8e3e1e2e3e4e5第12页，共50页，编辑于2022年，星期五邻接矩阵邻接矩阵第13页，共50页，编辑于2022年，星期五邻接矩阵示例右图的邻接矩阵是右图的邻接矩阵是 右图的邻接矩阵是右图的邻接矩阵是 134521342第14页，共50页，编辑于2022年，星期五主要结论主要结论第15页，共50页，编辑于2022年，星期五图论基本概念应用图论基本概念应用p例例1：证明在：证明在9座工厂之间，不可能每座工厂只与其他座工厂之间，不可能每座工厂
10、只与其他3座座工厂有业务联系，也不可能只有工厂有业务联系，也不可能只有4座工厂与偶数个工厂有座工厂与偶数个工厂有业务联系。业务联系。将将9座工厂看做座工厂看做9个点，他们有联系用边相连，若每座工厂个点，他们有联系用边相连，若每座工厂只与其他只与其他3座工厂有业务联系，则每个点的次都为座工厂有业务联系，则每个点的次都为3，从而，从而总次为总次为27，非偶数，与总次为边的，非偶数，与总次为边的2倍矛盾。从而得证。倍矛盾。从而得证。若只有若只有4座工厂与偶数个工厂有业务联系，则其余座工厂与偶数个工厂有业务联系，则其余5座与奇座与奇数个工厂有业务联系，从而总次为数个工厂有业务联系，从而总次为 4*偶偶
11、+5*奇奇=奇数奇数非偶数，矛盾。从而得证。非偶数，矛盾。从而得证。第16页，共50页，编辑于2022年，星期五例例2：6个人围成圆圈就座，每个人恰好只与相邻者不认识，是否可个人围成圆圈就座，每个人恰好只与相邻者不认识，是否可以重新就座，使每个人都与邻座认识？以重新就座，使每个人都与邻座认识？将将6个人看做个人看做6个点，相互认识用边表示个点，相互认识用边表示162345要求重排之后每个人与邻座认识只要求重排之后每个人与邻座认识只需找到一个序列，该序列中前后两需找到一个序列，该序列中前后两个点是相邻的就可以了。如个点是相邻的就可以了。如1-3-5-2-6-4-1143526第17页，共50页，
12、编辑于2022年，星期五例例3 甲、乙、丙、丁、戊甲、乙、丙、丁、戊5个运动员报名参加个运动员报名参加A,B,C,D,E，F六个项六个项目比赛，报名情况见下表（打目比赛，报名情况见下表（打*表示各运动员报名参加的比赛项目）。表示各运动员报名参加的比赛项目）。问如何安排项目，使每名运动员不连续参加两项比赛？问如何安排项目，使每名运动员不连续参加两项比赛？将将6个项目看做个项目看做6个点，同一个人参加的项目之间有边个点，同一个人参加的项目之间有边要求安排项目，每名运动员不连续参要求安排项目，每名运动员不连续参加两项比赛，只需找到一个遍历点的加两项比赛，只需找到一个遍历点的序列，该序列中前后两个点是
13、不相邻序列，该序列中前后两个点是不相邻的就可以了。如的就可以了。如A-C-D-E-F-BA AB BC CD DE EF F甲甲*乙乙*丙丙*丁丁*戊戊*ABCDEF第18页，共50页，编辑于2022年，星期五练习练习 10个研究生参加个研究生参加6门课考试，每个研究生考试课程见下表，门课考试，每个研究生考试课程见下表，要求上下午各排一门课，每人每天最多考一门，且要求上下午各排一门课，每人每天最多考一门，且A必须第一必须第一天上午，天上午，F必须最后考，必须最后考，B要安排在下午考，试给出一个考试安排表。要安排在下午考，试给出一个考试安排表。A AB BC CD DE EF F1 1*2 2*
14、3 3*4 4*5*6*7*8*9*10*AECBDF第19页，共50页，编辑于2022年，星期五欧拉回路欧拉回路n连通图连通图G中若存在一条道路，经每边一次且仅一次，则中若存在一条道路，经每边一次且仅一次，则该道路为欧拉道路该道路为欧拉道路n若存在一条回路，经每边一次且仅一次，该回路为欧拉若存在一条回路，经每边一次且仅一次，该回路为欧拉回路。回路。n有欧拉回路的图称为欧拉图。有欧拉回路的图称为欧拉图。第20页，共50页，编辑于2022年，星期五结论：结论：pTh1：无向连通图无向连通图G为欧拉图充要条件是为欧拉图充要条件是G中无奇点。中无奇点。pTh2：无向连通图无向连通图G为欧拉图充要条件
15、是为欧拉图充要条件是G的边集可分为的边集可分为若干初等回路。若干初等回路。pTh3：无相连通图无相连通图G为欧拉道路充要条件是为欧拉道路充要条件是G中恰有中恰有2个个奇点。奇点。pTh4：连通有向图连通有向图G为欧拉图充要条件是他每个顶点的出为欧拉图充要条件是他每个顶点的出次等于入次。次等于入次。pTh5：连通有向图连通有向图G为欧拉道路充要条件是这个图中除了为欧拉道路充要条件是这个图中除了两个顶点之外，其余每个顶点出次等于入次，且这两顶点两个顶点之外，其余每个顶点出次等于入次，且这两顶点中，一个顶点入次比出次多中，一个顶点入次比出次多1，另一个出次比入次多，另一个出次比入次多1.第21页，共
16、50页，编辑于2022年，星期五一个散步者能否从某地出发，走遍七桥且每座桥恰好经过一个散步者能否从某地出发，走遍七桥且每座桥恰好经过一次，最后回到原地？一次，最后回到原地？即是否存在欧拉回路？即是否存在欧拉回路？陆地A陆地B岛D岛CAD B C每点都是奇点，所以不是欧拉图，即不存在欧拉回路。每点都是奇点，所以不是欧拉图，即不存在欧拉回路。如果存在欧拉回路，如何找到该回路？如果存在欧拉回路，如何找到该回路？第22页，共50页，编辑于2022年，星期五欧拉回路的构造方法欧拉回路的构造方法p从从G中任意点中任意点v1出发找到一个初等回路出发找到一个初等回路c1，再从图中，再从图中去掉去掉c1，在剩余
17、的图中再找初等回路，在剩余的图中再找初等回路c2，一，一直找到图中所有的边都被包含在这些初等回路中为止，直找到图中所有的边都被包含在这些初等回路中为止，最后把这些回路连续起来即得该图的欧拉回路。最后把这些回路连续起来即得该图的欧拉回路。第23页，共50页，编辑于2022年，星期五下面两个图是否可以一笔画出？下面两个图是否可以一笔画出？V3V1V2V6V5V412345678910(2，e23,3,e34,4,e41,1,e12,2,e27,7,e75,5,e56,6,e67,7,e79,9,e910,10,e108,8,e89,9,e93,3,e310,10,e104,4,e48,8,e86,
18、6,e61,1,e15,5)第24页，共50页，编辑于2022年，星期五第二节第二节 最小树问题最小树问题 一、树的定义与树的特征一、树的定义与树的特征定义定义 连通且不含圈的无向图称为连通且不含圈的无向图称为树树常用常用T表示表示.树中的边称为树中的边称为树枝树枝.树中次为树中次为1的顶点称为的顶点称为树叶树叶，次，次大于大于1的点为的点为分枝点分枝点。第25页，共50页，编辑于2022年，星期五定理定理 设设T是具有是具有n个顶点的图，则下述命题等价：个顶点的图，则下述命题等价：1)T是树（是树（T无圈且连通）；无圈且连通）；2)T无圈，且有无圈，且有n-1条边；条边；3)T连通，且有连通
19、，且有n-1条边；条边；4)T无圈，但添加任一条新边恰好产生一个圈无圈，但添加任一条新边恰好产生一个圈;5)T连通，且删去一条边就不连通了连通，且删去一条边就不连通了6)T中任意两顶点间有唯一一条路中任意两顶点间有唯一一条路.第26页，共50页，编辑于2022年，星期五二、图的生成树二、图的生成树定义定义 若若T是包含图是包含图G的全部顶点的子图的全部顶点的子图,它又是树它又是树,则称则称T是是G的的生成树生成树.图图G中不在生成树的边叫做中不在生成树的边叫做弦弦.定理定理 图图G=(V,E)有生成树的充要条件是图有生成树的充要条件是图G是连是连 通的通的.找图中生成树的方法找图中生成树的方法
20、可分为两种：避圈法和破圈法可分为两种：避圈法和破圈法 A 避圈法避圈法:深探法和广探法深探法和广探法 B 破圈法破圈法 第27页，共50页，编辑于2022年，星期五A 避圈法避圈法 这种方法就是在已给的图这种方法就是在已给的图G中，每步选出一条边使它与中，每步选出一条边使它与已选边不构成圈，直到选够已选边不构成圈，直到选够n-1条边为止条边为止.这种方法可称这种方法可称为为“避圈法避圈法”或或“加边法加边法”在避圈法中，按照边的选法不同，找图中生成树的方法在避圈法中，按照边的选法不同，找图中生成树的方法可分为两种：可分为两种：深探法深探法和和广探法广探法.第28页，共50页，编辑于2022年，
21、星期五a)深探法深探法 若这样的边的另一端均已有标号，就退到标号为若这样的边的另一端均已有标号，就退到标号为步骤如下：步骤如下：i)在点集在点集V中任取一点中任取一点u,ii)若某点若某点v已得标号，检已得标号，检端是否均已标号端是否均已标号.若有边若有边(v,w)之之w未标号未标号,则给则给w代代v，重复，重复ii).i-1的的r点点,以以r代代v,重复重复ii),直到全部点得到标号为止直到全部点得到标号为止.给以标号给以标号0.查一端点为查一端点为v的各边，另一的各边，另一w以标号以标号i+1，记下边，记下边(v,w).令令例用深探法求出下图的一棵生成树例用深探法求出下图的一棵生成树 01
22、2345678910111213第29页，共50页，编辑于2022年，星期五13a)深探法深探法0123456789101112例用深探法求出下图的一棵生成树例用深探法求出下图的一棵生成树 012345789101112136第30页，共50页，编辑于2022年，星期五3b)广探法广探法步骤如下：步骤如下：i)在点集在点集V中任取一点中任取一点u,ii)令所有标号令所有标号i的点集为的点集为是否均已标号是否均已标号.对所有未标对所有未标号之点均标以号之点均标以i+1,记下这些记下这些 iii)对标号对标号i+1的点重复步的点重复步步骤步骤ii)，直到全部点得到，直到全部点得到给给u以标号以标号
23、0.Vi,检查检查Vi,VVi中的边端点中的边端点边边.例用广探法求出下图的一棵生成树例用广探法求出下图的一棵生成树 1012213212234标号为止标号为止.第31页，共50页，编辑于2022年，星期五3b)广探法广探法例用广探法求出下图的一棵生成树例用广探法求出下图的一棵生成树 1012213212234显然图的生成树不唯一显然图的生成树不唯一.04321111222233第32页，共50页，编辑于2022年，星期五B 破圈法 相对于避圈法，还有一种求生成树的方法叫做相对于避圈法，还有一种求生成树的方法叫做“破圈破圈法法”.这种方法就是在图这种方法就是在图G中任取一个圈，任意舍弃一中任取
24、一个圈，任意舍弃一条边，将这个圈破掉，重复这个步骤直到图条边，将这个圈破掉，重复这个步骤直到图G中没有圈中没有圈为止为止.例例 用破圈法求出用破圈法求出下图的一棵生成树下图的一棵生成树.第33页，共50页，编辑于2022年，星期五B B 破圈法破圈法例例 用破圈法求出下图的另一棵生成树用破圈法求出下图的另一棵生成树.不难发现，图不难发现，图的生成树不是的生成树不是唯一的唯一的.第34页，共50页，编辑于2022年，星期五三、三、最小生成树与算法最小生成树与算法 介绍最小树的两种算法：介绍最小树的两种算法：Kruskal算法算法（或（或避圈法避圈法）和）和破圈法破圈法.第35页，共50页，编辑于
25、2022年，星期五A Kruskal算法（或避圈法）算法（或避圈法）步骤如下：步骤如下：1)选择边选择边e1，使得，使得w(e1)尽可能小；尽可能小；2)若已选定边若已选定边 ，则从，则从中选取中选取 ，使得，使得:i)为无圈图，为无圈图，ii)是满足是满足i)的尽可能小的权，的尽可能小的权，3)重复步骤重复步骤2），直至选够），直至选够n-1条边条边.定理定理 由由Kruskal算法构作的任何生成树算法构作的任何生成树都是最小树都是最小树.第36页，共50页，编辑于2022年，星期五例例用用Kruskal算法求下图的最小树算法求下图的最小树.在左图中在左图中 权值权值最小的边有最小的边有 任
26、取一条任取一条 在在 中选取权值中选取权值最小的边最小的边 中权值最小边有中权值最小边有 ,从中选从中选任取一条边任取一条边中选取在中选取中选取在中选取已经选够已经选够5-1条边，从而最小树构条边，从而最小树构造结束。造结束。第37页，共50页，编辑于2022年，星期五B破圈法算法算法2 步骤如下：步骤如下：1)从图从图G中任选一棵树中任选一棵树T1.2)加上一条弦加上一条弦e1，T1+e1中中 立即生成一个圈立即生成一个圈.去掉此去掉此 圈中最大权边，得到新圈中最大权边，得到新树树T2,以以T2代代T1,重复重复2)再再检查剩余的弦，直到全检查剩余的弦，直到全部弦检查完毕为止部弦检查完毕为止
27、.例例用破圈法求下图的最小树用破圈法求下图的最小树.先求出上图的一棵生成树先求出上图的一棵生成树.加以弦加以弦 e2,得到的圈得到的圈v1v3v2v1,去掉最大的权边去掉最大的权边e2,得到一棵新得到一棵新树仍是原来的树；树仍是原来的树；再加上弦再加上弦e7，得到圈，得到圈 v4v5v2v4,去掉最大的权边去掉最大的权边e6，得到一棵，得到一棵新树；如此重复进行，直到全新树；如此重复进行，直到全部的弦均已试过部的弦均已试过,得得最小树最小树.第38页，共50页，编辑于2022年，星期五例：一家企业分别要在例：一家企业分别要在6 6间办公室铺设网线接入口，间办公室铺设网线接入口，网线的可行走线方
28、式如下图所示，如何铺设网线才能使网线的可行走线方式如下图所示，如何铺设网线才能使网线总长为最短？网线总长为最短？最短网线总长度为最小树权之和最短网线总长度为最小树权之和2+3+4+6+6=21 8 2 3 546 6 6 8v1v4v2v3v5v6第39页，共50页，编辑于2022年，星期五第三节第三节 最短路问题最短路问题 狄克斯特拉狄克斯特拉(Dijkstra)算法算法p路权：弧路权：弧(vi,vj)的权为的权为lij；路权是路；路权是路p中各条弧权之中各条弧权之 和和p最短路：在所有从最短路：在所有从vs到到vt 的路的路p中，求一条路权最短的路中，求一条路权最短的路p算法说明：算法说明
29、：n1959年提出，目前公认的最短路算法年提出，目前公认的最短路算法n适合于求解所有弧权适合于求解所有弧权wij 0的最短路问题的最短路问题第40页，共50页，编辑于2022年，星期五第三节第三节 最短有向路问题最短有向路问题p基本思路基本思路:n从始点从始点v vs s 出发，逐步探寻，给每个点标号；出发，逐步探寻，给每个点标号；n标号分永久标号标号分永久标号P(vP(vk k)和临时标号和临时标号T(vT(vk k)两种：两种：p永久标号永久标号P(vk)是从点是从点 vs vk 的最短路权的最短路权p临时标号临时标号T(vk)是从点是从点 vs vk 最短路权的上界最短路权的上界n算法的
30、每一步从临时标号集中选最小者变为永久标号；算法的每一步从临时标号集中选最小者变为永久标号；n经过逐次改变，就可以得到从点经过逐次改变，就可以得到从点v vs s 到各点的最短路到各点的最短路p标号形式：n单标号法是对每一点赋予一个路权标号单标号法是对每一点赋予一个路权标号n双标号法是对每一点赋予两个标号：路标、路权双标号法是对每一点赋予两个标号：路标、路权。第41页，共50页，编辑于2022年，星期五狄克斯特拉(Dijkstra)算法步骤第42页，共50页，编辑于2022年，星期五 例：从发电厂（记为节点1）向某城市（记为节点6）输送电，必须通过中转站（记为节点2，3，4，5）转送。图给出了两
31、节点间的距离。电力公司希望选择合适的中转站，使从电厂到城市的传输路线最短。即从节点1到节点6的最短路径。这就是一个最短路问题。第43页，共50页，编辑于2022年，星期五单标号求最短路单标号求最短路1325464332322 第0步：P(1)=0,T(i)=+；第1步：与1相连的标号为2,3，均是T标号，修改2,3的标号，T(2)=minT(2),P(1)+l12=4,T(3)=3；在所有的T标号中，3的标号最小，改3的标号为P(3)=3；第2步：修改与3相连的T标号；在所有剩下的T标号中，2的标号最小，改为P(2)=4；第3步：修改与2相连的T标号；在所有剩下的T标号中，5的标号最小，改为P
32、(5)=6；第4步：修改与5相连的T标号；在所有剩下的T标号中，4的标号最小，改为P(4)=7；第5步：修改与4相连的T标号；只剩下节点6是T标号，修改6的标号，P(6)=8。从节点6开始回退，得到最短路。P(1)=0T(3)=+T(2)=+T(3)=3T(5)=+P(3)=3T(5)=6T(2)=4T(4)=+T(6)=+P(2)=4T(4)=7P(5)=6T(6)=8P(4)=7P(6)=8P(6)=8P(5)=6P(3)=3P(1)=0第44页，共50页，编辑于2022年，星期五例：双标号法求下图网络最短路例：双标号法求下图网络最短路3947326141287110第45页，共50页，编
33、辑于2022年，星期五第一步：第一步：3947326141287110第46页，共50页，编辑于2022年，星期五第二步：第二步：3947326141287110第47页，共50页，编辑于2022年，星期五第三步：第三步：3947326141287110第48页，共50页，编辑于2022年，星期五最终：最终：依此类推，重复上述标号过程。得最短路。依此类推，重复上述标号过程。得最短路。3947326141287110第49页，共50页，编辑于2022年，星期五练习：求下图中练习：求下图中v1到到v8的最短距离的最短距离v1v2v3v4v5v6v7v84644594157576v8（v1，4）（v1，6）（v2，8）（v2，9）（v5，13）（v5，14）（v7，15）（v1，0）v7v5v2v1第50页，共50页，编辑于2022年，星期五