详解图的应用(最小生成树、拓扑排序、关键路径、最短路径)

2020-01-06 13:45:16王旭

e(i ) = ve(j)

l(i) = vl(k)-dut(<j,k>)

求ve(j)和vl(j)需分两步进行:
(1)从ve(0)开始向前递推
详解图的应用(最小生成树、拓扑排序、关键路径、最短路径)
其中,T是所有以第j个顶点为头的弧的结合。
(2)从vl(n-1)=ve(n-1)起向后递推
详解图的应用(最小生成树、拓扑排序、关键路径、最短路径)
其中,S是所有以第i个顶点为尾的弧的集合。

这两个递推公式的计算必须分别在拓扑有序和逆拓扑有序的前提下进行。也就是说ve(j-1)必须在vj的所有前驱的最早发生时间求得之后才能确定,而vl(j-1)则必须在vj的所有后继的最迟发生时间求得之后才能确定。因此,可以在拓扑排序的基础上计算ve(j-1)和vl(j-1)。

3.5 关键路径的算法:
(1)输入e条弧<j,k>,建立AOE-网的存储结构; 
(2)从源点v0出发,令ve[0]=0,按拓扑有序求其余各顶点的最早发生时间ve[i] (1≤i≤n-1)。如果得到的拓扑有序序列中顶点个数小于网中顶点数n,则说明网中存在环,不能求关键路径,算法终止;否则执行步骤(3)。
(3)从汇点vn出发,令vl[n-1]=ve[n-1],按逆拓扑有序求其余各顶点的最迟发生时间vl[i](n-2≥i≥0);
(4)根据各顶点的ve和vl值,求每条弧s的最早开始时间e(s)和最迟开始时间 l(s)。若某条弧满足条件e(s)=l(s),则为关键活动。

先将拓扑排序算法:TopologicalOrder()

CriticalPath便为求关键路径的算法:
 

  1. Status TopologicalOrder(ALGraph G,Stack &T){   //有向网G采用邻接表存储结构,求各顶点事件的最早发生时间ve(全局变量)。  
  2. //T为拓扑序列顶点栈,s为零入度顶点栈。若G无回路,返回G的一拓扑序列,函数值为OK,否则ERROR。    FindInDegree(G,indegree);//对各顶点求入度indegree[0..vernum-1]