数据结构课件07

1、第七章第七章 图图精英专升本精英专升本V1V2V3V4G1V1V2V4V5G2V3ABECFAEFBBC1597211132C V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2例例:(b)、(c) 是是 (a) 的子图的子图(a) (b) (c) ACDFE例如例如: :ID(B) = 3ID(A) = 2BABECF对有向图来说对有向图来说，例如例如: :ID(B) = 2OD(B) = 1TD(B) = 3ABECF 非连通图非连通图 连通图连通图 强连通图强连通图 非强连通图非强连通图 V

2、0V0 V1V1 V2V2 V3V3 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3 V0V0 V2V2 V3V3 V1V1 V5V5 V4V4在无（在无（有有）向图）向图G=( V, E )G=( V, E )中，若对任何两个顶点中，若对任何两个顶点 v v、u u 都存在从都存在从v v 到到 u u 的路径，则称的路径，则称G G是连通图（是连通图（强连通图强连通图）。）。非连通图非连通图 V0V0 V2V2 V3V3 V1V1 V5V5 V4V4无向图无向图G G 的的称为称为G G的连通分量。的连通分量。极大连通子图意思是：该子图是极大连通子

3、图意思是：该子图是 G G 连通子图，将连通子图，将G G 的任何不在该子图中的顶点加入，子图不再连通。的任何不在该子图中的顶点加入，子图不再连通。 V0V0 V2V2 V3V3 V1V1 V5V5 V4V4连通分量连通分量有向图有向图G G 的的称为称为G G的强连通分量。极的强连通分量。极大强连通子图意思是：该子图是大强连通子图意思是：该子图是G G的强连通子图，将的强连通子图，将D D的任何不在该子图中的顶点加入，子图不再是强连的任何不在该子图中的顶点加入，子图不再是强连通的。通的。强连通分量强连通分量 V0V0 V1V1 V2V2 V3V3 V0V0 V2V2 V3V3 V1V1：该子

4、图是：该子图是G G 的连通子图，在该子图的连通子图，在该子图中删除任何一条边，子图不再连通。中删除任何一条边，子图不再连通。包含无向连通图包含无向连通图G G 所有顶点的极小连通子所有顶点的极小连通子图。图。对非连通图，由各个连通分量的生对非连通图，由各个连通分量的生成树的集合。成树的集合。 连通图连通图 G1G1G1G1的生成树的生成树 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V27.2 7.2 图的存储结构图的存储结构数组表示法（邻接矩阵）数组表示法（邻接矩阵）多重链表多重链表0 (i

5、,j)VR1 (i,j)VR一、一、图的数组(邻接矩阵)存储表示BACDFE定义定义:矩阵的元素为矩阵的元素为A B C D E FABCDEF有向图的邻接矩阵有向图的邻接矩阵为非对称矩阵为非对称矩阵ABECF0 1 0 0 10 0 1 0 00 0 0 1 01 1 0 0 00 0 1 0 0typedef struct ArcCell / 弧的定义弧的定义 VRType adj; / VRType是顶点关系类型。 / 对无权图，用1或0表示相邻否； / 对带权图，则为权值类型。 InfoType *info; / 该弧相关信息的指针 ArcCell, typedef struct /

6、图的定义图的定义 VertexType / 顶点信息 / 弧的信息 int vexnum, arcnum; / 顶点数，弧数 GraphKind kind; / 图的种类标志 MGraph; , ),( , , .AMGraph 否否则则或或者者如如果果01A ; EjiEjijiarcs邻接矩阵：G1.arcs =（ v1 v2 v3 v4 v5 ）v1v2v3v4v50 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0顶点表：无向图的邻接矩阵表示法无向图的邻接矩阵表示法v1v2v3v5v4v4有向图的邻接矩阵有向图的邻接矩阵可能是不对称可能是不对称的。

7、的。顶点的顶点的出度出度= =第第i i行元素之和行元素之和 顶点的顶点的入度入度= =第第i i列元素之和列元素之和 顶点的顶点的度度= =第第i i行元素之和行元素之和+ +第第i i列元素之和列元素之和 v1v2v3v4邻接矩阵：( v1 v2 v3 v4 )v1v2v3v4注：注：在有向图的邻接矩阵中，在有向图的邻接矩阵中， 第第i i行含义：以结点行含义：以结点v vi i为尾的弧为尾的弧( (即出度边）；即出度边）； 第第i i列含义：以结点列含义：以结点v vi i为头的弧为头的弧( (即入度边）。即入度边）。顶点表：0 1 1 00 0 0 0 0 0 0 1 1 0 0 0

8、有向图的邻接矩阵表示法有向图的邻接矩阵表示法定义为：定义为： N.arcs i j =Wij 或（或（vi, vj）VR 无边（弧）无边（弧）N5489755613邻接矩阵：N.arcs =( v1 v2 v3 v4 v5 v6 )顶点表： 5 7 4 8 9 5 6 5 3 1 网（即有权图）的邻接矩阵表示法网（即有权图）的邻接矩阵表示法优点：优点：容易实现图的操作，如：求某顶点的度、判断顶容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边、找顶点的邻接点等等。点之间是否有边、找顶点的邻接点等等。缺点：缺点：n n个顶点需要个顶点需要n n* *n n个单元存储边个单元存储边; ;空间

9、效率为空间效率为O(nO(n2 2) )。 对稀疏图而言尤其浪费空间。对稀疏图而言尤其浪费空间。邻接矩阵表示法的特点邻接矩阵表示法的特点0 A1 B2 C3 D4 E5 FBACDFE二、图的邻接表二、图的邻接表 存储表示存储表示1 40 4 53 52 50 11 2 3v 以每个顶点以每个顶点vi 作为头结点，建立一个作为头结点，建立一个，把与，把与vi有关联的有关联的起来起来设两个域，表中每个设两个域，表中每个设为设为3个域；个域；邻接点域邻接点域，表表示示vi一个邻接一个邻接点的位置点的位置链域链域，指向指向vi下一个边下一个边或弧的结点或弧的结点数据域数据域，与与边有关信息边有关信息

10、（如权值）（如权值）数据域数据域，存存储顶点储顶点vi 信信息息链域链域，指向，指向单链表的第单链表的第一个结点一个结点adjvexnextarcinfodatafirstarc邻接表（链式）表示法邻接表（链式）表示法0123413341420注：注：邻接表不唯一邻接表不唯一，因各个边结点的链入顺序是任意的，因各个边结点的链入顺序是任意的v1v2v3v4v5231420无向图的邻接表表示无向图的邻接表表示TD(ViTD(Vi)=)=单链表中链接的结点个数单链表中链接的结点个数v1v2v3v5v4v4有向图的邻接表有向图的邻接表1 4230 120 1 2 3 4 A B C D EABECD可

11、见，在有向图的邻接表中不易找到指向该顶点的弧。出度出度入度入度度：度：OD(ViOD(Vi) )单链出边表中链接的结点数单链出边表中链接的结点数ID(ViID(Vi) )邻接点域为邻接点域为ViVi的弧个数的弧个数TD(Vi) = OD( Vi ) + I D( Vi )ABECD有向图的逆邻接表有向图的逆邻接表A B C D E 303420 01234在有向图的逆邻接表中，对每个顶点，链接的是指向该顶点的弧。8064125当邻接表的存当邻接表的存储结构形成后，储结构形成后，图便唯一确定！图便唯一确定！已知某网的邻接（出边）表，请画出该网络。已知某网的邻接（出边）表，请画出该网络。typed

12、ef struct ArcNode int adjvex; / 该弧所指向的顶点的位置 struct ArcNode *nextarc; / 指向下一条弧的指针 InfoType *info; / 该弧相关信息的指针 ArcNode;adjvex nextarc info弧的结点结构弧的结点结构typedef struct VNode VertexType data; / 顶点信息 ArcNode *firstarc; / 指向第一条依附该顶点的弧 VNode, AdjListMAX_VERTEX_NUM; data firstarc顶点顶点的头结点的头结点结构结构typedef struct

13、 AdjList vertices; int vexnum, arcnum; int kind; / 图的种类标志 ALGraph;图的结构定义图的结构定义v1v2v3v5v4v44321013341420v5v4v3v2v1231420（ v1 v2 v3 v4 v5 ）v1v2v3v4v50 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 00 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0邻接矩阵与邻接表表示法的关系邻接矩阵

14、与邻接表表示法的关系1. 1. 联系：联系：邻接表中每个链表对应于邻接矩阵中的一行，邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。链表中结点个数等于一行中非零元素的个数。2. 2. 区别：区别： 对于任一确定的无向图，邻接矩阵是对于任一确定的无向图，邻接矩阵是唯一唯一的（行列的（行列号与顶点编号一致），但邻接表号与顶点编号一致），但邻接表不唯一不唯一（链接次序（链接次序与顶点编号无关）。与顶点编号无关）。 邻接矩阵的空间复杂度为邻接矩阵的空间复杂度为O(nO(n2 2),),而邻接表的空间复而邻接表的空间复杂度为杂度为O(n+eO(n+e) )。3. 3. 用

15、途：用途：邻接矩阵多用于邻接矩阵多用于稠密图稠密图；而邻接表多用于；而邻接表多用于稀稀疏图疏图邻接矩阵与邻接表表示法的关系邻接矩阵与邻接表表示法的关系7.3 图的遍历图的遍历 从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的的过程。深度优先搜索深度优先搜索广度优先搜索广度优先搜索遍历应用举例遍历应用举例 从图中某个顶点V0 出发，访问此顶点，然后，直至图中所有和V0有路径相通的顶点都被访问到。一、深度优先搜索一、深度优先搜索遍历图（遍历图（DFS）连通图的深度优先搜索遍历连通图的深度优先搜索遍历Vw1SG1SG2SG3W1、W2和W3 均为 V 的邻接点，SG1、SG2 和 SG3 分

16、别为含顶点W1、W2和W3 的子图。w2w3w2基本思想：基本思想：仿树的先序遍历过程。仿树的先序遍历过程。v1v2v3v8v7v6v4v5起点起点深度优先搜索深度优先搜索( DFS Depth_First Search)解决思路：解决思路：设置设置辅助数组辅助数组 visitedvisited n n ，用来标记每，用来标记每个被访问过的顶点。个被访问过的顶点。初始状态为初始状态为0 0i i 被访问，改被访问，改 visitedvisited i i 为为1 1，防止被多次访问，防止被多次访问怎样避免重复访问？怎样避免重复访问？void DFS(Graph G, int v) / 从顶点从

17、顶点v出发，出发，深度优先搜索遍历连通图深度优先搜索遍历连通图 G /算法调用前，设每个结点的算法调用前，设每个结点的visitedv=FALSE visitedv = TRUE; VisitFunc(v); for( ; ; ) if (!visitedw) DFS(G, w); / 对v的尚未访问的邻接顶点w / 递归调用DFS / DFS连通图连通图的深度优先搜索的深度优先搜索遍历算法（遍历算法（P169算法算法7.5） 首先将图中每个顶点的访问标志设为 FALSE, 之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。非连通图的深度优先搜

18、索遍历非连通图的深度优先搜索遍历void DFSTraverse(Graph G, Status (*Visit)(int v) / 对图对图 G 作深度优先遍历。作深度优先遍历。 VisitFunc = Visit; for (v=0; vG.vexnum; +v) visitedv = FALSE; / 访问标志数组初始化 for (v=0; vw1, V-w2, V-w8 的路径长度为1；V-w7, V-w3, V-w5 的路径长度为2；V-w6, V-w4 的路径长度为3。w1Vw2w7w6w3w8w5w4基本思想：基本思想：仿树的层次遍历过程仿树的层次遍历过程广度优先搜索广度优先搜索

19、( BFS Breadth_First Search)v1v2v3v8v7v6v4v5起点起点简单归纳：简单归纳：在访问了在访问了起始点起始点v之后，依次访问之后，依次访问 v的邻接点的邻接点；之后按这些顶点被访问的先后次序，依次访问它们按这些顶点被访问的先后次序，依次访问它们的的未被访问过的邻接点未被访问过的邻接点；直到所有顶点都被访问直到所有顶点都被访问过为止。过为止。广度优先搜索的步骤广度优先搜索的步骤v1v2v3v8v7v6v4v5起点起点V9 void BFSTraverse(Graph G, Status (*Visit)(int v) for (v=0; vG.vexnum; +

20、v) visitedv = FALSE; /初始化访问标志 InitQueue(Q); / 置空的辅助队列Q for ( v=0; vG.vexnum; +v ) if ( !visitedv) / v 尚未访问 / BFSTraverse visitedv = TRUE; Visit(v); / 访问uEnQueue(Q, v); / v入队列while (!QueueEmpty(Q) DeQueue(Q, u); / 队头元素出队并置为u for(w=FirstAdjVex(G, u); w!=0; w=NextAdjVex(G,u,w) if ( ! visitedw) visitedw

21、=TRUE; Visit(w); EnQueue(Q, w); / 访问的顶点w入队列 / if / while真题：已知一有向图的邻接表存储结构如下图所示，分别根据图的深度和广度优先搜索遍历算法，从顶点v1出发，得到的顶点序列分别为（ ）和（ ）。A、v1,v2,v3,v4,v5 B、v1,v3,v2,v4,v5 C、v1,v3,v4,v5,v2 D、v1,v4,v3,v5,v2最小生成树最小生成树最短路径最短路径拓扑排序拓扑排序关键路径关键路径图的应用（图的应用（ 7.4 ，7.5，7.6）：该子图是该子图是G 的连通子图，在该子图中删除的连通子图，在该子图中删除任何一条边，子图不再连通。

22、任何一条边，子图不再连通。包含图包含图G所有顶点的极小连通子图（所有顶点的极小连通子图（n-1条边）条边）G1G1的生成树的生成树连通图连通图 G1G1 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2最小生成树最小生成树DFSDFS生生成成树树邻邻接接表表0123413341420v4v3v2v1v0231420v0v2v1v4v3BFSBFS生生成成树树v0v1v3v2v4无向连通图无向连通图画出下图的生成树画出下图的生成树v0v1v2v4v4v3求最小生成树求最小生成树首先明确首先明确：

23、使用不同的遍历图的方法，可以得到不同的生成树使用不同的遍历图的方法，可以得到不同的生成树 从不同的顶点出发，也可能得到不同的生成树。从不同的顶点出发，也可能得到不同的生成树。 按照生成树的定义，按照生成树的定义，n n 个顶点的个顶点的连通网络连通网络的生成树的生成树有有 n n 个顶点、个顶点、n-n-1 1 条边。条边。目标：目标：在在的多个生成树中，寻找一个的多个生成树中，寻找一个v必须考虑到该必须考虑到该网中的边的权网中的边的权来构造最小生成树；来构造最小生成树；v必须使用且仅使用必须使用且仅使用n-1n-1条边条边来联结网络中的来联结网络中的n n个个顶点顶点v不能使用产生不能使用产

24、生回路回路的边的边构造最小生成树的准则构造最小生成树的准则最小生成树即：在 e 条带权的边中选取 n-1 条边（不构成回路），使“权值之和权值之和”为最小。欲在欲在n n个城市间建立通信网，则个城市间建立通信网，则n n个城市应铺个城市应铺n-1n-1条条线路；但因为每条线路都会有对应的经济成本，而线路；但因为每条线路都会有对应的经济成本，而n n个个城市可能有城市可能有n(n-1)/2 n(n-1)/2 条线路，那么，条线路，那么，如何选择如何选择n n1 1条条线路，使总费用最少？线路，使总费用最少？数学模型：数学模型：顶点顶点表示城市，有表示城市，有n n个；个；边边表示线路，有表示线路

25、，有n n1 1条；条；边的权值边的权值表示线路的经济代价；表示线路的经济代价；连通网连通网表示表示n n个城市间通信网。个城市间通信网。显然此连通网显然此连通网是一个是一个生成树生成树！最小生成树的典型用途最小生成树的典型用途v PrimPrim（普里姆）算法（普里姆）算法 v KruskalKruskal（克鲁斯卡尔）算法（克鲁斯卡尔）算法PrimePrime算法算法: : 归并顶点归并顶点，与边数无关，适于，与边数无关，适于稠密网稠密网Kruskal算法：算法：归并边归并边，适于，适于稀疏网稀疏网如何求最小生成树如何求最小生成树 设连通网络设连通网络 N = V, E 生成树的顶点集生成

26、树的顶点集合合UU普里姆算法的基本思想归并顶点普里姆算法的基本思想归并顶点应用普里姆算法构造最小生成树的过程应用普里姆算法构造最小生成树的过程 在生成树的构造过程中，图中 n 个顶点分属两个集合：已落在生成树上的顶点集 U 和尚未落在生成树上的顶点集V-U ，则应在所有连通在所有连通U中顶点和中顶点和V-U中中顶点的边中选取权值最小的边顶点的边中选取权值最小的边。 一般情况下所添加的顶点应满足下列条件: 设置一个辅助数组，对当前设置一个辅助数组，对当前集集中的每个顶点，记录和顶点集中的每个顶点，记录和顶点集U中顶点中顶点相连接的相连接的：struct VertexType adjvex; /

27、U集中的顶点序号 VRType lowcost; / 边的权值 MAX_VERTEX_NUM;abcdegf195141827168213ae12dcb7closedge0123456AdjvexLowcostaaa19141814例如例如:e12ee8168d3dd7213c5 5a b c d e f g16g21fvoid MiniSpanTree_P(MGraph G, VertexType u) /用普里姆算法从顶点u出发构造网G的最小生成树 k = LocateVex ( G, u ); for ( j=0; jG.vexnum; +j ) / 辅助数组初始化 if (j!=k)

28、closedgej = u, G.arcskj.adj ; closedgek.lowcost = 0; / 初始，Uu for (i=0; iG.vexnum; +i) 继续向生成树上添加顶点继续向生成树上添加顶点; k = minimum(closedge); / 求出加入生成树的下一个顶点(k) printf(closedgek.adjvex, G.vexsk); / 输出生成树上一条边 closedgek.lowcost = 0; / 第k顶点并入U集 for (j=0; jG.vexnum; +j) /修改其它顶点的最小边 if (G.arcskj.adj closedgej.low

29、cost) closedgej = G.vexsk, G.arcskj.adj ; 设连通网络设连通网络 N = V, E 1. 构造一个只有构造一个只有 n 个顶点，没有边的非连通图个顶点，没有边的非连通图 T = V, , 每个顶点自成一个连通分量每个顶点自成一个连通分量 2. 在在 E 中选最小权值的边中选最小权值的边,若该边的两个顶点落在若该边的两个顶点落在不同的连通分量上，则加入不同的连通分量上，则加入 T 中；否则舍去，重中；否则舍去，重新选择新选择 3. 重复下去，直到所有顶点在同一连通分量上为重复下去，直到所有顶点在同一连通分量上为止止克鲁斯卡尔算法的基本思想归并边克鲁斯卡尔算

30、法的基本思想归并边应用克鲁斯卡尔算法构造最小生成树的过程应用克鲁斯卡尔算法构造最小生成树的过程普里姆算法普里姆算法 克鲁斯卡尔算法克鲁斯卡尔算法时间复杂度时间复杂度O(n2)O(eloge)稠密图稠密图稀疏图稀疏图算法名算法名适应范围适应范围比较两种算法如果用有向图来描述一个工程或系统的进行过程，则图中不允许出现回路。有向无环图简称图。比如教学计划的制定比如教学计划的制定哪些课程是必须先修的，哪些课程是可以并行学习的。哪些课程是必须先修的，哪些课程是可以并行学习的。7.5 有向无环图及其应用有向无环图及其应用如：用有向图表示一个工程的施工图或程序的数据流图学生课程学习工程图学生课程学习工程图对

31、有向图进行如下操作： 按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。由此所得顶点的线性序列称之为7.5.1 拓扑排序拓扑排序例如：对于下列有向图BDAC可求得拓扑有序序列： A B C D 或 A C B DBDAC反之，对于下列有向图不能求得它的拓扑有序序列。因为图中存在一个回路 B, C, D1.输入输入AOV网络。令网络。令 n 为顶点个数。为顶点个数。2. 在在AOV网络中网络中选一个没有直接前驱的顶点选一个没有直接前驱的顶点, 并输出之并输出之; 3. 从图中删去该顶点从图中删去该顶点, 同时删去所有它发出的有

32、向边同时删去所有它发出的有向边;4. 重复以上重复以上 2、3 步步, 直到：直到：u全部顶点均已输出，拓扑有序序列形成，拓扑排序全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或：完成；或：u图中还有未输出的顶点，但已跳出处理循环。图中还有未输出的顶点，但已跳出处理循环。，再也，再也找不到没有前驱的顶点了。这时找不到没有前驱的顶点了。这时。拓扑排序的过程拓扑排序的过程a3=6a5=47.5.2 关键路径关键路径AOE网用边表示活动，顶点表示事件，弧上的权值表示完成该项活动所需时间整个工程只有一个开始点和一个结束点。源点汇点abcdefghk64521187244例如例如: :整个工程完成的

33、时间为：从有向图的源点源点到汇点汇点的最长路径。6174a1a2a3a4a5a6a7a8a9a10a11 假设第 i 条活动ai（弧）为 ， 定义“活动ai (弧)”的 最早开工时间 定义“活动ai (弧)”的 最迟开始时间 abcdefghk64521187244a1a2a3a4a5a6a7a8a9a10a11整个活动的完成时间整个活动的完成时间18“事件事件(顶点顶点)” 的 最早发生时间 设活动设活动ai用弧用弧表示，其持续时间记为：表示，其持续时间记为：dut()则有：则有：（1）ee(i)=Ve(j)（2）el(i)=Vl(k)-dut()jkai987645321a2=4a3=5a

34、5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4(1)从从Ve(1)=0开始向前递推开始向前递推为头的弧的集合是所有以其中2,),()()(jTnjTjijidutiVeMaxjVeiabcdefghk64521187244a1a2a3a4a5a6a7a8a9a10a11Ve(b)=6; Ve(c)=4; Ve(e)=7; (2)从从Vl(n)=Ve(n)开始向后递推开始向后递推为尾的弧的集合是所有以其中iSniSjijidutjVlMiniVlj11 ,),()()(abcdefghk64521187244a1a2a3a4a5a6a7a8a9a10a11Vl(g)=

35、16; Vl(h)=14; Vl(e)=7;Vl(b)=6整个活动的完成时间整个活动的完成时间18Vl(k)=Ve(k)=18abcdefghk64521187244a b c d efg h kvevl0000000006457115 715 14 1818181818181818181816 1486610807（1）列出所有的）列出所有的关键路径关键路径；（2）完成整个工程）完成整个工程至少至少需要多少时间？需要多少时间？（3）事件）事件V5 的最早的最早完成完成时间是多少？时间是多少？（4）活动）活动 a6 的的最早最早开工时间是多少？开工时间是多少？练习：对于下面的练习：对于下面的A

36、OEAOE网络，试回答下列问题：网络，试回答下列问题：典型用途：典型用途：交通问题。如：城市交通问题。如：城市A A到城市到城市B B有多条线路，有多条线路，但每条线路的交通费（或所需时间）不同，那么，但每条线路的交通费（或所需时间）不同，那么，如如何选择一条线路，使总费用（或总时间）最少？何选择一条线路，使总费用（或总时间）最少？问题抽象：问题抽象：在在带权有向图带权有向图中中A A点（源点）到达点（源点）到达B B点（终点（终点）的多条路径中，寻找一条点）的多条路径中，寻找一条各边权值之和最小各边权值之和最小的路的路径，即最短路径。径，即最短路径。（注：最短路径与最小生成树不同，路径上（注

37、：最短路径与最小生成树不同，路径上不一定包含不一定包含n n个顶点）个顶点）7.6 7.6 最短路径最短路径一顶点到一顶点到其余各顶其余各顶点点两种常见的最短路径问题：两种常见的最短路径问题：一、一、 单源最短路径单源最短路径用用Dijkstra（迪杰斯特拉）（迪杰斯特拉）算法算法二、所有顶点间的最短路径二、所有顶点间的最短路径用用Floyd（弗洛伊德）（弗洛伊德）算法算法任意两顶任意两顶点之间点之间目的：目的： 设一设一有向图有向图G=G=（V, EV, E），已知各边的权值，以某指定），已知各边的权值，以某指定点点v v0 0为源点，求从为源点，求从v v0 0到图的其余各点的最短路径。到

38、图的其余各点的最短路径。限定各边上限定各边上的权值大于或等于的权值大于或等于0 0。源点源点从从FAFA的路径有的路径有4 4条：条： FAFA： 2424 FBA FBA： 5 518=2318=23 FBCA FBCA：5+7+9=215+7+9=21 FDCAFDCA：25+12+9=3625+12+9=36又：又：从从FBFB的最短路径是哪条？的最短路径是哪条？从从FCFC的最短路径是哪条？的最短路径是哪条？单源最短路径问题（单源最短路径问题（Dijkstra算法）算法） 依依路径路径的长度的长度递增的次序求得递增的次序求得各节点的最短路径各节点的最短路径V0v1v2V34263213基本思想（基本思想（Dijkstra算法）算法）V0v1v2V34263213基本思想（基本思想（Dijkstra算法）算法） 依依路径路径的长度的长度递增的次序求得递增的次序求得各节点的最短路径各节