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

12六月2024第1页最短路径、关键路径及其应用所谓最短路径问题是指：如果从图中某一顶点〔称为源点〕出发到达另一顶点〔称为终点〕的路径可能不止一条，如何找到一条路径使得沿此路径上各边的权值总和到达最小。最短路径问题求从某个源点到其余各点的最短路径12六月2024第3页

每一对顶点之间的最短路径12六月2024第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)12六月2024第6页

在这条路径上，必定只含一条弧，并且这条弧的权值最小。下一条路径长度次短的最短路径的特点：路径长度最短的最短路径的特点：

它只可能有两种情况：或者是直接从源点到该点(只含一条弧)；或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)。12六月2024第7页其余最短路径的特点：再下一条路径长度次短的最短路径的特点:

它可能有三种情况：或者是直接从源点到该点(只含一条弧)；或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)；或者是从源点经过顶点v2，再到达该顶点。

它或者是直接从源点到该点(只含一条弧)；或者是从源点经过已求得最短路径的顶点，再到达该顶点。如何在计算机中求得最短路径？12六月2024第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中其余各顶点的最短路径。V0V1V2V3V4V5

V0∞∞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终点V0V2V1V4V5V3550301010100602012六月2024第13页1〕在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。2〕修改其它各顶点的Dist[k]值。假设求得最短路径的顶点为u，假设Dist[u]+G.arcs[u][k]<Dist[k]那么将Dist[k]改为Dist[u]+G.arcs[u][k]。V0和k之间存在弧V0和k之间不存在弧其中的最小值即为最短路径的长度。12六月2024第14页求每一对顶点之间的最短路径弗洛伊德算法的根本思想是：

从vi

到vj

的所有可能存在的路径中，选出一条长度最短的路径。12六月2024第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)//输出邻接矩阵g 2〕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退出程序。测试丁和己12六月2024第29页

拓扑排序

问题:假设以有向图表示一个工程的施工图或程序的数据流图，那么图中不允许出现回路。

检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序。12六月2024第30页何谓“拓扑排序”？对有向图进行如下操作：按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，那么可以人为加上任意的次序关系。AOV〔ActivityOnVertex〕网:就是顶点代表活动，边〔狐〕表示活动的优先关系的有向图。12六月2024第31页例如：对于以下有向图BDAC可求得拓扑有序序列：

ABCD

或

ACBD12六月2024第32页BDAC反之，对于以下有向图不能求得它的拓扑有序序列。因为图中存在一个回路

{B,C,D}施工从活动a1、a2开始，到达活动a8和a9时，整个施工结束。这类有向图中，顶点表示活动，弧<ai，aj>表示活动ai优先于活动aj，称这类有向图为顶点表示活动的网〔AOV网〕。AOV网(Activityonvertexnetwork)

一个有向图可用来表示一个施工流程图、一个产品生产流程图、或一个程序框图等。如图：a1a5a4a6a2a3a8a7a9AOV网可解决如下两个问题：〔1〕判定工程的可行性。显然，有回路，整个工程就无法结束〔2〕确定各项活动在整个工程执行中的先后顺序称这种先后顺序为拓扑有序序列。如图有如下拓扑有序序列：a1a2a3a4a5a6a7a8a9

a2a6a1a3a4a5a7a9a8a1a5a4a6a2a3a8a7a912六月2024第35页如何进行拓扑排序？一、从有向图中选取一个没有前驱的顶点，并输出之；

重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。二、从有向图中删去此顶点以及所

有以它为尾的弧；12六月2024第36页abcghdfeabhcdgfe在算法中需要用定量的描述替代定性的概念

没有前驱的顶点

入度为零的顶点删除顶点及以它为尾的弧

弧头顶点的入度减1由此分析知：拓扑排序算法的实现与顶点的入度有密切关系，因此，在选取存储结构时，应考虑：能容易得到各顶点的入度；有利于寻找任一顶点的所有直接后继。为此，采用邻接表作为AOV网的存储结构，并在头结点中增加一个存放顶点入度的域〔indegree〕12六月2024第38页取入度为零的顶点v;while(v<>0){

printf(v);++m;w:=FirstAdj(v);

while(w<>0){inDegree[w]--;w:=nextAdj(v,w);

}

取下一个入度为零的顶点v;}ifm<nprintf(“图中有回路”);算法描述12六月2024第39页为防止每次都要搜索入度为零的顶点，在算法中设置一个“栈”，以保存“入度为零”的顶点。CountInDegree(G,indegree);//对各顶点求入度InitStack(S);for(i=0;i<G.vexnum;++i)

if(!indegree[i])Push(S,i);//入度为零的顶点入栈12六月2024第40页count=0;//对输出顶点计数while(!EmptyStack(S)){

Pop(S,v);++count;printf(v);

for(w=FirstAdj(v);w;w=NextAdj(G,v,w)){

--indegree(w);//弧头顶点的入度减一

if(!indegree[w])Push(S,w);

//新产生的入度为零的顶点入栈

}}if(count<G.vexnum)printf(“图中有回路”)c1c9c4c2c12c10c11c5c3c6c7c8将表转换成图c1c9c4c2c12c10c11c5c3c6c7c8拓扑序列：c1,c9c4c2c12c10c11c5c3c6c7c8拓扑序列：c1,c9c4c2c12c10c11c5c3c6c7c8拓扑序列：c1,c9c4c2c12c10c11c5c3c6c7c8拓扑序列：c1,c9,c4,c2,c10,c11c12c5c3c6c7c8拓扑序列：c1,c9,c4,c2,c10,c11c12c5c3c6c7c8拓扑序列：c1,c9,c4,c2,c10,c11,c3,c12,c6c5c7c8拓扑序列：c1,c9,c4,c2,c10,c11,c3,c12,c6c5c7c8拓扑序列：c1,c9,c4,c2,c10,c11,c3,c12,c6,c5,c7,c8c1c9c4c2c12c10c11c5c3c6c7c8拓扑序列：c1,c9,c4,c2,c10,c11,c3,c12,c6,c5,c7,c812六月2024第52页

关键路径问题:

假设以有向网表示一个施工流图，弧上的权值表示完成该项子工程所需时间。问：哪些子工程项是“关键工程”？即：哪些子工程项将影响整个工程的完成期限的。一、AOE网可解决如下问题：估算工程的最短工期〔从源点到汇点至少需要多少时间〕找出哪些活动是影响整个工程进展的关键①②③⑤a1=6a4=1a2=4a5=1有4个事件：V1，V2，V3，V5V1为源点，V5为汇点有4个活动：a1,a2,a4,a5V3表示：a2已完成，a5可以开始二、关键路径几个术语路径长度：路径上各活动持续时间的总和〔即：路径上所有弧的权值之和〕关键路径：从源点到汇点之间路径长度最长的路径〔不一定唯一〕事件Vi的最早发生时间ve(i)：从源点到Vi的最长路径长度活动ai的最早开始时间e(i)：等于该活动的弧尾事件Vj的最早发生时间即假设<j,k>表示活动ai，那么有e(i)=ve(j)vjvkai事件vk的最迟发生时间vl(k)：是在不推迟整个工期的前提下，该事件最迟必须发生的时间活动ai的最迟开始时间L(i)：是该活动的弧头事件的最迟发生时间与该活动的持续时间之差，即L(i)=vl(k)-ai的持续时间关键活动：l(i)=e(i)的活动由此可见：在AOE网中找关键活动问题可转化为求l(i)=e(i)，而e(i)=ve(j)l(i)=vl(k)-ai的持续时间因此，需先求出事件的最早、最迟发生时间

关键路径三、关键路径算法思想1.从ve(1)=0开始利用下面递推公式，计算出各事件的最早发生时间ve(j)=Max{ve(i)+dut(<i,j>)}，j=2,……,n，<i,j>∈T其中：T是所有以j为头的弧集合dut(<i,j>)表示活动的持续时间前例中，ve(5)=Max{ve(2)+dut(<2,5>)，ve(3)+dut(<3,5>)}=Max{6+1,4+1}=7①②③⑤a1=6a4=1a2=4a5=12.从vl(n)=ve(n)开始，利用下面递推公式，计算出各事件的最迟发生时间：vl(i)=Min{vl(j)-dut(<i,j>)}i=n-1,……,2,1,<i,j>∈S其中：S是所有以i为尾的弧集合关键路径

关键路径3.设活动ai由弧<j,k>表示，其持续时间为dut(<j,k>)，那么利用下面公式，计算出各活动的最早、最迟开始时间：e(i)=ve(j)l(i)=vl(k)-dut(<j,k>)4.找出e(i)=l(i)的活动，即为关键活动，诸关键活动组成的从源点到汇点的路径即为关键路径jkai=dut(<j,k>)四、例子计算结果为：顶点VeVl活动弧持续Tell-e关键活动

V100a1<1,2>3011V234a2<1,3>2000a2V322a3<2.4>2341V466a4<2,5>3341V567a5<3,4>4220a5V688a6<3,6>3253a7<4,6>2660a7Max+Min-

a8<5,6>1671①②③④⑤⑥a4=3a2=2a1=3a5=4a6=3a7=2a8=1a3=2关键路径上的活动都是关键活动。缩短非关键活动都不能缩短整个工期如a6缩短为1，那么整个工期仍为8。又如a6推迟3天开始，或拖延3天完成〔a6=6〕均不影响整个工期①②③④⑤⑥a4=3a2=2a1=3a5=4a6=3a7=2a8=1a3=2分析关键路径的目的是找出影响整个工期的关键活动，缩短关键活动的持续时间，常可以缩短整个工期。如a7缩短为1，那么整个工期为7。此时，再缩短任一关键活动均不能缩短整个工期。即在有多条关键路径时，缩短那些在所有关键路上的关键活动，才能缩短整个工期①②③④⑤⑥a4=3a2=2a1=3a5=4a6=3a7=2a8=1a3=2v1v3v4v5v6v7v8v2v9最早发生时间ve[i]最迟发生时间vl[i]顶点序号viv1v3v4v5v6v7v8v2v9最早发生时间ve[i]最迟发生时间vl[i]顶点序号via2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4v1v3v4v5v6v7v8v2v9最早发生时间ve[i]最迟发生时间vl[i]顶点序号via2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4006650467778161618181414e[i]=ve[j]L[i]=vl[k]-dut<j,k>12六月2024第65页abcdefghk64521187244又例如:“关键活动”指的是：该弧上的权值增加

将使有向图上的最长路径的长度增加。整个工程完成的时间为：从有向图的源点到汇点的最长路径。源点汇点617412六月2024第66页abcdefghk6452118724400000000064571157151418181818181818181818161486610807拓扑有序序列:a-d-f-c-b-e-h-g-k12六月2024第67页064577151418181416107866000064577715141416023668871012六月2024第68页

算法的实现要点:显然，求ve的顺序应该是按拓扑有序的次序；

而求vl的顺序应该是按拓扑逆序的次序；因为拓扑逆序序列即为拓扑有序序列的逆序列，因此应该在拓扑排序的过程中，另设一个“栈”记下拓扑有序序列。下表给出了某工程各工序之间的优先关系和各工序所需的时问〔其中“一”表示无先驱工序〕，请完成以下各题： (1)

画出相应的AOE网。 (2)

列出各事件的最早发生时间和最迟发生时间。 (3)

求出关键路径并指明完成该工程所需的最短时间。实例 试题考核AOE网和关键路径问题。要求熟悉AOE网的概念和如何求关键路径的方法及步骤。 (1)

根据表的数据，可得AOE网，如下图。

(2)

所有事件的最早发生时间ve，如下所示：ve〔v1〕＝0

，ve〔v2〕＝3

，ve〔v3〕＝2ve〔v4〕＝Max{ve〔v2〕+2，ve〔v3〕+4}＝6

ve〔v5〕＝ve〔v2〕＋3＝6

，

ve〔v6〕＝Max{ve〔v3〕+3，ve〔v4〕+2，ve〔v5〕+1}＝8

所有事件的最迟发生时间vl，如下所示：vl〔v6〕＝8

，

vl〔v5〕＝vl〔v6〕－1＝7

vl〔v4〕＝vl〔v6〕－2＝6，vl〔v3〕＝Min{vl〔v4〕－4，vl〔v6〕－3}＝2vl〔v2〕＝Min{vl〔v4〕－2，vl〔v5〕－3}＝4vl〔v1〕＝Min{vl〔v2〕－3，vl〔v3〕－2}＝0(3)

求所有活动的最早发生时间e、最迟发生时间l和时间余量l-e。 e〔A〕＝ve〔v1〕＝0

l〔A〕＝vl〔v2〕－3＝1

l〔A〕－e〔A〕＝1