《数据结构》最短路径关键路径及其应用解析

2020年4月11日星期六第1页最短路径、关键路径及其应用所谓最短路径问题是指：如果从图中某一顶点（称为源点）出发到达另一顶点（称为终点）的路径可能不止一条，如何找到一条路径使得沿此路径上各边的权值总和达到最小。最短路径问题+求从某个源点到其余各点的最短路径2020年4月11日星期六第3页每一对顶点之间的最短路径2020年4月11日星期六第4页求从源点到其余各点的最短路径的算法的基本思想:依最短路径的长度递增的次序求得各条路径源点v1…其中，从源点到顶点v的最短路径是所有路径中长度最短者。v2给定带权有向图G和源点v,求从v到G中其余各顶点的最短路径。V5V0V2V4V1V31003010601020505V0V2V4V3V5V0始点终点D[i]最短路径V1V2V3V4V5∞10∞30100∞10∞30100∞106030100∞106030100∞105030100(V0,V2)(V0,V4)(V0,V5)(V0,V2)(V0,V4)(V0,V5)(V0,V2)(V0,V2,V3)(V0,V4)(V0,V5)(V0,V2)(V0,V2,V3)(V0,V4)(V0,V5)(V0,V2)(V0,V4,V3)(V0,V4)(V0,V5)∞10503090(V0,V2)(V0,V4,V3)(V0,V4)(V0,V4,V5)∞10503090(V0,V2)(V0,V4,V3)(V0,V4)(V0,V4,V5)∞10503060(V0,V2)(V0,V4,V3)(V0,V4)(V0,V4,V3,V5)∞10503060(V0,V2)(V0,V4,V3)(V0,V4)(V0,V4,V3,V5)2020年4月11日星期六第6页在这条路径上，必定只含一条弧，并且这条弧的权值最小。下一条路径长度次短的最短路径的特点：路径长度最短的最短路径的特点：它只可能有两种情况：或者是直接从源点到该点(只含一条弧)；或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)。2020年4月11日星期六第7页其余最短路径的特点：再下一条路径长度次短的最短路径的特点:它可能有三种情况：或者是直接从源点到该点(只含一条弧)；或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)；或者是从源点经过顶点v2，再到达该顶点。它或者是直接从源点到该点(只含一条弧)；或者是从源点经过已求得最短路径的顶点，再到达该顶点。如何在计算机中求得最短路径？2020年4月11日星期六第9页求最短路径的迪杰斯特拉算法：一般情况下，Dist[k]=源点到顶点k的弧上的权值或者=源点到其它顶点的路径长度+其它顶点到顶点k的弧上的权值。设置辅助数组Dist，其中每个分量Dist[k]表示当前所求得的从源点到其余各顶点k的最短路径。Dijkstra提出了一个按路径“长度”递增的次序，逐步得到由给定源点到图的其余各点间的最短路径的算法：假设我们以邻接矩阵cost表示所研究的有向网。迪杰斯特拉算法需要一个顶点集合，初始时集合内只有一个源点V0，以后陆续将已求得最短路径的顶点加入到集合中，到全部顶点都进入集合了，过程就结束了。集合可用一维数组来表示，设此数组为S，凡在集合S以外的顶点，其相应的数组元素S[i]为0，否则为1。另需一个一维数组D，每个顶点对应数组的一个单元，记录从源点到其他各顶点当前的最短路径长度，其初值为D[i]=cost[V0][i]，i=1…n。数组D中的数据随着算法的逐步进行要不断地修改定义了S集合和D数组并对其初始化后，迪杰斯特拉算法在进行中，都是从S之外的顶点集合中选出一个顶点w，使D[w]的值最小。于是从源点到达w只通过S中的顶点，把w加入集合S中，并调整D中记录的从源点到集合中每个顶点v的距离：取D[v]和D[w]+cost[w][v]中值较小的作为新的D[v]重复上述，直到S中包含V中其余各顶点的最短路径。V0V1V2V3V4V5V0∞∞10∞30100V1∞∞5∞∞∞V2∞∞∞50∞∞V3∞∞∞∞∞10V4∞∞∞20∞60V5∞∞∞∞∞∞{V0,V2,V4,V3,V5,V1}{V0,V2,V4,V3,V5}{V0,V2,V4,V3}{V0,V2,V4}{V0,V2}S={V0}V1V5V3V4V2VjV5V4V3V260305010∞60{V0,4,3,5}305010∞90{V0,4,5}3050{V0,4,3}10∞100{V0,5}30{V0,4}60{V0,2,3}10∞100{V0,5}30{V0,4}∞10{V0,2}∞V1i=5i=4i=3i=2i=1D终点V0V2V1V4V5V355030101010060202020年4月11日星期六第13页1）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。2）修改其它各顶点的Dist[k]值。假设求得最短路径的顶点为u，若Dist[u]+G.arcs[u][k]Dist[k]则将Dist[k]改为Dist[u]+G.arcs[u][k]。INFINITYkvarcsGkDist]][0[.][V0和k之间存在弧V0和k之间不存在弧其中的最小值即为最短路径的长度。2020年4月11日星期六第14页求每一对顶点之间的最短路径弗洛伊德算法的基本思想是：从vi到vj的所有可能存在的路径中，选出一条长度最短的路径。2020年4月11日星期六第15页若vi,vj存在，则存在路径{vi,vj}//路径中不含其它顶点若vi,v1,v1,vj存在，则存在路径{vi,v1,vj}//路径中所含顶点序号不大于1若{vi,…,v2},{v2,…,vj}存在，则存在一条路径{vi,…,v2,…vj}//路径中所含顶点序号不大于2…依次类推，则vi至vj的最短路径应是上述这些路径中，路径长度最小者。问题描述：已知一个各边权值均大于0的带权有向图，对每对顶点vi≠vj，要求求出每一对顶点之间的最短路径和最短路径长度。解决方案：1.每次以一个顶点为源点，重复执行迪杰斯特拉算法n次。这样，便可求得每一对顶点之间的最短路径。总的执行时间为O(n3)。2.形式更直接的弗洛伊德（Floyd）算法。时间复杂度也为O(n3)。弗洛伊德算法思想：假设求从顶点Vi到Vj的最短路径。如果从Vi到Vj有弧，则从Vi到Vj存在一条长度为a[i][j]的路径，该路径不一定是最短路径，尚需进行n次试探。首先考虑路径（Vi,V0,Vj）是否存在（即判别（Vi,V0）、（V0,Vj）是否存在）。如存在，则比较（Vi,Vj）和（Vi,V0,Vj）的路径长度，取长度较短者为从Vi到Vj的中间顶点的序号不大于0的最短路径。假如在路径上再增加一个顶点V1，…依次类推。可同时求得各对顶点间的最短路径。定义一个n阶方阵序列D(-1),D(0),D(1),D(2),…,D(k),…,D(n-1)其中：D(-1)[i][j]=a[i][j]D(k)[i][j]=Min{D(k-1)[i][j],D(k-1)[i][k]+D(k-1)[k][j]}0≤k≤n-1可见，D(1)[i][j]就是从vi到vj的中间顶点的序号不大于1的最短路径的长度;D(k)[i][j]就是从vi到vj的中间顶点的序号不大于k的最短路径的长度;D(n-1)[i][j]就是从vi到vj的最短路径的长度。04116023∞0各顶点间的最短路径及其路径长度最短路径弗洛伊德举例04116023∞021CABCABCBCAABCABCABCABCBAABCABCABCABCBAACAB0210210210210P(2)P(1)P(0)P(-1)P2107320564007320664007320611400320611400210210210210D(2)D(1)D(0)D(-1)DCABCBAACAB最短路径导航查询系统(图)+设计一个交通导航质询系统，能让旅客质询从任一个城市顶点到另一个城市顶点之间的最短路径问题。设计分为三个部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现两个城市顶点之间的最短路径问题。+该程序所做的工作是给司机们提供最佳路线，来提高能源和时间的合理利用。+此程序规定：+1.把城市交通线路转化为图，从而对图进行相应的结构存储；+2.程序的输出信息主要为：起始城市到目的城市的最短路径；+3.程序的功能主要包括：城市之间路径的存储，最短路径的计算，以及最短路径和邻接矩阵的输出；+概要设计+对于这样的问题，先假设有四个城市甲乙丙丁，甲乙相距2千米，且只有从乙到甲的单程线路。甲丙相距7千米，且只有从甲到丙的单程线路。甲丁相距4千米，且只有从甲到丁的单程线路。乙丙相距5千米，且只有从丙到乙的单程线路。乙丁相距3千米，且只有从丁到乙的单程线路。丙丁相距3千米，且只有从丁到丙的单程线路。戊甲相距6千米，且只有从戊到甲的单程线路。戊丁相距2千米，且只有从丁到戊的单程线路。乙己相距8千米，且只有从乙到己的单程线路。丙己相距6千米，且只有从己到丙的单程线路。+编程出能求出个一点到任一点的最短路经。则图G的邻接矩阵为：+甲乙丙丁戊己+甲∞∞74∞∞++乙2∞∞∞∞8++丙∞5∞∞∞∞++丁∞33∞2∞++戊6∞∞∞∞∞++己∞∞6∞∞∞系统用到的数据有：intwhich;intv;intendv;用到的主要函数：1）voidDispMat(MGraphg)//输出邻接矩阵g2）voidppath(intpath[][MAXV],intv,intendv)//输出相应选择的起点和终点的最短路3）voidDisPath(intA[][MAXV],intpath[][MAXV],intn,intv,intendv)//由path计算最短路径4）voidFloyd(MGraphg,intv,intendv)//采用弗洛伊德算法求没对顶点之间的最短路径5）intmain（）//主函数+各程序模块之间的调用关系：+函数3）可以调用函数2）。+函数4）可以调用函数3）。+函数5）可以调用函数1）和函数4）。+（具体程序略）+首先运行程序，包括三个选项，+a.需要求最短路径请按：1.+b.输出有向图G的邻接矩阵：2.+c.退出系统请按：3.+然后可以根据不同的需要选择不同的选项进行操作+最后按3退出程序。测试丁和己2020年4月11日星期六第29页拓扑排序问题:假设以有向图表示一个工程的施工图或程序的数据流图，则图中不允许出现回路。检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序。2020年4月11日星期六第30页何谓“拓扑排序”？对有向图进行如下操作：按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。AOV（ActivityOnVertex）网:就是顶点代表活动，边（狐）表示活动的优先关系的有向图。2020年4月11日星期六第31页例如：对于下列有向图BDAC可求得拓扑有序序列：ABCD或ACBD2020年4月11日星期六第32页BDAC反之，对于下列有向图不能求得它的拓扑有序序列。因为图中存在一个回路{B,C,D}施工从活动a1、a2开始，到达活动a8和a9时，整个施工结束。这类有向图中，顶点表示活动，弧ai，aj表示活动ai优先于活动aj，称这类有向图为顶点表示活动的网（AOV网）。AOV网(Activityonvertexnetwork)一个有向图可用来表示一个施工流程图、一个产品生产流程图、或一个程序框图等。如图：a1a5a4a6a2a3a8a7a9AOV网可解决如下两个问题：（1）判定工程的可行性。显然，有回路，整个工程就无法结束（2）确定各项活动在整个工程执行中的先后顺序称这种先后顺序为拓扑有序序列。如图有如下拓扑有序序列：a1a2a3a4a5a6a7a8a9a2a6a1a3a4a5a7a9a8a1a5a4a6a2a3a8a7a92020年4月11日星期六第35页如何进行拓扑排序？一、从有向图中选取一个没有前驱的顶点，并输出之；重复上述两步，直