算法与数据结构（C++语言版）（第2版） 课件 第9章-图的应用

DataStructureandAlgorithmdesign|analyze|experiment|implement数据结构与算法第九章图的应用9.1最小生成树9.1.1最小生成树的概念9.1.2Prim算法9.1.3Kruskal算法9.2有向无环图及其应用9.3最短路径*9.4算法拓展*9.5你怎么看？目录CONTENTS最小生成树的概念连通图最小生成树MST的性质最小生成树的构造算法Prim算法Kruskal算法最小生成树最小生成树（MinimumSpanningTree）：在加权连通图（连通网）的所有生成树中，各边权值之和最小的生成树，称为最小生成树。要注意：(1)该定义是在无向连通图的基础上的；(2)最小生成树可能不唯一，但是其权值之和是唯一的;(3)对于n个结点的图，其生成树中必定有n-1条边最小生成树的概念应用举例上图代表6个城市间的交通网，边上的权表示公路的造价现在要用公路把6个城市连接起来（这至少要修5条公路）如何设计使得这5条公路的总造价最少呢？最小生成树的概念(a)(a)的MST(a)的MST最小生成树的概念若图中有较小相等权值，最小生成树可能不唯一，但是最小生成树上权值之和是相等的。MST性质：假设G=（V，E）是一个加权连通图，U是顶点集V的一个非空子集。若（u，v）是一条具有最小权值的边，其中u∈U，v∈V－U，则必存在一棵包含边（u，v）的最小生成树。最小生成树的概念MST性质可以用反证法证明如下：假设图G的任何一棵最小生成树都不包含边（u，v），显然当把边（u，v）加入到G的一棵最小生成树T中时，由生成树的定义，将产生一个含有边（u，v）的回路最小生成树的概念由于T是生成树，T中必存在不同于边（u，v）的另一条边（u’，v’），使得u’∈U，v’∈V-U，且u和u’之间，v和v’之间均有路径相连通将边（u’，v’）删除，就消除了上述回路，并得到了另一棵生成树T’。由于W(u，v)≤W(u’，v’)，所以生成树T’的耗费不大于树T的耗费。于是T’是一棵包含边(u，v)的最小生成树，与假设矛盾

最小生成树边集的存储表示为了存储一棵最小生成树的边集，在图的抽象数据类型graph中定义了最小生成树的边结点类型mstEdge，该类型包含三个域：vex1为一条带权边上关联的一个顶点的编号；vex2为该边上关联的另一个顶点的编号；weight为边上的权值。mstEdge类型定义structmstEdge{ //最小生成树的边结点类型intvex1,vex2; EdgeTypeweight; //边的三元组(始点，终点，权值)booloperator<(constmstEdge&e)const{ //使用优先级队列需重载<returnweight<e.weight;}};9.1最小生成树9.1.1最小生成树的概念9.1.2Prim算法9.1.3Kruskal算法9.2有向无环图及其应用9.3最短路径*9.4算法拓展*9.5你怎么看？目录CONTENTSPrim算法设G=（V，E）是一个连通的带权图，其中V是顶点的集合，E是边的集合，TE为最小生成树的边的集合。则Prim算法通过以下步骤得到最小生成树：(1)最小生成树T的初始状态为U={u0}(u0V)，TE={}，此时图中只有一个起始顶点，边集为空。(2)在所有u∈U，v∈V－U的边中找一条代价最小的边(u，v)；把边(u，v)并入生成树的边集TE，同时v并入生成树的顶点集U；(3)重复执行步骤2，直至U=V为止。此时，TE中必有n-1条边，T=(U，TE)为G的最小生成树。算法结束时，TE中包含了G中的n-1条边。经过上述步骤选取到的所有边恰好就构成了图G的一棵最小生成树Prim算法构造一棵最小生成树的过程从U={A}，TE={}开始，当存在多条从U中顶点到V－U中同一顶点的边时，只列举权值小者Prim算法构造一棵最小生成树的过程Prim算法构造一棵最小生成树的过程作答Prim算法逐渐增加当前最小边相关联的顶点到U集合中v0v4v1v3v5v6v211541062V0V4V5V6V2V1V3}U:{请手工模拟左图用Prim算法求解最小生成树的过程主观题10分算法的关键是如何找到连接顶点集U和顶点集V-U的最小代价边。为实现这一目的，除了需要访问标志数组visited，用以区分顶点是否已经被访问过，还需要设置一个辅助数组D，用以记录从U到V－U具有最小代价的边。对于每个vi∈V－U，在辅助数组D中存在一个分量D[i]与之对应，它包括两个域：lowCost为U中的顶点到顶点vi的边上的最小权值；adjVex表示U集合中编号为adjVex的顶点与编号为i的顶点（即vi）之间的边上的权值是lowCost。Prim算法Prim算法--基于邻接表template<classVertexType,classEdgeType>voidadjList<VertexType,EdgeType>::prim(EdgeTypenoEdge)const{

structDist{intadjVex; //最小代价边依附的顶点编号EdgeTypelowCost; //最小代价}*D=newDist[verNum];edgeNode*p;EdgeTypeminCost;intu,i,j,count=0;for(i=0;i<verNum;++i){visited[i]=false;D[i].lowCost=noEdge;}u=0;visited[u]=true; //初始化U集合for(i=1;i<verNum;++i){ //选中一个点u入U集合后for(p=verList[u].firstEdge;p!=NULL;p=p->next) //更新u关联的顶点的D值if(!visited[p->to]&&D[p->to].lowCost>p->weight){D[p->to].lowCost=p->weight; //更新lowcostD[p->to].adjVex=u; //更新adjVex}minCost=noEdge;for(j=0;j<verNum;++j) //在V-U中找lowCost最小顶点uif(D[j].lowCost<minCost){minCost=D[j].lowCost;u=j;}TE[count].vex1=D[u].adjVex; //保存最小生成树的一条边TE[count].vex2=u;TE[count++].weight=D[u].lowCost;D[u].lowCost=noEdge; //顶点u已并入U集合visited[u]=true; }delete[]D;}Prim算法--基于邻接表时间性能Prim算法是一种基于顶点的贪心算法，从起始顶点出发，每次迭代选择当前可用的最小权值边，然后把边上依附的其他顶点加入到最小生成树。Prim算法可以称为“加点法”，比较适合稠密图。本算法通过直接比较D数组元素，确定代价最小的边就需要总时间O(n2)；取出权最小的顶点后，修改D数组共需要时间O(e)，因此共需要花费O(n2)的时间。作答使用Prim(普里姆)算法求带权连通图的最小(代价)生成树(MST)。请回答下列问题(1)对下图G，从顶点A开始求G的MST，依次给出按算法选出的边。

(2)图G的MST是唯一的吗?(3)对任意的带权连通图，满足什么条件时，其MST是唯一的?【2017年全国统考408（8分）】【参考答案】(1)依次选出的边为：(A，D)，(D，E)，(E，C)，(C，B)。(2)图G的MST是唯一的。(3)当带权连通图的任意一个环中所包含的边的权值均不相同时，其MST是唯一的。主观题10分9.1最小生成树9.1.1最小生成树的概念9.1.2Prim算法9.1.3Kruskal算法9.2有向无环图及其应用9.3最短路径*9.4算法拓展*9.5你怎么看？目录CONTENTSKruskal算法Kruskal算法：使用的贪心准则，从剩下的边中选择具有最小权值且不会产生环路的边加入到生成树的边集中。Kruskal算法Kruskal算法的构造思想是：首先将G中的n个顶点看成是独立的n个连通分量，这时的状态是有n个顶点而无边的森林，可以记为T=<V，{}>。然后在E中选择代价最小的边，如果该边依附于两个不同的连通分支，那么将这条边加入到T中，否则舍去这条边而选择下一条代价最小的边。依此类推，直到T中所有顶点都在同一个连通分量中为止，此时就得到图G的一棵最小生成树。Kruskal算法构造一棵最小生成树的过程作答请手工模拟左图用Kruskal算法求解最小生成树的过程提示：已知n个独立的顶点，逐渐给n个顶点添加n-1条边，使之成为连通图，所添加的边不能使图中出现环v0v4v1v3v5v6v211541062主观题10分Kruskal算法算法的关键是如何找到最小代价边？可以将图中所有边按照权值存入一个最小优先级队列中，权值越小的边，其优先级越高，将会优先出队列如何判断该边的加入会不会形成环？可以将各连通分量上的顶点作为并查集的一个子集，对最小代价边的两个顶点分别执行find()查找操作，如果返回值相同，则表示两个顶点属于同一连通分量，加入这条边会形成环，否则将这条边加入TE，添加边之后还要执行merge()合并操作，合并两个顶点所属的连通分量。Kruskal算法--基于邻接表template<classVertexType,classEdgeType>voidadjList<VertexType,EdgeType>::kruskal()const{ intcount=0;mstEdgee;edgeNode*p;unionFindSetS(verNum); //并查集SpriorityQueue<mstEdge>Q; //优先级队列Qfor(inti=0;i<verNum;++i){ //边入优先级队列for(p=verList[i].firstEdge;p!=NULL;p=p->next)if(i<p->to){ //防止重复入队e.vex1=i;e.vex2=p->to;e.weight=p->weight;Q.enQueue(e); //边e入队}}while(count<verNum-1){ //选出verNum-1条边e=Q.deQueue(); //从优先级队列出队一条边intu=S.find(e.vex1); //查找顶点vex1所属子集intv=S.find(e.vex2); //查找顶点vex2所属子集if(u!=v){ //边上的两个顶点不属于同一连通分量S.merge(u,v); //合并u、v所属子集（连通分量）TE[count++]=e; //保存最小生成树上的一条边}}}Kruskal算法--基于邻接表Kruskal算法基于邻接表的Kruskal算法的时间复杂度为O(eloge)。这个算法的时间复杂度主要取决于边数，因此Kruskal算法适合于构造稀疏图的最小生成树。比较：Prim算法时间复杂度为O(n2),适用于稠密图。Kruskal算法时间复杂度为O(eloge),适用于稀疏图。作答V2V3V1V4V58112102549已知带权图的邻接矩阵，试画出从顶点v1开始利用Prim算法得到的最小生成树

主观题10分作答12354614254832345671235461425483234567利用Kruskal算法求最小生成树主观题10分下列关于最小生成树的叙述中，正确的是

Ⅰ最小生成树的代价唯一

Ⅱ所有权值最小的边一定会出现在所有的最小生成树中

Ⅲ使用普里姆（Prim）算法从不同顶点开始得到的最小生成树一定相同

Ⅳ使用普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树总不相同【2012年全国统考408】仅Ⅰ仅Ⅱ仅Ⅰ、Ⅲ仅Ⅱ、ⅣABCD提交单选题1分求下面带权图的最小（代价）生成树时，可能是克鲁斯卡（kruskal）算法第二次选中但不是普里姆（Prim）算法（从V4开始）第2次选中的边是（）。【2013年全国统考408】(V1,V3) (V1,V4)(V2,V3)(V3,V4)ABCD提交单选题1分已知无向图G如下所示，使用克鲁斯卡尔（Kruskal）算法求图G的最小生成树，加到最小生成树中的边依次是（）。【2020年全国统考408】(b,f),(b,d),(a,e),(c,e),(b,e)(b,f),(b,d),(b,e),(a,e),(c,e)(a,e),(b,e),(c,e),(b,d),(b,f)(a,e),(c,e),(b,e),(b,f),(b,d)ABCD提交单选题1分9.1最小生成树9.2有向无环图及其应用9.2.1拓扑排序*9.2.2关键路径9.3最短路径*9.4算法拓展*9.5你怎么看？目录CONTENTS拓扑排序拓扑排序是对有向无环图的顶点的一种排序。概念：(1)AOV网络：在有向图中，用顶点表示活动或任务，弧表示活动或任务间的优先关系，则此有向图称为用顶点表示活动的网络（ActivityOnVertex，简称AOV网络）。通常，这样的有向图可用来表示工程施工图，生产产品的流程图或数据流图等。(2)拓扑序列（TopologicalOrder）：在有向无环图中，若存在顶点vi到顶点vj的路径，那么在序列中顶点vi就排在顶点vj的前面，称此序列为拓扑序列。(3)拓扑排序（TopologicalSort）：将有向无环图的顶点按照它们之间的优先关系排成一个拓扑序列的操作称为拓扑排序。拓扑排序拓扑排序可以解决先决条件问题，即以某种线性顺序来组织多项任务，使任务顺序完成。拓扑序列(topologicalorder)应满足：如果有向无环图G中存在顶点vi到vj的一条路径，那么在序列中顶点vi必在顶点vj之前。拓扑排序拓扑排序的步骤如下：(1)在有向图中任选一个入度为0的顶点（即没有前驱的顶点）并输出它；(2)删除该顶点以及该顶点的所有出边，将其邻接点的入度减1；重复上述步骤，最后结果可能有两种情况：(1)当输出了有向图的全部顶点时，拓扑排序成功，得到该图的拓扑序列；(2)当图中还有顶点没有输出时，拓扑排序失败，说明该图中含有环，剩余顶点的入度均不为0。拓扑排序如何计算和存储顶点的入度？设置了一个整型数组inDegree，数组元素表示的各顶点的入度，随图中边数的减少而减少。从逻辑上删除某顶点以及该顶点的所有出边的操作，可通过对该顶点的后继（邻接点）的入度减1来实现。此外，为了便于查找入度为0的顶点，另设一个存储空间暂存入度为0的顶点（一般用栈或队列实现，区别是排序结果可能不同）拓扑排序拓扑排序算法描述如下：(1)计算每个顶点的入度，存入inDegree数组，遍历inDegree数组并将所有入度为0的顶点入队列。(2)若队列非空，从队首出队一个入度为0的顶点并输出它，将以该顶点为尾的所有邻接点的入度减1，若此时某个邻接点的入度为0，便将其入队；(3)重复执行步骤2，直到队列为空为止；此时，若所有顶点均已输出，拓扑排序成功，返回true；否则，还有顶点未输出表示图中有环，拓扑排序失败，返回false。拓扑排序根据前述算法求图9.7有向图的拓扑序列拓扑序列为：V1，V2，V3，V4，V5，V7，V6，V8，V9拓扑排序*拓扑排序过程*拓扑排序过程*拓扑排序过程*拓扑排序过程*拓扑排序过程拓扑排序—基于邻接表template<classVertexType,classEdgeType>booladjList<VertexType,EdgeType>::topSort()const{queue<int>q;edgeNode*p;inti,curNode,count=0,*inDegree=newint[verNum];for(i=0;i<verNum;i++)inDegree[i]=0;for(i=0;i<verNum;i++){ //遍历边表，求顶点入度for(p=verList[i].firstEdge;p!=NULL;p=p->next)++inDegree[p->to];}for(i=0;i<verNum;i++) //入度为0的顶点入队列if(inDegree[i]==0)q.push(i);while(!q.empty()){curNode=q.front();q.pop();//出队一个入度为0的顶点cout<<verList[curNode].vertex<<''; //输出//topOrder[count]=curNode; //保存拓扑序列用于求关键路径count++; //计数器+1for(p=verList[curNode].firstEdge;p!=NULL;p=p->next)

if(--inDegree[p->to]==0) //邻接点入度减1q.push(p->to); //入度为0的顶点入队列}cout<<endl;if(count==verNum)returntrue; //输出全部顶点，拓扑排序成功returnfalse; //该有向图有环，拓扑排序失败}拓扑排序—基于邻接表与图的深度优先搜索方式遍历相同图的每条边处理一次图的每个顶点访问一次采用邻接表表示时，为O(n+e)采用相邻矩阵表示时，为O(n2)时间性能怎么知道图中所有顶点的入度？图基类中设有indegree数组保存顶点的入度，随边数的增减而变化是否可以用栈来取代队列？可以，只是排序结果不同讨论对下图进行拓扑排序，可以得到不同的拓扑序列的个数是（）【2012年全国统考408】4321ABCD提交单选题1分下列关于图的叙述中，正确的是（）。Ⅰ．回路是简单路径 Ⅱ．存储稀疏图，用邻接矩阵比邻接表更省空间Ⅲ．若有向图中存在拓扑序列，则该图不存在回路【2011年全国统考408】仅Ⅱ仅Ⅰ和Ⅱ仅Ⅲ仅Ⅰ和ⅢABCD提交单选题1分若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是【2012年全国统考408】存在，且唯一 存在，且不唯一存在，可能不唯一 无法确定是否存在ABCD提交单选题1分下列选项中，不是如下有向图的拓扑序列的是（）。【2018年全国统考408】1，5，2，3，6，45，1，2，6，3，45，1，2，3，6，45，2，1，6，3，4ABCD提交单选题1分修改递归方式实现的图的深度优先搜索（DFS）算法，将输出（访问）顶点信息的语句移到退出递归前（即执行输出语句后立刻退出递归）。采用修改后的算法遍历有向无环图G，若输出结果中包含G中的全部顶点，则输出的顶点序列是G的（）。【2020年全国统考408】拓扑有序序列逆拓扑有序序列广度优先搜索序列深度优先搜索序列ABCD提交单选题1分给定如下有向图，该图的拓扑有序序列的个数是（）。【2021年全国统考408】1234ABCD提交单选题1分9.1最小生成树9.2有向无环图及其应用9.3最短路径9.3.1单源点最短路径9.3.2每对顶点之间的最短路径*9.4算法拓展*9.5你怎么看？目录CONTENTS顶点——表示城市边——表示城市间的交通联系权——表示此线路的长度或沿此线路运输所花的时间或费用等源点——路径的开始顶点终点——路径的最后一个顶点问题——从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径——最短路径用带权的有向图表示一个交通运输网，图中最短路径

从某个源点到其它各顶点的最短路径:Dijkstra算法

每一对顶点之间的最短路径:Floyed算法最短路径

201531050v2v1v5v3v4v0202010301545v0->v210v0->v2->v325v0->v2->v3->v145v0->v445最短路径长度最短路径

单源最短路径给定一个带权图G=<V，E>，其中每条边（vi，vj）上的权W[vi，vj]是一个非负实数。另外，给定V中的一个顶点s充当源点。现在要计算从源点s到所有其他各顶点的最短路径，这个问题通常称为单源最短路径(single-sourceshortestpaths)问题单源最短路径解决单源最短路径问题的一个常用算法是Dijkstra算法，它是由E.W.Dijkstra提出的一种按路径长度递增的次序产生到各顶点最短路径的贪心算法。E.W.Dijkstra：1930年5月11日出身于theNetherlandsRotterdam.1972年获得图灵奖（对开发ALGOL做出了重要贡献）去世于2002年8月6日于Nuenen,theNetherlands.基本思想：按路径长度递增的次序来产生最短路径算法方法：把V分成两组

1.S：已求出最短路径的顶点的集合

2.V-S：尚未确定最短路径的顶点集合,将V-S中顶点按最短路径递增的次序加入到S中单源最短路径讨论如何找到从源点s到V-S中的顶点的当前最短路径？引入数组D，对于顶点vi∈V－S，D[i]表示从源点s开始，经过S中的顶点到达vi的当前最短路径的长度。对于V－S中的顶点，当前最短路径并不一定是最终的最短路径；而对于S中的顶点，当前最短路径一定是最终的最短路径。如何记录最短路径上的顶点？引入整型数组pre，数组元素pre[i]记录从源点s到顶点vi的最短路径上，位于顶点vi前面的顶点（vi的直接前驱）的序号。Dijkstra算法基本步骤：(1)初始化D、pre和visited数组；(2)从尚未确定最短路径长度的集合V-S中取出一个最短路径长度最小的顶点vk，将vk加入集合S，置visited[k]为true；(3)修改数组D中由s经过vk可达的最短路径长度。若加进vk做中间顶点，使得源点s到vi∈V－S的最短路径长度变短，则修改D[i]和pre[i]，即：当D[i]>D[k]+weight(vk，vi)时，置D[i]=D[k]+weight(vk，vi),pre[i]=k；(4)重复步骤2、3，直到V=S，算法结束。D数组记录了从源点s到图中其它顶点的最短路径长度。Dijkstra算法步骤Dijkstra示例Dijkstra算法示例求从源点start到其它顶点的最短路径。template<classVertexType,classEdgeType>booladjList<VertexType,EdgeType>::dijkstra(intstart,EdgeTypenoEdge)const{ if(start<0||start>verNum-1) //源点下标越界returnfalse;EdgeType*D=newEdgeType[verNum];//记录最短路径长度int*pre=newint[verNum]; //记录前驱edgeNode*p;EdgeTypemin;inti,j,k;for(i=0;i<verNum;++i){ //初始化visited[i]=false;D[i]=noEdge;pre[i]=-1;}

Dijkstra算法--基于邻接表Dijkstra算法--基于邻接表D[start]=0;pre[start]=start; //start到自身的路径长度置0min=D[start];k=start;for(i=1;i<verNum;++i){visited[k]=true; //刷新start到k的邻接点的最短路径长度for(p=verList[k].firstEdge;p!=NULL;p=p->next)

if

(!visited[p->to]&&D[p->to]>min+p->weight){D[p->to]=min+p->weight;pre[p->to]=k;}

min=noEdge;k=start;for(j=0;j<verNum;++j)//重新找当前路径长度最短且未被访问过的顶点kif(!visited[j]&&D[j]<min){k=j; min=D[k];}if(k!=start){printDijPath(start,k,pre); //输出start到k的最短路径cout<<":"<<D[k]<<endl;}}delete[]D;delete[]pre;returntrue;}Dijkstra算法--基于邻接表输出最短路径：距离数组D中还可以设立一个域pre来记录从源点到顶点v的最短路径上v前面经过的一个顶点当Dijkstra算法终止时就可以找到源点s到顶点v的最短路径上每个顶点的前一个顶点，从而找到源点s到顶点v的最短路径。*输出从源点到终点的最短路径上的顶点序列输出从源点from到to的最短路径上的顶点序列template<classVertexType,classEdgeType>voidadjList<VertexType,EdgeType>::printDijPath(intfrom,intto,intpre[])const{if(from==to){ //递归出口，遇到源点cout<<verList[from].vertex;return;}printDijPath(from,pre[to],pre);//递归输出前驱cout<<"->"<<verList[to].vertex;}*输出从源点到终点的最短路径上的顶点序列时间性能对于一个含n个顶点和e条边的有向图，基于邻接表的Dijkstra算法中第一个循环用于初始化数组，时间复杂度为O(n)；第二个循环用于更新V－S中的顶点的当前最短距离和寻找路径长度最短且未被访问过的顶点，时间复杂度为O(e+n2)，因此总的时间复杂度为O(n2)。基于邻接矩阵的Dijkstra算法的时间复杂度也是O(n2)。单源最短路径这种算法为什么得到的就是最短路径呢？事实上，如果存在一条从源点到u且长度比D[u]更短的路径，假设这条路径经过第二个集合的第一个顶点为x，则真实的最短路径为s->...->x->...->u，在这条路径上分别用d(s，x)，d(x，u)和d(s，u)表示源点s到顶点x、顶点x到顶点u和源点s到顶点u的路径，那么有：d(s，u)=d(s，x)+d(x，u)<D[u]，且D[x]≤d(s，x)。由边的权值的非负性，推得D[x]<D[u]。这与是第二个集合中路径值最小的顶点矛盾，所以每次加入第一个集合的u的路径值就是从s到u的最短路径长度。如果存在总权值为负的回路，则将出现权值为-

的情况-1A-3-2C讨论

Dijkstra算法支持负权值吗？即使不存在负的回路，也可能有在后面出现的负权值，从而导致整体计算错误主要原因是Dijkstra算法是贪心法，当作最小取进来后，不会返回去重新计算，如从A出发，先选C距离是6……10A6-8CBDE11讨论

如果不存在负权回路呢？

Dijkstra算法不受负权边的影响吗？Bellman－Ford算法参考书MIT“IntroductiontoAlgorithms”SPFA算法持负权值的最短路径算法对如下有向带权图，若采用迪杰斯特拉（Dijkstra）算法求从源点a到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是c，后续得到的其余各最短路径的目标顶点依次是（）。【2012年全国统考408】d，e，fe，d，ff，d，ef，e，dABCD提交单选题1分使用迪杰斯特拉（Dijkstra）算法求下图中从顶点1到其他各点的最短路径，依次得到的各最短路径的目标顶点是（）。

【2016年全国统考408】5，2，3，4，65，2，3，6，45，2，4，3，65，2，6，3，4ABCD提交单选题1分使用Dijkstra算法求下图中从顶点1到其余各顶点的最短路径，将当前找到的从顶点1到顶点2,3,4,5的最短路径长度保存在数组dist中，求出第二条最短路径后，dist中的内容更新为（）。【2021年全国统考408】26，3，14，6 25，3，14，621，3，14，6 15，3，14，6ABCD提交单选题1分作答带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径，假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：

①设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点；

②选择离u最近且尚未在最短路径中的一个顶点v，加入到最短路径中，修改当前顶点u=v；

③重复步骤②，直到u是目标顶点时为止。请问上述方法能否求得最短路径？若该方法可行，请证明之；否则，请举例说明。【2009年全国硕士研究生入学计算机学科专业基础综合试题】主观题10分【参考答案】上述方法不一定能求得最短路径，离顶点u最近未必离初始顶点最近。例如图9.19所示的带权图，从顶点1到顶点3的最短路径应为：1->2->3，路径长度为7；而用上述方法求得的最短路径是：1->5->6->3，路径长度为11。详细证明请参照Dijkstra算法。用Dijkstra算法的处理过程，源顶点为v0作答主观题10分9.1最小生成树9.2有向无环图及其应用9.3最短路径9.3.1单源点最短路径9.3.2每对顶点之间的最短路径*9.4算法拓展*9.5你怎么看？目录CONTENTS每对顶点之间的最短路径找出从任意顶点vi到顶点vj的最短路径，这个问题通常称为带权图的所有顶点对之间的最短路径(all-pairsshortestpaths)问题方法一：解决这一问题可以每次以一个顶点为源点，重复执行Dijkstra算法n次，这样就可以求得所有的顶点对之间的最短路径及其最短路径长度，其时间复杂度为O(n3)。voidDijkstra_P2P(graph&G){ Dist**D=newDist*[G.VerNum]; for(i=0;i<G.VerNum;i++) Dijkstra(i，noEdge);}方法二：Floyd算法是典型的动态规划法，自底向上分别求解子问题的解，然后由这些子问题的解得到原问题的解。这个算法的时间复杂度也是O(n3)，但形式上比较简单RobertW.Floyd:1936年6月8日生于纽约，“自学成才”斯坦福大学计算机科学系教授1978年图灵奖获得者每对顶点之间的最短路径Floyd算法步骤Floyd算法步骤描述如下：(1)初始化D矩阵和pre矩阵，若vi到vj没有弧，则D[i][j]=∞，Pre[i][j]=-1；若i=j，则D[i][j]=0，Pre[i][j]=i；否则，若vi到vj存在弧，则D[i][j]=weight(vi，vj)，Pre[i][j]=i。(2)对于每一个顶点vk，若D[i][k]+D[k][j]<D[i][j]成立，表明从vi经过vk再到vj的路径比原来vi到vj的路径短，则置D[i][j]=D[i][k]+D[k][j]，pre[i][j]=pre[k][j]。(3)将图中n个顶点依次加入每对顶点间进行探测，也就是对矩阵D和矩阵Pre进行n次更新，最终矩阵D中记录的便是每对顶点间的最短路径的长度。每对顶点之间的最短路径

每对顶点间的最短路径的Floyd算法迭代过程由图G构建邻接矩阵D(-1)在D(-1)的基础上加入V0,修改顶点间的最小距离在D(0)的基础上加入V1,修改顶点间的最小距离在D(1)的基础上加入V2,修改顶点间的最小距离手工模拟Floyd算法作答6311v2v1v024v0v1v2加入Vi后下图矩阵和上一步矩阵的值比较，取较小者主观题10分求各顶点间最短路径

template<classVertexType,classEdgeType>voidadjMatrix<VertexType,EdgeType>::floyd()const{ EdgeType**D=newEdgeType*[verNum];int**pre=newint*[verNum];inti,j,k;for(i=0;i<verNum;++i){D[i]=newEdgeType[verNum];pre[i]=newint[verNum];for(j=0;j<verNum;++j){D[i][j]=(i==j)?0:edges[i][j];pre[i][j]=(edges[i][j]==noEdge)?-1:i;}}Floyd算法

for(k=0;k<verNum;++k)for(i=0;i<verNum;++i)for(j=0;j<verNum;++j)if(D[i][k]!=noEdge&&D[k][j]!=noEdge&&D[i][k]+D[k][j]<D[i][j]){D[i][j]=D[i][k]+D[k][j];pre[i][j]=pre[k][j];}printFloyed(D,pre);for(i=0;i<verNum;++i){delete[]D[i];delete[]pre[i];}delete[]D;delete[]pre;}Floyd算法

*输出各顶点间的最短路径输出各顶点间的最短路径template<classVertexType,classEdgeType>voidadjMatrix<VertexType,EdgeType>::printFloyed(EdgeType**D,int**pre)const{ inti,j,k;cout<<"shortestpath：\n";for(i=0;i<verNum;++i){for(j=0;j<verNum;++j)cout<<D[i][j]<<'\t';cout<<endl;}cout<<"precursorofvertex：\n";for(i=0;i<verNum;++i){for(j=0;j<verNum;++j)cout<<pre[i][j]<<'\t';cout<<endl;}}三重for循环复杂度是o(n3)时间性能在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（）。G中有弧<Vi，Vj>G中有一条从Vi到Vj的路径G中没有弧<Vi,Vj>G中有一条从Vj到Vi的路径ABCD提交单选题1分下列有关图的说法错误的是（）在有向图中，出度为0的结点称为叶子。用邻接矩阵表示图，容易判断任意两个结点之间是否有边相连，并求得各结点的度。按深度方向遍历图和先根次序遍历树类似，得到的结果是唯一的。若有向图G中从结点Vi到结点Vj有一条路径，则在图G的结点的线性序列中结点Vi必在结点Vj之前的话，则称为一个拓扑序列。ABCD提交单选题1分9.1最小生成树9.2有向无环图及其应用9.3最短路径*9.4算法拓展*9.5你怎么看？目录CONTENTS算法拓展给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。voidHospital(AdjMatrixw,intn)∥医院建在何处，使离医院最远的村庄到医院的路径最短{for(k=1;k<=n;k++)∥求任意两顶点间的最短路径

for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(w[i][k]+w[k][j]<w[i][j])w[i][j]=w[i][k]+w[k][j];m=MAXINT