拓?fù)渑判蛑饕菫榻鉀Q一個工程能否順序進行的問題，但有時我們還需要解決工程完成需要的最短時間問題。比如說，造一輛汽車，我們需要先造各種各樣的零件、部件，最終再組裝成車，如下圖所示。這些零部件基本都是在流水線上同時生產(chǎn)的，假如造一個輪子需要0.5天時間，造一個發(fā)動機需要3天時間，造一個車底盤需要2天時間，造一個外殼需要2天時間，其他零部件時間需要2天，全部零部件集中到一處需要0.5天，組裝成車需要2天時間，請問，在汽車廠造一輛車，最短需要多少時間呢？
有人說時間就是全部加起來，這當(dāng)然是不對的。我已經(jīng)說了前提，這些零部件都是分別在流水線上同時生產(chǎn)的，也就是說，在生產(chǎn)發(fā)動機的3天里，可能已經(jīng)生產(chǎn)了6個輪子，1.5個外殼和1.5個底盤，而組裝車是在這些零部件都生產(chǎn)好后才可以進行。因此最短的時間其實是零部件中生產(chǎn)時間最長的發(fā)動機3天+集中零部件0.5天+組裝車的2天，一共5.5天完成一輛汽車的生產(chǎn)。
因此，我們?nèi)绻獙σ粋€流程圖獲得最短時間，就必須要分析它們的拓?fù)潢P(guān)系，并且找到當(dāng)中最關(guān)鍵的流程，這個流程的時間就是最短時間。
因此在前面講了AOV網(wǎng)的基礎(chǔ)上，我們來介紹一個新的概念。在一個表示工程的帶權(quán)有向圖中，用頂點表示事件，用有向邊表示活動，用邊上的權(quán)值表示活動的持續(xù)時間，這種有向圖的邊表示活動的網(wǎng)，我們稱之為AOE網(wǎng)（Activity On Edge Net-work）。我們把AOE網(wǎng)中沒有入邊的頂點稱為始點或源點，沒有出邊的頂點稱為終點或匯點。由于一個工程，總有一個開始，一個結(jié)束，所以正常情況下，AOE網(wǎng)只有一個源點一個匯點。例如圖7-9-2就是一個AOE網(wǎng)。其中v0即是源點，表示一個工程的開始，v9是匯點，表示整個工程的結(jié)束，頂點v0，v1，……，v9分別表示事件，弧<v0,v1>，<v0,v2>，……，<v8,v9>都表示一個活動，用a0，a1，……，a12表示，它們的值代表著活動持續(xù)的時間，比如弧<v0,v1>就是從源點開始的第一個活動a0，它的時間是3個單位。
既然AOE網(wǎng)是表示工程流程的，所以它就具有明顯的工程的特性。如有在某頂點所代表的事件發(fā)生后，從該頂點出發(fā)的各活動才能開始。只有在進入某頂點的各活動都已經(jīng)結(jié)束，該頂點所代表的事件才能發(fā)生。
盡管AOE網(wǎng)與AOV網(wǎng)都是用來對工程建模的，但它們還是有很大的不同，主要體現(xiàn)在AOV網(wǎng)是頂點表示活動的網(wǎng)，它只描述活動之間的制約關(guān)系，而AOE網(wǎng)是用邊表示活動的網(wǎng)，邊上的權(quán)值表示活動持續(xù)的時間，如下圖所示兩圖的對比。因此，AOE網(wǎng)是要建立在活動之間制約關(guān)系沒有矛盾的基礎(chǔ)之上，再來分析完成整個工程至少需要多少時間，或者為縮短完成工程所需時間，應(yīng)當(dāng)加快哪些活動等問題。
我們把路徑上各個活動所持續(xù)的時間之和稱為路徑長度，從源點到匯點具有最大長度的路徑叫關(guān)鍵路徑，在關(guān)鍵路徑上的活動叫關(guān)鍵活動。顯然就上圖的AOE網(wǎng)而言，開始→發(fā)動機完成→部件集中到位→組裝完成就是關(guān)鍵路徑，路徑長度為5.5。
如果我們需要縮短整個工期，去改進輪子的生產(chǎn)效率，哪怕改動成0.1也是無益于整個工期的變化，只有縮短關(guān)鍵路徑上的關(guān)鍵活動時間才可以減少整個工期長度。例如如果發(fā)動機制造縮短為2.5，整車組裝縮短為1.5，那么關(guān)鍵路徑長度就為4.5，整整縮短了一天的時間。
關(guān)鍵路徑算法原理
假設(shè)一個學(xué)生放學(xué)回家，除掉吃飯、洗漱外，到睡覺前有四小時空閑，而家庭作業(yè)需要兩小時完成。不同的學(xué)生會有不同的做法，抓緊的學(xué)生，會在頭兩小時就完成作業(yè)，然后看看電視、讀讀課外書什么的；但也有超過一半的學(xué)生會在最后兩小時才去做作業(yè)，要不是因為沒時間，可能還要再拖延下去。下面的同學(xué)不要笑，像是在說你的是吧，你們是不是有過暑假兩個月，要到最后幾天才去趕作業(yè)的壞毛病呀？這也沒什么好奇怪的，拖延就是人性幾大弱點之一。
這里做家庭作業(yè)這一活動的最早開始時間是四小時的開始，可以理解為0，而最晚開始時間是兩小時之后馬上開始，不可以再晚，否則就是延遲了，此時可以理解為2。顯然，當(dāng)最早和最晚開始時間不相等時就意味著有空閑。
接著，你老媽發(fā)現(xiàn)了你拖延的小秘密，于是買了很多的課外習(xí)題，要求你四個小時，不許有一絲空閑，省得你拖延或偷懶。此時整個四小時全部被占滿，最早開始時間和最晚開始時間都是0，因此它就是關(guān)鍵活動了。
也就是說，我們只需要找到所有活動的最早開始時間和最晚開始時間，并且比較它們，如果相等就意味著此活動是關(guān)鍵活動，活動間的路徑為關(guān)鍵路徑。如果不等，則就不是。
為此，我們需要定義如下幾個參數(shù)。
1.事件的最早發(fā)生時間etv（earliest time ofvertex）：即頂點vk的最早發(fā)生時間。
2.事件的最晚發(fā)生時間ltv（latest time ofvertex）：即頂點vk的最晚發(fā)生時間，也就是每個頂點對應(yīng)的事件最晚需要開始的時間，超出此時間將會延誤整個工期。
3.活動的最早開工時間ete（earliest time ofedge）：即弧ak的最早發(fā)生時間。
4.活動的最晚開工時間lte（latest time ofedge）：即弧ak的最晚發(fā)生時間，也就是不推遲工期的最晚開工時間。
我們是由1和2可以求得3和4，然后再根據(jù)ete[k]是否與lte[k]相等來判斷ak是否是關(guān)鍵活動。
關(guān)鍵路徑算法
我們將下面的AOE網(wǎng)轉(zhuǎn)化為鄰接表結(jié)構(gòu)如下圖所示，注意與拓?fù)渑判驎r鄰接表結(jié)構(gòu)不同的地方在于，這里弧鏈表增加了weight域，用來存儲弧的權(quán)值。
求事件的最早發(fā)生時間etv的過程，就是我們從頭至尾找拓?fù)湫蛄械倪^程，因此，在求關(guān)鍵路徑之前，需要先調(diào)用一次拓?fù)湫蛄兴惴ǖ拇a來計算etv和拓?fù)湫蛄辛斜怼榇?，我們首先在程序開始處聲明幾個全局變量。
int *etv, *ltv; /* 事件最早發(fā)生時間和最遲發(fā)生時間數(shù)組 */
int *stack2; /* 用于存儲拓?fù)湫蛄械臈?*/
int top2; /* 用于stack2的指針 */
其中stack2用來存儲拓?fù)湫蛄?，以便后面求關(guān)鍵路徑時使用。
下面是改進過的求拓?fù)湫蛄兴惴ā?/p>
/* 拓?fù)渑判?，用于關(guān)鍵路徑計算 */
Status TopologicalSort(GraphAdjList GL)
{
EdgeNode *e;
int i, k, gettop;
/* 用于棧指針下標(biāo) */
int top = 0;
/* 用于統(tǒng)計輸出頂點的個數(shù) */
int count = 0;
/* 建棧將入度為0的頂點入棧 */
int *stack;
stack = (int *)malloc(GL->numVertexes * sizeof(int));
for (i = 0; i < GL->numVertexes; i++)
if (0 == GL->adjList[i].in)
stack[++top] = i;
/* 初始化為0 */
top2 = 0;
/* 事件最早發(fā)生時間 */
etv = (int *)malloc(GL->numVertexes * sizeof(int));
for (i = 0; i < GL->numVertexes; i++)
/* 初始化為0 */
etv[i] = 0; \
/* 初始化 */
stack2 = (int *)malloc(GL->numVertexes * sizeof(int));
while (top != 0)
{
gettop = stack[top--];
count++;
/* 將彈出的頂點序號壓入拓?fù)湫蛄械臈?*/
stack2[++top2] = gettop;
for (e = GL->adjList[gettop].firstedge; e; e = e->next)
{
k = e->adjvex;
if (!(--GL->adjList[k].in))
stack[++top] = k;
/* 求各頂點事件最早發(fā)生時間值 */
if ((etv[gettop] + e->weight) > etv[k])
etv[k] = etv[gettop] + e->weight;
}
}
if (count < GL->numVertexes)
return ERROR;
else
return OK;
}
第11～15行為初始化全局變量etv數(shù)組、top2和stack2的過程。第21行就是將本是要輸出的拓?fù)湫蛄袎喝肴謼tack2中。第27～28行很關(guān)鍵，它是求etv數(shù)組的每一個元素的值。比如說，假如我們已經(jīng)求得頂點v0對應(yīng)的etv[0]=0，頂點v1對應(yīng)的etv[1]=3，頂點v2對應(yīng)的etv[2]=4，現(xiàn)在我們需要求頂點v3對應(yīng)的etv[3]，其實就是求etv[1]+len<v1,v3>與etv[2]+len<v2,v3>的較大值。顯然3+5<4+8，得到etv[3]=12，如下圖所示。在代碼中e->weight就是當(dāng)前弧的長度。
由此我們也可以得出計算頂點vk即求etv[k]的最早發(fā)生時間的公式是：
其中P[K]表示所有到達頂點vk的弧的集合。比如圖7-9-5的P[3]就是<v1,v3>和<v2,v3>兩條弧。len<vi,vk>是弧<vi,vk>上的權(quán)值。
下面我們來看求關(guān)鍵路徑的算法代碼。
/* 求關(guān)鍵路徑，GL為有向網(wǎng)，輸出GL的各項關(guān)鍵活動 */
void CriticalPath(GraphAdjList GL)
{
EdgeNode *e;
int i, gettop, k, j;
/* 聲明活動最早發(fā)生時間和最遲發(fā)生時間變量 */
int ete, lte;
/* 求拓?fù)湫蛄校嬎銛?shù)組etv和stack2的值 */
TopologicalSort(GL);
/* 事件最晚發(fā)生時間 */
ltv = (int *)malloc(GL->numVertexes * sizeof(int));
for (i = 0; i < GL->numVertexes; i++)
/* 初始化ltv */
ltv[i] = etv[GL->numVertexes - 1];
/* 計算ltv */
while (top2 != 0)
{
/* 將拓?fù)湫蛄谐鰲?，后進先出 */
gettop = stack2[top2--];
for (e = GL->adjList[gettop].firstedge; e; e = e->next)
{
/* 求各頂點事件的最遲發(fā)生時間ltv值 */
k = e->adjvex;
/* 求各頂點事件最晚發(fā)生時間ltv */
if (ltv[k] - e->weight < ltv[gettop])
ltv[gettop] = ltv[k] - e->weight;
}
}
/* 求ete，lte和關(guān)鍵活動 */
for (j = 0; j < GL->numVertexes; j++)
{
for (e = GL->adjList[j].firstedge; e; e = e->next)
{
k = e->adjvex;
/* 活動最早發(fā)生時間 */
ete = etv[j];
/* 活動最遲發(fā)生時間 */
lte = ltv[k] - e->weight;
* 兩者相等即在關(guān)鍵路徑上 */
if (ete == lte) /
printf("<v%d,v%d> length: %d , ",
GL->adjList[j].data, GL->adjList[k].data, e->weight);
}
}
}
1．程序開始執(zhí)行。第5行，聲明了ete和lte兩個活動最早最晚發(fā)生時間變量。
2．第6行，調(diào)用求拓?fù)湫蛄械暮瘮?shù)。執(zhí)行完畢后，全局變量數(shù)組etv和棧stack的值如下圖所示，top2=10。也就是說，對于每個事件的最早發(fā)生時間，我們已經(jīng)計算出來了。
3．第7～9行為初始化全局變量ltv數(shù)組，因為etv[9]=27，所以數(shù)組ltv當(dāng)前的值為：{27,27,27,27,27,27,27,27,27,27}
4．第10～19行為計算ltv的循環(huán)。第12行，先將stack2的棧頭出棧，由后進先出得到gettop=9。根據(jù)鄰接表中，v9沒有弧表，所以第13～18行循環(huán)體未執(zhí)行。
5．再次來到第12行，gettop=8，在第13～18行的循環(huán)中，v8的弧表只有一條<v8,v9>，第15行得到k=9，因為ltv[9]-3<ltv[8]，所以ltv[8]=ltv[9]-3=24，如下圖所示。
6．再次循環(huán)，當(dāng)gettop=7、5、6時，同理可算出ltv相對應(yīng)的值為19、13、25，此時ltv值為：{27，27，27，27，27，13，25，19，24，27}
7．當(dāng)gettop=4時，由鄰接表可得到v4有兩條弧<v4,v6>、<v4,v7>，通過第13～18行的循環(huán)，可以得到ltv[4]=min(ltv[7]-4,ltv[6]-9)=min(19-4,25-9)=15，如下圖所示。
此時你應(yīng)該發(fā)現(xiàn)，我們在計算ltv時，其實是把拓?fù)湫蛄械惯^來進行的。因此我們可以得出計算頂點vk即求ltv[k]的最晚發(fā)生時間的公式是：
其中S[K]表示所有從頂點vk出發(fā)的弧的集合。比如圖7-9-8的S[4]就是<v4,v6>和<v4,v7>兩條弧，en<vk,vj>是弧<vk,vj>上的權(quán)值。
就這樣，當(dāng)程序執(zhí)行到第20行時，相關(guān)變量的值如下圖所示，“比如etv[1]=3而ltv[1]=7，表示的意思就是如果時間單位是天的話，哪怕v1這個事件在第7天才開始，也可以保證整個工程的按期完成，你可以提前v1事件開始時間，但你最早也只能在第3天開始。跟我們前面舉的例子，是先完成作業(yè)再玩還是先玩最后完成作業(yè)一個道理。
8．第20～31行是來求另兩個變量活動最早開始時間ete和活動最晚開始時間lte，并對相同下標(biāo)的它們做比較。兩重循環(huán)嵌套是對鄰接表的頂點和每個頂點的弧表遍歷。
9．當(dāng)j=0時，從v0點開始，有<v0,v2>和<v0,v1>兩條弧。當(dāng)k=2時，ete=etv[j]=etv[0]=0。lte=ltv[k]-e->weight=ltv[2]-len<v0,v2>=4-4=0，此時ete=lte，表示弧<v0,v2>是關(guān)鍵活動，因此打印。當(dāng)k=1時，ete=etv[j]=etv[0]=0。lte=ltv[k]-e->weight=ltv[1]-len<v0,v1>=7-3=4，此時ete≠lte，因此<v0,v1>并不是關(guān)鍵活動，如下圖所示。
這里需要解釋一下，ete本來是表示活動<vk,vj>的最早開工時間，是針對弧來說的。但只有此弧的弧尾頂點vk的事件發(fā)生了，它才可以開始，因此ete=etv[k]。
而lte表示的是活動<vk,vj>的最晚開工時間，但此活動再晚也不能等vj事件發(fā)生才開始，而必須要在vj事件之前發(fā)生，所以lte=ltv[j]-len<vk,vj>。就像你晚上23點睡覺，你不能說到23點才開始做作業(yè)，而必須要提前2小時，在21點開始，才有可能按時完成作業(yè)。
所以最終，其實就是判斷ete與lte是否相等，相等意味著活動沒有任何空閑，是關(guān)鍵活動，否則就不是。10．j=1一直到j(luò)=9為止，做法是完全相同的，關(guān)鍵路徑打印結(jié)果為“<v0,v2>4,<v2,v3>8,<v3,v4>3,<v4,v7>4,<v7,v8>5,<v8,v9>3,”，最終關(guān)鍵路徑如下圖所示。
分析整個求關(guān)鍵路徑的算法，第6行是拓?fù)渑判?，時間復(fù)雜度為O(n+e)，第8～9行時間復(fù)雜度為O(n)，第10～19行時間復(fù)雜度為O(n+e)，第20～31行時間復(fù)雜也為O(n+e)，根據(jù)我們對時間復(fù)雜度的定義，所有的常數(shù)系數(shù)可以忽略，所以最終求關(guān)鍵路徑算法的時間復(fù)雜度依然是O(n+e)。
實踐證明，通過這樣的算法對于工程的前期工期估算和中期的計劃調(diào)整都有很大的幫助。不過注意，本例是唯一一條關(guān)鍵路徑，這并不等于不存在多條關(guān)鍵路徑的有向無環(huán)圖。如果是多條關(guān)鍵路徑，則單是提高一條關(guān)鍵路徑上的關(guān)鍵活動的速度并不能導(dǎo)致整個工程縮短工期，而必須提高同時在幾條關(guān)鍵路徑上的活動的速度。這就像僅僅是有事業(yè)的成功，而沒有健康的身體以及快樂的生活，是根本談不上幸福的人生一樣，三者缺一不可。
