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