5

图的应用——关键路径算法

 2 years ago
source link: https://blog.51cto.com/Laccoliths/5688489
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

图的应用——关键路径算法

精选 原创

Laccoliths 2022-09-19 13:25:13 博主文章分类：数据结构 ©著作权

文章标签 关键路径 数组 数据结构 文章分类 C/C++ 编程语言 yyds干货盘点 阅读数202

如果要对一个流程图获得最短时间，就必须要分析它们的拓扑关系，并找到当中最关键的流程，这个流程的时间就是最短时间。

在一个表示工程的带权有向图中，用顶点表示时间，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网，我们称之为AOE网（Activity On Edge Network）。把AOE网中没有入边的顶点称之始点或源点，没有出边的顶点称为源点或汇点。由于一个工程，总有一个开始，一个结束，所以正常情况下AOE网只有一个源点一个汇点。如图所示。

图的应用——关键路径算法_数组

既然AOE网是表示工程流程的，所以它就具有明显的工程的特性。如有在某顶点所代表的事件发生后，从该顶点出发的各活动才能开始。只有在进入某顶点的各活动都已经结束，该顶点所代表的事件才能发生。

尽管AOE网与AOV网都是用来对工程建模的，但它们还是有很大的不同的，主要体现在AOV网是顶点表示活动的网，它只描述活动之间的制约关系，而AOE网是用边表示活动的网边上的权值表示活动持续的时间，如下图所示两图的对比。因此，AOE网是要建立在活动之间制约关系没有矛盾的基础之上，再来分析完成整个工程至少需要多少时间，或者为缩短完成工程所需时间’应当加快哪些活动等问题。

图的应用——关键路径算法_数组_02

路径上各个活动所持续的时间之和称为路径长度，从源点到汇点且有最大长度的路径叫关键路径，在关键路径上的活动叫关键活动。在上图中就是关键路径，路径好穿那个地为5.5。

1.1 关键路径算法原理

关键路径算法需要定义几个参数：

  • 事件的最早发生时间etv（earliest time of vertex）：即顶点的最早发生时间。
  • 事件的最晚发生时间ltv（latest time of vertex）：即顶点的最晚发生时间，也就是每个顶点对应的事件最晚需要开始的时间，超出此时间会延误整个工期。
  • 活动的最早开工时间ete（earliest time of edge）：即弧的最早发生时间。
  • 活动的最晚开工时间lte（latest time of edge）：即弧的最晚发生时间，也就是不推迟工期的最晚开工时间。

由1和2可以求得3和4，再根据ete[k]是否与lte[k]相等来判断顶点是否是关键活动。

1.2 关键路径算法

将AOE网转化成邻接表结构如图所示，注意与拓扑排序的不同的地方在于，弧链表增加了weight域，用来存储弧的权值。

图的应用——关键路径算法_数组_04

只有缩短关键路径上关键活动的时间才可以减少整个工期长度。

只需要找到所有活动的最早开始时间和最晚开始时间，并且比较它们，如果相等就意味着此活动是关键活动，活动间的路径为关键路径。如果不等，则就不是。

关键路径算法的全局变量：

int *etv,*ltv; /* 事件最早发生时间和最迟发生时间数组 */
int *stack2;   /* 用于存储拓扑序列的栈 */
int top2;     /* 用于stack2的指针 */



关键路径算法的改进拓扑序列算法：



/* 拓扑排序 */
Status TopologicalSort(GraphAdjList GL)
{    /* 若GL无回路，则输出拓扑排序序列并返回1，若有回路返回0。 */    
  EdgeNode *e;    
  int i,k,gettop;   
  int top=0;  /* 用于栈指针下标  */
  int count=0;/* 用于统计输出顶点的个数 */   
  int *stack;  /* 建栈将入度为0的顶点入栈  */   
  stack=(int *)malloc(GL->numVertexes * sizeof(int) );    
  for(i = 0; i<GL->numVertexes; i++)                
    if(0 == GL->adjList[i].in) /* 将入度为0的顶点入栈 */           
      stack[++top]=i;    

top2=0;    
  etv=(int *)malloc(GL->numVertexes * sizeof(int) ); /* 事件最早发生时间数组 */    
  for(i=0; i<GL->numVertexes; i++)        
    etv[i]=0;    /* 初始化 */
  stack2=(int *)malloc(GL->numVertexes * sizeof(int) );/* 初始化拓扑序列栈 */

printf("TopologicalSort:\t");
  while(top!=0)    
  {        
    gettop=stack[top--];        
    printf("%d -> ",GL->adjList[gettop].data);        
    count++;        /* 输出i号顶点，并计数 */ 

stack2[++top2]=gettop;        /* 将弹出的顶点序号压入拓扑序列的栈 */

for(e = GL->adjList[gettop].firstedge; e; e = e->next)        
    {            
      k=e->adjvex;            
      if( !(--GL->adjList[k].in) )        /* 将i号顶点的邻接点的入度减1，如果减1后为0，则入栈 */                
        stack[++top]=k; 

if((etv[gettop] + e->weight)>etv[k])    /* 求各顶点事件的最早发生时间etv值 */                
        etv[k] = etv[gettop] + e->weight;
    }    
  }    
  printf("\n");   
  if(count < GL->numVertexes)        
    return ERROR;    
  else       
    return OK;
}



关键路径核心算法代码：



/* 求关键路径,GL为有向网，输出G的各项关键活动 */
void CriticalPath(GraphAdjList GL) 
{    
  EdgeNode *e;    
  int i,gettop,k,j;    
  int ete,lte;  /* 声明活动最早发生时间和最迟发生时间变量 */        
  TopologicalSort(GL);   /* 求拓扑序列，计算数组etv和stack2的值 */ 
  ltv=(int *)malloc(GL->numVertexes*sizeof(int));/* 事件最早发生时间数组 */   
  for(i=0; i<GL->numVertexes; i++)        
    ltv[i]=etv[GL->numVertexes-1];    /* 初始化 */        

printf("etv:\t");   
  for(i=0; i<GL->numVertexes; i++)        
    printf("%d -> ",etv[i]);    
  printf("\n"); 

while(top2!=0)    /* 出栈是求ltv */    
  {        
    gettop=stack2[top2--];        
    for(e = GL->adjList[gettop].firstedge; e; e = e->next)        /* 求各顶点事件的最迟发生时间ltv值 */        
    {            
      k=e->adjvex;            
      if(ltv[k] - e->weight < ltv[gettop])               
        ltv[gettop] = ltv[k] - e->weight;        
    }   
  }    

printf("ltv:\t");   
  for(i=0; i<GL->numVertexes; i++)        
    printf("%d -> ",ltv[i]);    
  printf("\n"); 

for(j=0; j<GL->numVertexes; j++)        /* 求ete,lte和关键活动 */        
  {            
    for(e = GL->adjList[j].firstedge; e; e = e->next)            
    {                
      k=e->adjvex;                
      ete = etv[j];        /* 活动最早发生时间 */                
      lte = ltv[k] - e->weight; /* 活动最迟发生时间 */               
      if(ete == lte)    /* 两者相等即在关键路径上 */                    
        printf("<v%d - v%d> length: %d \n",GL->adjList[j].data,GL->adjList[k].data,e->weight);
    }        
  }
}

        

        

            

                report
            

        

    







        
Recommend

        



                

    
About Joyk

    
 





Aggregate valuable and interesting links.

Joyk means Joy of geeK