AOE 네트워크 의 핵심 경 로 를 구하 세 요.

변 으로 활동 을 표시 하고, 정점 으로 사건 을 표시 하 는 유방 향 망 을 AOE (activity on edge) 망 이 라 고 한다. AOE 망 은 유방 향 무 환 도 이 며, 권 치 는 활동 이 지속 되 는 시간 을 나타 낸다.AOE 망 으로 공사 완료 시점 을 가늠 할 수 있다.공 사 는 시작 점 과 완성 점 이 하나 밖 에 없 기 때문에 순환 도로 가 없 는 조건 에서 네트워크 에 입 도 를 0 으로 하 는 점 과 출 도 를 0 으로 하 는 점 만 있 습 니 다. 다음은 AOE 네트워크 와 관련 된 몇 가지 개념 입 니 다. (1) 경로 길이: 경로 상 각 활동 의 지속 시간의 합 입 니 다.
(2) 공 사 를 완성 하 는 가장 짧 은 시간: AOE 네트워크 에서 활동 이 병행 되 기 때문에 공 사 를 완성 하 는 가장 짧 은 시간 은 시작 점 에서 완성 점 까지 의 가장 긴 길이 이다.(3) 활동 최초 시작 시간 (earlist time) (e (i)): 시작 점 에서 정점 vi 까지 의 가장 긴 경 로 를 사건 vi 의 최초 발생 시간 이 라 고 합 니 다.
이 시간 은 vi 를 끝 으로 하 는 아크 로 표 시 된 활동 의 최초 시작 시간 을 결정 합 니 다. (4) 활동 의 가장 늦 은 시작 시간 (latest time) (l (i): 전체 공사 의 완성 을 미 루 지 않 는 전제 에서 활동 이 가장 늦게 시작 되 는 시간 (5) 활동 을 완성 하 는 시간 여 유량: 이 활동 의 가장 늦 은 시작 시간 에서 가장 빠 른 시작 시간 (6) 관건 적 인 경로 (critical path) 를 줄 입 니 다.: 경로 길이 가 가장 긴 경 로 를 관건 적 인 경로 (7) 관건 적 인 활동 (critical activity) 이 라 고 한다. 관건 적 인 경로 에서 의 활동 을 관건 적 인 활동 이 라 고 한다. 관건 적 인 활동 의 특징 은 e (i) = l (i) 이 관건 적 인 경 로 를 분석 하 는 목적 은 전체 공사 에서 어떤 것 이 관건 적 인 활동 인지 판별 하여 관건 적 인 활동 의 업무 효율 을 향상 시 키 고 전체 공사 의 공사 기한 을 단축 시 키 는 것 이다.
파일 "aoe. h"

#include
#include
#include
#include
using namespace std;

const int MAX_VEX_NUM=20;
int ve[20];//    ,             

class ArcNode //   
{
public:
	int adjvex;
	int info;//  
	ArcNode *nextarc;
};

class VNode //   
{
public:
	string data;
	int indegree; //     
	ArcNode *firstarc;
};

class ALGraph 
{
private:
	VNode vertices[MAX_VEX_NUM];
	int arcnum;
	int vexnum;
public:

	void Create_ALG()
	{
		//     		
		string v1,v2;
		int i,j,w;
		ArcNode *p=NULL;

		cout<>vexnum>>arcnum;

		cout<>vertices[i].data;
			vertices[i].firstarc=NULL;
			vertices[i].indegree=0;
		}

		for(int k=0;k                      ：";
			cin>>v1>>v2>>w;
			i=Locate_Vex(v1);
			j=Locate_Vex(v2);

			while(i==-1 || j==-1)
			{
				cout<>v1>>v2;
				i=Locate_Vex(v1);
				j=Locate_Vex(v2);
			}

			p=new ArcNode;
			p->adjvex=j;
			p->info=w;
			p->nextarc=vertices[i].firstarc;
			vertices[i].firstarc=p;
			vertices[j].indegree+=1; //             1
		}

		cout<  ,        dut().      ：
			/ e(i)=ve(j),   l(i)=vl(k)-dut();
			/     vj       ve(j)       vl(j)      ：
			/ (1): ve(0)=0(    0    )  ，            
			/        ： ve(j)=Max{ve(i)+dut()}   i j          
			/ (2) vl(n-1)=ve(n-1)  ，                   ：
			/ vl(i)=Min{vl(j)-dut()}   j i        
			/                            ，    ve(j-1)
			/    vj                      。 vl(j-1)    
			/ vj                      ，            
			/         ve(j-1) vl(j-1).
			/                      vl ，            
			/          ，          ，            .
			/         ，                   .
			/----------------------------------------------------------------*/

	//            
	bool Topo_Order(stack &T)
	{
		stack s;
		ArcNode *p=NULL;
		for(int i=0;inextarc)
			{
				int w=p->adjvex;
				if(vertices[w].indegree)
					vertices[w].indegree--;
				if(!vertices[w].indegree)
					s.push(w);
				if(ve[k]+p->info>ve[w]) // ve[w]       
					ve[w]=ve[k]+p->info;
			}
		}
		if(count T;
		string cp[10];
		int c=0;
		if(!Topo_Order(T))
		{
			cout<nextarc)
			{
				int k=p->adjvex;
				int dut=p->info;
				if(vl[k]-dutnextarc)
			{
				int k=p->adjvex;
				int dut=p->info;
				int ee=ve[j];
				int el=vl[k]-dut;
				char tag;
				tag=(ee==el)?'*':' ';
				cout<";
		cout<

주 함수 "main. cpp"

#include"aoe.h"

int main()
{
	ALGraph G;
	G.Create_ALG();
	G.Critical_Path();
	cout<

입 출력 결과:

        ：6 8
      ：v1 v2 v3 v4 v5 v6
   ->                      ：v1 v2 3
   ->                      ：v1 v3 2
   ->                      ：v2 v5 3
   ->                      ：v2 v4 2
   ->                      ：v3 v4 4
   ->                      ：v3 v6 3
   ->                      ：v4 v6 2
   ->                      ：v5 v6 1
       
tail  head  weight  earliest time  latest time  tag
 v1    v3      2        0               0        *
 v1    v2      3        0               1
 v2    v4      2        3               4
 v2    v5      3        3               4
 v3    v6      3        2               5
 v3    v4      4        2               2        *
 v4    v6      2        6               6        *
 v5    v6      1        6               7
The critical activities are ended with *
So the critical path is :v1->v3->v4->v6

Press any key to continue

입력 에 따라 생 성 된 유방 향 망 은 다음 과 같다.
관건 적 인 경로 가 하나 밖 에 없 을 때 출력 관건 적 인 경로 가 옳 습 니 다. 관건 적 인 경로 가 하 나 를 모 를 때 틀 렸 지만 모든 관건 적 인 활동, 경로 출력 알고리즘 을 찾 을 수 있 습 니 다. 나중에 출력 할 수 있 기 때문에 관건 적 인 경 로 를 보완 할 수 있 습 니 다.
역 토폴로지 질서 서열 을 구 하 는 것 은 토폴로지 질 서 를 구 할 때 창고 에 들 어 가 는 것 을 제외 하고 DFS 로 이 방향 도 를 직접 옮 겨 다 닐 수 있다. 이 노드 의 모든 인접 노드 가 출력 될 때 까지 이 서열 은 역 토폴로지 질서 서열 이다.