?? p297.cpp
字號(hào):
#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è)后繼
}
}
}
?? 快捷鍵說(shuō)明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -