#include "P267E.cpp"
template <class NameType, class DistType> 		
void Graph<NameType,DistType>::CriticalPath ( ) {
		//在此算法中需要對(duì)鄰接表中單鏈表的結(jié)點(diǎn)加以修改, 在各結(jié)點(diǎn)中增加一個(gè)int域cost, 記錄該結(jié)點(diǎn)所表示的邊
		//上的權(quán)值。
		   int i;  int k;  int e, l; 		   
		   Edge<NameType,DistType> *p;
		   int* Ve = new int[NumVertices]; int* Vl = new int[NumVertices];					//事件最早、最遲開始時(shí)間
		   for ( i=0; i<NumVertices; i++ ) Ve[i] = 0;					//Ve數(shù)組初始化
		   for ( i=0; i<NumVertices; i++ ) {							//順向計(jì)算事件最早允許開始時(shí)間Ve
			 p = NodeTable[i].adj;				//該頂點(diǎn)邊鏈表鏈頭指針p
			 while ( p != NULL ) {						//掃描邊鏈表, 找所有后繼鄰接頂點(diǎn)
			   k = p->dest;							// i的后繼鄰接頂點(diǎn)k
			   if ( Ve[i] + p->cost > Ve[k] ) Ve[k] = Ve[i] + p->cost; 
	 		   p = p->link;							//找下一個(gè)后繼
			 }
		   }
		   for ( i=0; i<NumVertices; i++ ) Vl[i] = Ve[NumVertices-1];					//逆向計(jì)算事件的最遲開始時(shí)間Vl
		   for ( i=NumVertices-2; i; i-- ) {							//按逆拓?fù)溆行蝽樞蛱幚?			 p = NodeTable[i].adj;						//該頂點(diǎn)邊鏈表鏈頭指針p
			 while ( p != NULL ) {
			   k = p->dest;							// i的后繼鄰接頂點(diǎn)k
			   if ( Vl[k] - p->cost < Vl[i]) Vl[i] = Vl[k] - p->cost;
			   p = p->link;							//找下一個(gè)后繼
			 }
		   };
		   for ( i=0; i<NumVertices; i++ ) {							//逐個(gè)頂點(diǎn)求各活動(dòng)的e[k], l[k]
			 p = NodeTable[i].adj;						//該頂點(diǎn)邊鏈表鏈頭指針p
			 while ( p != NULL ) {
			   k = p->dest;							// k是i的后繼鄰接頂點(diǎn)
			   e = Ve[i];  l = Vl[k] - p->cost;
			   if ( l == e )							//關(guān)鍵活動(dòng)
				 cout << "<" << i << "," << k << ">" << "is Critical Activity" << endl;
			   p = p->link;							//找下一個(gè)后繼
			 }
		   }
		}