학습 노트 - 관건 적 인 경로

중요 경로:

AOE - 네트워크

AOE - 네트워크 의 기본 개념

몇 가지 중요 한 정의

관건 적 인 경로 의 기본 절차

수 정 된 토폴로지 정렬 알고리즘

관건 적 인 경로 의 실현 알고리즘

AOE - 네트워크:
방향 도 에서 정점 으로 사건 을 표시 하고 호 로 활동 을 표시 하 며 호의 가중치 는 활동 에 필요 한 시간 을 나타 낸다.무 환 도 를 향 해 활동 을 표시 하 는 그물 이 있 는데, 줄 여서 AOE - 그물 이 라 고 한다.
AOE - 네트워크 의 기본 개념:
원점: 유일한 입 도 는 0 의 정점 이 존재 하 는데 원점 이 라 고 합 니 다.외환 점: 유일한, 출 도 0 의 정점 이 존재 하 는데 외환 점 이 라 고 합 니 다.관건 적 인 경로: 원점 에서 외환 점 까지 의 가장 긴 경로 의 길 이 는 전체 공사 임 무 를 완성 하 는 데 필요 한 시간 이 고 이 경 로 를 관건 적 인 경로 라 고 합 니 다.관건 적 인 활동: 관건 적 인 경로 의 활동 을 관건 적 인 활동 이 라 고 한다.
몇 가지 중요 한 정의:
ve (i): 이벤트 vi 의 최초 발생 시간, 즉 원점 에서 정점 vi 까지 의 최 장 경로 의 길이 입 니 다. -ve (i) 를 구 할 때 원점 에서 시작 하여 토폴로지 정렬 에 따라 외환 점 으로 전달 할 수 있 습 니 다. ve (0) = 0;ve(i)=Max{ve(k)+dut()}; dut () 는 k 시 에서 j 시 까지 의 지속 시간 이나 변 권 이다.
vl (i): 사건 vi 의 가장 늦 은 발생 시간. -ve (i) 를 구 하 는 토대 에서 외환 점 부터 역 토폴로지 정렬 에 따라 원점 으로 전달 할 수 있다. vl (n - 1) = ve (n - 1);vl(i)=Min{vl(k)-dut()};
e (i): 활동 ai 의 최초 시작 시간. -만약 에 활동 ai 에 대응 하 는 호가 있다 면 e (i) 는 원점 에서 정점 j 까지 의 가장 긴 경로 의 길이, 즉 e (i) = ve (j) 와 같다.
l (i): 이벤트 ai 의 가장 늦 은 시작 시간. -이벤트 ai 에 대응 하 는 아크 가 dut () 이면 l (i) = vl (k) - dut ();
활동 ai 의 이완 시간: l (i) - e (i) 와 같다.
중요 한 경로 의 기본 절 차 를 찾 습 니 다:
1. 그림 의 정점 에 대해 토폴로지 정렬 을 하고 정렬 과정 에서 토폴로지 서열 에 따라 모든 사건 의 최초 발생 시간 ve (i) 를 구한다.2. 역 토폴로지 서열 에 따라 모든 사건 의 가장 늦게 발생 하 는 시간 vl (i) 을 구한다.3. 모든 활동 ai 의 최초 시작 시간 e (i) 와 가장 늦게 시작 하 는 시간 l (i) 을 구한다.4. e (i) = l (i) 의 활동 ai 를 찾아내 는 것 이 관건 적 인 활동 이다.
수 정 된 토폴로지 정렬 알고리즘:

int ve[MAX];/*           */
int TopoOrder(AdjList G，Stack *T)/*T         ，S      0     */
{ Stack S;
  int indegree[MAX];
  int i,j,count,k;
  ArcNode *p;
  FindID(G,indegree);/*      */
  InitStack(T);
  InitStack(&S);
  for(i=0;i<G.vexnum;i++){
     if(indegree[i]==0)
     Push(&S,i);/*    0     */
     count=0;
  for(j=0;j<G.vexnum;j++){
      ve[j]=0;/*   */
  while(!StackEmpty(S))
   {  Pop(&S,&j);
      Push(T,j);/*       T */
      count++;
      p=G.vertex[j].firstarc;
      while(p!==NULL)
      { k=p->adjvex;
        indegree[k]--;
        if(indegree[k]==0)
        Push(&S,k);/*     0，   */
        if(ve[k]+p->weight>ve[k])
           ve[k]=ve[j]+p->weight;/*           */
        p=p->nextarc;
        }
    } } }
   if(count<G.vexnum)
      return(Error);
    else return(Ok);
}

관건 적 인 경로 의 실현 알고리즘 을 구하 십시오:

int CriticalPath(AdjList G)
{ ArcNode *p;
  Stack T;
  int vl[MAX];
  int i,j,k,dut,ei,li;
  if(!TopoOrder(G,&T))
     return(Error);
  for(i=0;i<G.vexnum;i++){
     vl[i]=ve[i];/*   */
     while(!StackEmpty(T))
   {  Pop(&T,&i);/*           */
      p=G.vertex[i].firstarc;/*i     */
      while(p!==NULL)
      { k=p->adjvex;
        dut=p->weight;
        if(vl[k]-dut<vl[i])/*           */
           vl[i]=vl[k]-dut;
        p=p->nextarc;
        }
    }  }
   for(j=0;j<G.vexnum;j++){
      p=G.vertex[j].firstarc;
      while(p!=NULL)
      { k=p->adjnex;
        dut=p->weight;
        ei=ve[j];
        li=vl[k]-dut;
        tag=(ei==li)?'*':' ';/*  ei  li      ，   *，       */
        printf("%c,%c,%d,%d,%d,%c
",G.vertex[j].data,G.vertex[k].data,dut,ei,li,tag);
        /*      */
        p=p->nextarc;
      }
    }
    return（Ok);
}