第七章图PPT讲稿.ppt

《第七章图PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第七章图PPT讲稿.ppt（70页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第七章图第1页，共70页，编辑于2022年，星期一第七章 图v7.1 图的定义和术语图(Graph)图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对或有序对有向图有向图G是由两个集合V(G)和E(G)组成的 其中：V(G)是顶点的非空有限集 E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为，v,w是顶点，v为弧尾，w为弧头第2页，共70页，编辑于2022年，星期一第七章 图无向图无向图G是由两个集合V(G)和E(G)组成的 其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对

2、，记为（v,w）或（w,v)，并且（v,w)=(w,v)第3页，共70页，编辑于2022年，星期一例245136G1图G1中：V(G1)=1,2,3,4,5,6 E(G1)=,例157324G26图G2中：V(G2)=1,2,3,4,5,6,7 E(G1)=(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)第4页，共70页，编辑于2022年，星期一7.1 图的定义和术语有向完备图n个顶点的有向图最大边数是n(n-1)无向完备图n个顶点的无向图最大边数是n(n-1)/2例213213有向完备图无向完备图权与图的边或弧相关的数叫网带权的图叫第5页，共70页，编辑于2

3、022年，星期一7.1 图的定义和术语子图如果图G(V,E)和图G(V,E),满足：VV,EE,则称G为G的子图356例245136图与子图第6页，共70页，编辑于2022年，星期一7.1 图的定义和术语顶点的度v无向图中，顶点的度为与每个顶点相连的边数v有向图中，顶点的度分成入度与出度入度：以该顶点为头的弧的数目出度：以该顶点为尾的弧的数目v一个有n个顶点和e条边或弧的图，满足：例245136G1顶点2入度：1 出度：3顶点4入度：1 出度：0例157324G26顶点5的度：3顶点2的度：4第7页，共70页，编辑于2022年，星期一7.1 图的定义和术语路径路径是顶点的序列V=Vi,0,Vi

4、,1,Vi,n,满足(Vi,j-1,Vi,j)E,或E(1jn)路径长度沿路径边的数目或沿路径各边权值之和回路第一个顶点和最后一个顶点相同的路径叫简单路径序列中顶点不重复出现的路径叫简单回路除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫第8页，共70页，编辑于2022年，星期一例157324G26例245136G1路径：1，2，3，5，6，3路径长度：5简单路径：1，2，3，5回路：1，2，3，5，6，3，1简单回路：3，5，6，3路径：1，2，5，7，6，5，2，3路径长度：7简单路径：1，2，5，7，6回路：1，2，5，7，6，5，2，1简单回路：1，2，3，1第9页，共70页

5、，编辑于2022年，星期一7.1 图的定义和术语v图的连通性连通从顶点V到顶点W有一条路径，则说V和W是连通的。无向图的连通性v连通图无向图中任意两个顶点都是连通的叫v连通分量非连通图的每一个连通部分叫ABCDEFGIJLHMKABCDEHMFGIJLK无向图G3无向图G3的三个连通分量第10页，共70页，编辑于2022年，星期一7.1 图的定义和术语有向图的连通性v强连通图有向图中，如果对每一对Vi,VjV,ViVj,从Vi到Vj 和从Vj到 Vi都存在路径，则称G是v强连通分量：非强连通图的每一个强连通部分叫例245136强连通图356例强连通分量第11页，共70页，编辑于2022年，星期

6、一7.2 图的存储结构v多重链表例G12413例15324G2V1V2 V4 V3 V1 V2 V4 V5 V3第12页，共70页，编辑于2022年，星期一7.2 图的存储结构v邻接矩阵表示顶点间相联关系的矩阵定义：设G=(V,E)是有n1个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵第13页，共70页，编辑于2022年，星期一7.2 图的存储结构例G12413例15324G2第14页，共70页，编辑于2022年，星期一7.2 图的存储结构特点：v无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2v有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为nv无

7、向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行（列）元素之和v有向图中，顶点Vi的出度是A中第i行元素之和顶点Vi的入度是A中第i列元素之和第15页，共70页，编辑于2022年，星期一7.2 图的存储结构特点：v网络的邻接矩阵可定义为：例1452375318642第16页，共70页，编辑于2022年，星期一7.2 图的存储结构v关联矩阵表示顶点与边的关联关系的矩阵定义：设G=(V,E)是有n1个顶点，e0条边的图，G的关联矩阵A是具有以下性质的ne阶矩阵第17页，共70页，编辑于2022年，星期一4321例G124131234例15324G2123456432156第18页，共70页，编辑

8、于2022年，星期一例BDAC123456ABCD432156第19页，共70页，编辑于2022年，星期一7.2 图的存储结构特点v关联矩阵每列只有两个非零元素，是稀疏矩阵；n越大，零元素比率越大。v无向图中顶点Vi的度TD(Vi)是关联矩阵A中第i行元素之和。v有向图中，顶点Vi的出度是A中第i行中“1”的个数。顶点Vi的入度是A中第i行中“-1”的个数。第20页，共70页，编辑于2022年，星期一7.2 图的存储结构v邻接表表示顶点与边的关联关系是图的一种链式存储结构，适用于有向图和无向图。为图中每个顶点vi建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的

9、弧）,即所有邻接（于）vi的顶点vj链成一个单链表（称为关于vi的邻接表）。v邻接表中每个表结点都有两个域：邻接点域 adjvex和链域 next；另外若要表示边上的信息如（权值）,则在表结点中还应增加一个数据域cost.typedef struct node int adjvex;/邻接点域，存放与Vi邻接的顶点的序号 struct node *next;/链域，将邻接表的所有表点链在一起JD;adjvex next第21页，共70页，编辑于2022年，星期一表头接点：typedef struct tnode int vexdata;/存放顶点信息 struct node *firstarc

10、;/vi的邻接表的头指针，指示第一个邻接点TD;TD gM;/g0不用vexdata firstarc7.2 图的存储结构每个顶点vi的邻接表设置一个表头结点，头结点包含两个域，顶点域 vexdata和指针域 firstarc，它是。为了便于随机访问任意顶点的邻接表，将所有头结点顺序存储在一个数组中,这样就构成了图的邻接表表示第22页，共70页，编辑于2022年，星期一例G1bdac例aecbdG21234acdbvexdata firstarc 3 2 4 1adjvex next1234acdbvexdata firstarc 4 2 1 2adjvex next5e 4 3 5 1 5

11、3 2 3第23页，共70页，编辑于2022年，星期一7.2 图的存储结构特点v无向图中顶点Vi的度为第i个单链表中的结点数v有向图中顶点Vi的出度为第i个单链表中的结点个数顶点Vi的入度为整个单链表中邻接点域值是i的结点个数v优点：易找到任一顶点的第一个邻接点和下一个邻接点v缺点：判定任意两个顶点之间是否有边或弧相连的办法：搜索第i和第j个单链表。不及邻接矩阵方便。第24页，共70页，编辑于2022年，星期一7.2 图的存储结构逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表例G1bdac1234acdbvexdata firstarc 4 1 1 3adjvex next第25页，共

12、70页，编辑于2022年，星期一void creategraph(int n,TD g)int e,i,s,d;struct node*p,*q;printf(input number_edge(e):);/*输入边的数目存入e中*/scanf(%d,&e);for(i=1;i=n;i+)getchar();printf(“the%d information:”,i);/*提示输入顶点信息*/scanf(%c,&gi.vexdata);gsi.firstarc=NULL;for(i=1;in:,i);/*输入边信息*/scanf(%d,%d,&s,&d);p=(JD*)malloc(sizeo

13、f(JD);/*开辟存储边的空间*/q=(JD*)malloc(sizeof(JD);p-adjvex=d;p-next=gs.firstarc;gs.firstarc=p;/*p和s的firstarc指针连接起来*/q-adjvex=s;q-next=gd.firstarc;gd.firstarc=q;/*q和s的firstarc指针连接起来*/*完成一个边的创建*/输入顶点及边的信息，建立无向图邻接表vexdata firstarcadjvex next第26页，共70页，编辑于2022年，星期一void defarc(int xMM,int n,TD g)int i,j;JD*p;for

14、(i=0;in;i+)gi+1.vexdata=i;gi+1.firstarc=NULL;for(j=0;jadjvex=j+1;p-next=gi+1.firstarc;gi+1.firstarc=p;12341342 2 7 8 355 6 4 1 5 1 2 8 2 678678 7 3 6 3 5 4邻接矩阵X99函数defarc（）：由图的邻接矩阵建立邻接表第27页，共70页，编辑于2022年，星期一7.3 图的遍历v定义：从图中某个顶点出发遍访图中其余顶点，且使每个顶点仅被访问一次的过程.v实质：对图的每个顶点查找邻接点的过程。其遍历算法是求解图的连通性、拓扑排序、求关键路径等算法

15、的基础。v图的两种遍历方式(有向图和无向图均适用)：深度优先搜索DFS（Depth First Search）广度优先搜索BFS(Breadth First Search)第28页，共70页，编辑于2022年，星期一7.3 图的遍历v深度优先遍历(DFS)从图中某个顶点V0 出发，访问此顶点。依次从V0的各个未被访问的邻接点出发深度优先遍历图，直至图中所有和V0有路径相通的顶点都被访问到。若图中还有顶点未被访问，另选图中一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。V1V2V4V5V3V7V6V8例深度遍历：V1 V2 V4 V8 V5 V3 V6 V7(遍历序列不

16、唯一)v1 v3 v7 v6 v2 v5 v8 v4第29页，共70页，编辑于2022年，星期一V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8深度遍历：V1 V2 V4 V8 V5 V6 V3 V7深度遍历：V1 V2 V4 V8 V5 V6 V3 V7第30页，共70页，编辑于2022年，星期一V1V2V4V5V3V7V6V8例深度遍历：V1 V2 V4 V8 V3 V6 V7 V5第31页，共70页，编辑于2022年，星期一7.3 图的遍历深度优先遍历算法v递归算法(图采用邻接表表示)V1V2V4V5V3V7V6V8例深度遍历：V112341342vexdatafir

17、starc 2 7 8 3adjvexnext55 6 4 1 5 1 2 8 2678678 7 3 6 3 5 4V3 V7 V6 V2 V5 V8 V4第32页，共70页，编辑于2022年，星期一递归算法(图采用邻接表表示)开始访问V,置标志求V邻接点有邻接点p求下一邻接点pVp访问过结束NYNYDFS开始标志数组初始化i=1Vi访问过DFSi=i+1in结束NNYY第33页，共70页，编辑于2022年，星期一int visitedM;void traver(TD g,int n)int i;for(i=1;i=n;i+)visitedi=0;/*设置每个顶点为未访问*/for(i=1;

18、iadjvex;if(visitedi=0)dfs(g,i);p=p-next;12341342 2 7 8 355 6 4 1 5 1 2 8 2678678 7 3 6 3 5 4函数dfs（）：对顶点V进行遍历第35页，共70页，编辑于2022年，星期一V1V2V4V5V3V7V6V8例12341342vexdata firstarc 2 7 8 3adjvex next55 6 4 8 2678678 7深度遍历：V1V3 V7 V6 V2 V4 V8 V5第36页，共70页，编辑于2022年，星期一V1V2V4V5V3V7V6V8例广度遍历：V1 V2 V3 V4 V5 V6 V7

19、V87.3 图的遍历广度优先遍历(BFS)v从图中的某个顶点v0出发，访问此顶点，v依次访问v0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和v0有路径相通的顶点都被访问到。v若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止（遍历序列不唯一）V1 V3 V2 V7 V6 V5 V4 V8第37页，共70页，编辑于2022年，星期一V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8广度遍历：V1 V2 V3 V4 V5 V6 V7 V8广度遍历：V1 V2 V3 V4

20、V5 V6 V7 V8第38页，共70页，编辑于2022年，星期一V1V2V4V5V3V7V6V8例广度遍历：V1 V2 V3 V4 V6 V7 V8 V5第39页，共70页，编辑于2022年，星期一开始访问V0,置标志求V邻接点ww存在吗V下一邻接点ww访问过结束NYNYBFS初始化队列V0入队队列空吗队头V出队访问w,置标志w入队NaaYv广度优先遍历算法了解第40页，共70页，编辑于2022年，星期一int visitedM;void traver(TD g,int n)int i;for(i=1;i=n;i+)visitedi=0;for(i=1;iadjvex;if(visitedv

21、=0)visitedv=1;printf(%dn,v);qu+r=v;p=p-next;第41页，共70页，编辑于2022年，星期一例1423512341342vexdata firstarc 1 1 2 3adjvex next55 5 1 5 5 2 3 4 40 1 2 3 4 51fr遍历序列：10 1 2 3 4 52fr遍历序列：1 20 1 2 3 4 52 3fr遍历序列：1 2 3第42页，共70页，编辑于2022年，星期一例1423512341342vexdata firstarc 1 1 2 3adjvex next55 5 1 5 5 2 3 4 40 1 2 3 4

22、52 3 4fr遍历序列：1 2 3 40 1 2 3 4 5 3 4fr遍历序列：1 2 3 40 1 2 3 4 5 3 4 5fr遍历序列：1 2 3 4 5第43页，共70页，编辑于2022年，星期一0 1 2 3 4 5 4 5fr遍历序列：1 2 3 4 50 1 2 3 4 5 5fr遍历序列：1 2 3 4 50 1 2 3 4 5 fr遍历序列：1 2 3 4 5例1423512341342vexdata firstarc 1 1 2 3adjvex next55 5 1 5 5 2 3 4 4第44页，共70页，编辑于2022年，星期一7.4 生成树v生成树定义：所有顶点均

23、由边连接在一起，但不存在回路的图叫。即连通图的一个极小连通子图，含有图中全部顶点，但只有足以构成一棵树的n-1条边说明v一个图可以有许多棵不同的生成树v所有生成树具有以下共同特点：生成树的顶点个数与图的顶点个数相同一个有n个顶点的连通图的生成树有n-1条边生成树中任意两个顶点间的路径是唯一的在生成树中再加一条边必然形成回路v含n个顶点n-1条边的图不一定是生成树第45页，共70页，编辑于2022年，星期一7.4 生成树深度优先生成树与广度优先生成树生成森林：非连通图每个连通分量的生成树一起组成非连通图的第46页，共70页，编辑于2022年，星期一V1V2V4V5V3V7V6V8例深度遍历：V1

24、 V2 V4 V8 V5 V3 V6 V7V1V2V4V5V3V7V6V8深度优先生成树V1V2V4V5V3V7V6V8广度优先生成树V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8广度遍历：V1 V2 V3 V4 V5 V6 V7 V8第47页，共70页，编辑于2022年，星期一例ABLMCFDEGHKIJABLMCFJDEGHKI深度优先生成森林第48页，共70页，编辑于2022年，星期一7.4 生成树v最小生成树问题提出v要在n个城市间建立通信联络网，v顶点表示城市v权城市间建立通信线路所需花费代价v希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代

25、价）最小最小代价生成树1654327131791812752410第49页，共70页，编辑于2022年，星期一7.4 生成树v最小生成树问题分析vn个城市间，最多可设置n(n-1)/2条线路vn个城市间建立通信网，只需n-1条线路v问题转化为：如何在可能的线路中选择n-1条，能把所有城市（顶点）均连起来，且总耗费（各边权值之和）最小1654327131791812752410第50页，共70页，编辑于2022年，星期一7.5 有向无环图及其应用v重点研究内容：有向无环图的拓扑排序和关键路径v有向无环图：无环的有向图。v应用：描述工程和系统的进行过程v工程能否顺利进行v估算工程完成必须的最短时间

26、有向图中的有向图中的拓扑排序拓扑排序问题问题有向图的有向图的关键路径关键路径问题问题第51页，共70页，编辑于2022年，星期一7.5 拓扑排序v问题提出：学生选修课程问题顶点表示课程有向弧表示先决条件，若课程i是课程j的先决条件，则图中有弧学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业拓扑排序编号课程名称C1数学C2程序设计C3离散数学C4汇编程序设计C5数据结构C6结构程序设计C7编译原理C1C3C2C7C5C6C4第52页，共70页，编辑于2022年，星期一7.5 拓扑排序v定义AOV网用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网(Activity On

27、 Vertex network)，简称AOV网v若是图中有向边，则vi是vj的直接前驱；vj是vi的直接后继vAOV网中不允许有回路，若存在则意味着某项活动以自己为先决条件第53页，共70页，编辑于2022年，星期一7.5.1 拓扑排序-实现拓扑排序步骤：vStep1:在有向图中选一个无前驱的顶点输出之;vStep2:从有向图中删去此顶点及所有以它为尾的弧;vStep3:重复Step1,2到图中顶点全部输出，或图不空但找不到无前驱的顶点(有环)为止。v例：有向图G的弧表示课程进行先后关系，排一张课程先后次序表编号课程名称C1数学C2程序设计C3离散数学C4汇编程序设计C5数据结构C6结构程序设

28、计C7编译原理C1C3C2C7C5C6C4拓扑有序序列：C1=C3=C2=C4=C6=C5=C7第54页，共70页，编辑于2022年，星期一7.5.2 关键路径v问题提出把工程计划表示为有向图，用顶点表示事件，弧表示活动。例.设一个工程有11项活动，9个事件 事件 V1表示整个工程开始 事件 V9表示整个工程结束问题：（1）完成整项工程至少需要多少时间？（2）哪些活动是影响工程进度的关键？987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4第55页，共70页，编辑于2022年，星期一7.4 关键路径定义：vAOE网(Activity O

29、n Edge)也叫边表示活动的网。AOE网是一个带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间v路径长度路径上各活动持续时间之和v关键路径路径长度最长的路径叫987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4第56页，共70页，编辑于2022年，星期一6.4 关键路径vVe(j)表示事件Vj的最早发生时间vVl(j)表示事件Vj的最迟发生时间ve(i)表示活动ai的最早开始时间vl(i)表示活动ai的最迟开始时间vl(i)-e(i)表示完成活动ai的时间余量v关键活动关键路径上的活动叫，即l(i)=e(i)的活动9

30、87645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4第57页，共70页，编辑于2022年，星期一6.4 关键路径问题分析v如何找e(i)=l(i)的关键活动？设活动ai用弧表示，其持续时间记为：dut()。则有：（1）e(i)=Ve(j)（2）l(i)=Vl(k)-dut()jkaiv如何求Ve(j)和Vl(j)？(1)从Ve(1)=0开始向前递推(2)从Vl(n)=Ve(n)开始向后递推第58页，共70页，编辑于2022年，星期一求关键路径步骤v求Ve(i)v求Vl(j)v求e(i)v求l(i)v计算l(i)-e(i)987645321

31、a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4V1V2V3V4V5V6V7V8V9顶点 Ve Vl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活动 e l l-e00002266046258377077071031616014140033第59页，共70页，编辑于2022年，星期一邻接表结点：typedef struct node int vex;/顶点域 int length;struct node *next;/链域JD;表头结点：typedef struct tnode int vexda

32、ta;int in;/入度域 struct node *link;/链域TD;TD gM;/g0不用6.4 关键路径算法实现了解v以邻接表作存储结构v从源点V1出发，令Ve1=0,按拓扑序列求各顶点的Veiv从汇点Vn出发，令Vln=Ven,按逆拓扑序列求其余各顶点的Vliv根据各顶点的Ve和Vl值，计算每条弧的ei和li,找出ei=li的关键活动第60页，共70页，编辑于2022年，星期一987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=47.4 关键路径算法描述v输入顶点和弧信息，建立其邻接表v计算每个顶点的入度v对其进行拓扑排序排

33、序过程中求顶点的Vei将得到的拓扑序列进栈v按逆拓扑序列求顶点的Vliv计算每条弧的ei和li,找出ei=li的关键活动第61页，共70页，编辑于2022年，星期一987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4inlinkvexnextvexdatalength123456789123456789011121122 26 34 45 79 51 62 51 87 84 910 94第62页，共70页，编辑于2022年，星期一7.6 最短路径了解问题提出v用带权的有向图表示一个交通运输网，图中：v顶点表示城市；边表示城市间的交通联系

34、v权表示此线路的长度或沿此线路运输所花的时间或费用等v问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径最短路径从某个源点到其余各顶点的最短路径51643208562301371732913长度最短路径813192120第63页，共70页，编辑于2022年，星期一7.5 最短路径迪杰斯特拉(Dijkstra)算法思想v按路径长度递增次序产生最短路径算法：v把V分成两组：（1）S：已求出最短路径的顶点的集合（2）V-S=T：尚未确定最短路径的顶点集合v将T中顶点按最短路径递增的次序加入到S中，保证：（1）从源点V0到S中各顶点的最短路径长度都不大于从V0到T中任

35、何顶点的最短路径长度（2）每个顶点对应一个距离值 S中顶点：从V0到此顶点的最短路径长度 T中顶点：从V0到此顶点的只包括S中顶点作中间 顶点的最短路径长度依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和（反证法可证）第64页，共70页，编辑于2022年，星期一6.5 最短路径求最短路径步骤v初使时令 S=V0,T=其余顶点，T中顶点对应的距离值若存在，为弧上的权值若不存在，为v从T中选取一个其距离值为最小的顶点W，加入Sv对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值

36、v重复上述步骤，直到S中包含所有顶点，即S=V为止第65页，共70页，编辑于2022年，星期一1383032V2:813-133032V1:13-13302220V3:13-192220V4:19终点 从V0到各终点的最短路径及其长度V1V2V3V4V5V6Vj-2120V6:20516432085623013717329第66页，共70页，编辑于2022年，星期一6.5 最短路径算法实现v图用带权邻接矩阵存储ad v数组dist 存放当前找到的从源点V0到每个终点的最短路径长度，其初态为图中直接路径权值v数组pre 表示从V0到各终点的最短路径上，此顶点的前一顶点的序号；若从V0到某终点无路

37、径，则用0作为其前一顶点的序号第67页，共70页，编辑于2022年，星期一v算法描述627543185623013717329dist0 1 2 3 4 5 60 13 8 30 32pre0 1 2 3 4 5 60 1 1 0 1 0 1(1)k=1113312220221941215111长度最短路径13813192120v算法分析：T(n)=O(n)第68页，共70页，编辑于2022年，星期一6.5 最短路径每一对顶点之间的最短路径v方法一：每次以一个顶点为源点，重复执行Dijkstra算法n次 T(n)=O(n)v方法二：弗洛伊德(Floyd)算法算法思想：逐个顶点试探法求最短路径步

38、骤v初始时设置一个n阶方阵，令其对角线元素为0，若存在弧，则对应元素为权值；否则为v逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值v所有顶点试探完毕，算法结束第69页，共70页，编辑于2022年，星期一例ACB2643110 4 116 0 23 0初始：路径：AB ACBA BCCA0 4 66 0 23 7 0加入V2：路径：AB ABCBA BCCA CAB0 4 116 0 23 7 0加入V1：路径：AB ACBA BCCA CAB0 4 65 0 23 7 0加入V3：路径：AB ABCBCA BCCA CAB第70页，共70页，编辑于2022年，星期一