《《数据结构》最短路径关键路径及其应用课件》由会员分享，可在线阅读，更多相关《《数据结构》最短路径关键路径及其应用课件（82页珍藏版）》请在金锄头文库上搜索。
1、2020年10月14日星期三,第1页,最短路径、关键路径及其应用,所谓最短路径问题是指：如果从图中某一顶点（称为源点）出发到达另一顶点（称为终点）的路径可能不止一条，如何找到一条路径使得沿此路径上各边的权值总和达到最小。,最短路径问题,求从某个源点到其余各点的最短路径,2020年10月14日星期三,第3页,每一对顶点之间的最短路径,2020年10月14日星期三,第4页,求从源点到其余各点的最短路径的算法的基本思想:,依最短路径的长度递增的次序求得各条路径,源点,v1,其中，从源点到顶点v的最短路径是所有路径中长度最短者。,v2,给定带权有向图G和源点v, 求从v到G中其余各顶点的最短路径。,V
2、5,V0,V2,V4,V1,V3,100,30,10,60,10,20,50,5,V0,V2,V4,V3,V5,V0,始点 终点 Di 最短路径,V1 V2 V3 V4 V5, 10 30 100, 10 30 100, 10 60 30 100, 10 60 30 100, 10 50 30 100,(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,
3、V4, V3) (V0, V4) (V0, V5), 10 50 30 90,(V0, V2) (V0, V4, V3) (V0, V4) (V0, V4, V5), 10 50 30 90,(V0, V2) (V0, V4, V3) (V0, V4) (V0, V4, V5), 10 50 30 60,(V0, V2) (V0, V4, V3) (V0, V4) (V0, V4, V3, V5), 10 50 30 60,(V0, V2) (V0, V4, V3) (V0, V4) (V0, V4, V3, V5),2020年10月14日星期三,第6页,在这条路径上，必定只含一条弧，并且这条
4、弧的权值最小。,下一条路径长度次短的最短路径的特点：,路径长度最短的最短路径的特点：,它只可能有两种情况：或者是直接从源点到该点(只含一条弧)； 或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)。,2020年10月14日星期三,第7页,其余最短路径的特点：,再下一条路径长度次短的最短路径的特点:,它可能有三种情况：或者是直接从源点到该点(只含一条弧)； 或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)；或者是从源点经过顶点v2，再到达该顶点。,它或者是直接从源点到该点(只含一条弧)； 或者是从源点经过已求得最短路径的顶点，再到达该顶点。,如何在计算机中求得最短路径？,2020年10
5、月14日星期三,第9页,求最短路径的迪杰斯特拉算法：,一般情况下， Distk = 或者 = + 。,设置辅助数组Dist，其中每个分量Distk 表示 当前所求得的从源点到其余各顶点 k 的最短路径。,Dijkstra提出了一个按路径“长度”递增的次序，逐步得到由给定源点到图的其余各点间的最短路径的算法： 假设我们以邻接矩阵cost表示所研究的有向网。 迪杰斯特拉算法需要一个顶点集合，初始时集合内只有一个源点V0 ，以后陆续将已求得最短路径的顶点加入到集合中，到全部顶点都进入集合了，过程就结束了。集合可用一维数组来表示，设此数组为S，凡在集合S以外的顶点，其相应的数组元素Si 为 0 ，否则
6、为 1 。,另需一个一维数组D，每个顶点对应数组的一个单元，记录从源点到其他各顶点当前的最短路径长度，其初值为Di=costV0i，i=1n。数组D中的数据随着算法的逐步进行要不断地修改 定义了S集合和D数组并对其初始化后，迪杰斯特拉算法在进行中，都是从S之外的顶点集合中选出一个顶点w，使Dw的值最小。于是从源点到达w只通过S中的顶点，把 w 加入集合S中，并调整D中记录的从源点到集合中每个顶点v的距离： 取Dv和Dw+costwv中值较小的作为新的Dv 重复上述，直到S中包含V中其余各顶点的最短路径。,V0 V1 V2 V3 V4 V5 V0 10 30 100 V1 5 V2 50 V3
7、10 V4 20 60 V5 ,V0,V2,V4,V3,V5 ,V1,V0,V2,V4,V3,V5,V0,V2,V4,V3,V0,V2,V4,V0,V2,S=V0,V1,V5,V3,V4,V2,Vj,V5,V4,V3,V2,V1,i=5,i=4,i=3,i=2,i=1,D 终点,2020年10月14日星期三,第13页,1）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。,2）修改其它各顶点的Distk值。 假设求得最短路径的顶点为u， 若 Distu+G.arcsukDistk 则将 Distk 改为 Distu+G.arcsuk。,V0和k之间存在弧,V0和k之间不存在弧,其
8、中的最小值即为最短路径的长度。,2020年10月14日星期三,第14页,求每一对顶点之间的最短路径,弗洛伊德算法的基本思想是：,从 vi 到 vj 的所有可能存在的路径中，选出一条长度最短的路径。,2020年10月14日星期三,第15页,若存在，则存在路径vi,vj / 路径中不含其它顶点 若,存在，则存在路径vi,v1,vj / 路径中所含顶点序号不大于1 若vi,v2, v2,vj存在， 则存在一条路径vi, , v2, vj / 路径中所含顶点序号不大于2 ,依次类推，则 vi 至 vj 的最短路径应是上述这些路径中，路径长度最小者。,问题描述： 已知一个各边权值均大于 0 的带权有向图
9、，对每对顶点 vivj，要求求出每一对顶点之间的最短路径和最短路径长度。 解决方案： 1. 每次以一个顶点为源点，重复执行迪杰斯特拉算法n次。这样，便可求得每一对顶点之间的最短路径。总的执行时间为O(n3)。 2. 形式更直接的弗洛伊德（Floyd）算法。时间复杂度也为O(n3)。,弗洛伊德算法思想： 假设求从顶点Vi到Vj的最短路径。如果从Vi到Vj有弧，则从Vi到Vj存在一条长度为aij的路径，该路径不一定是最短路径，尚需进行n次试探。 首先考虑路径（Vi,V0,Vj）是否存在（即判别（Vi,V0）、（V0,Vj）是否存在）。如存在，则比较（Vi,Vj）和（Vi,V0,Vj）的路径长度，取
10、长度较短者为从 Vi到Vj 的中间顶点的序号不大于0 的最短路径。假如在路径上再增加一个顶点 V1，依次类推。可同时求得各对顶点间的最短路径。,定义一个n阶方阵序列 D(-1),D(0),D(1),D(2),D(k),D(n-1) 其中： D(-1)ij= aij D(k)ij=Min D(k-1)ij, D(k-1)ik+ D(k-1)kj 0kn-1 可见，D(1)ij就是从vi到vj的中间顶点的序号不大于1的 最短路径的长度; D(k)ij就是从vi到vj的中间顶点的序号不大于k的 最短路径的长度; D(n-1)ij就是从vi到vj的最短路径的长度。,各顶点间的最短路径及其路径长度,最短
11、路径弗洛伊德举例,2,1,0,2,1,0,2,1,0,2,1,0,2,1,0,P(2),P(1),P(0),P(-1),P,2,1,0,2,1,0,2,1,0,2,1,0,2,1,0,D(2),D(1),D(0),D(-1),D,最短路径导航查询系统(图) 设计一个交通导航质询系统，能让旅客质询从任一个城市顶点到另一个城市顶点之间的最短路径问题。设计分为三个部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现两个城市顶点之间的最短路径问题。,该程序所做的工作是给司机们提供最佳路线，来提高能源和时间的合理利用。 此程序规定： 1.把城市交通线路转化为图，从而对图进行相应的结构
12、存储； 2.程序的输出信息主要为：起始城市到目的城市的最短路径； 3.程序的功能主要包括：城市之间路径的存储，最短路径的计算，以及最短路径和邻接矩阵的输出；,概要设计 对于这样的问题，先假设有四个城市甲乙丙丁，甲乙相距2千米，且只有从乙到甲的单程线路。甲丙相距7千米，且只有从甲到丙的单程线路。甲丁相距4千米，且只有从甲到丁的单程线路。乙丙相距5千米，且只有从丙到乙的单程线路。乙丁相距3千米，且只有从丁到乙的单程线路。丙丁相距3千米，且只有从丁到丙的单程线路。戊甲相距6千米，且只有从戊到甲的单程线路。戊丁相距2千米，且只有从丁到戊的单程线路。乙己相距8千米，且只有从乙到己的单程线路。丙己相距6千
13、米，且只有从己到丙的单程线路。 编程出能求出个一点到任一点的最短路经。,则图G的邻接矩阵为： 甲 乙 丙 丁 戊 己 甲 7 4 乙 2 8 丙 5 丁 3 3 2 戊 6 己 6 ,系统用到的数据有： int which; int v ; int endv; 用到的主要函数： 1）void DispMat(MGraph g) /输出邻接矩阵g 2）void ppath(int pathMAXV,int v,int endv) /输出相应选择的起点和终点的最短路 3）void DisPath(int AMAXV,int pathMAXV,int n,int v,int endv)/由path计
14、算最短 路径,4）void Floyd(MGraph g,int v,int endv) /采用弗洛伊德算法求没对顶点之间的最短 路径 5）int main（） /主函数 各程序模块之间的调用关系： 函数3）可以调用函数2）。 函数4）可以调用函数3）。 函数5）可以调用函数1）和函数4）。 （具体程序略）,首先运行程序，包括三个选项， a.需要求最短路径请按：1. b.输出有向图G的邻接矩阵：2. c.退出系统请按：3 . 然后可以根据不同的需要选择不同的选项进行操作 最后按3退出程序。,测试丁和己,2020年10月14日星期三,第29页,拓扑排序,问题:,假设以有向图表示一个工程的施工图或
15、程序的数据流图，则图中不允许出现回路。,检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序。,2020年10月14日星期三,第30页,何谓“拓扑排序”？,对有向图进行如下操作：,按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。AOV（Activity On Vertex）网:就是顶点代表活动，边（狐）表示活动的优先关系的有向图。,2020年10月14日星期三,第31页,例如：对于下列有向图,B,D,A,C,可求得拓扑有序序列： A B C D 或 A C B D,2020年10月14日星期三,第32页,B,D,A,C,反之，对于下列有向图,不能求得它的拓扑有序序列。,因为图中存在一个回路 B, C, D,施工从活动 a1、 a2开始，到达活动 a8和 a9时，整个施工结束。这类有向图中，顶点表示活动，弧表示活动 ai优先于活动 aj ，称这类有向图为顶点表示活动的网（AOV网）。,AOV网(Activity on vertex network) 一个有向图可用来表示一个施工流程图、一个产品生产流程图、或一个程序框图等。如图：,AOV网可解决
