關(guān)鍵路徑是指設(shè)計(jì)中從輸入到輸出經(jīng)過(guò)的延時(shí)最長(zhǎng)的邏輯路徑。優(yōu)化關(guān)鍵路徑是一種提高設(shè)計(jì)工作速度的有效方法。一般地，從輸入到輸出的延時(shí)取決于信號(hào)所經(jīng)過(guò)的延時(shí)最大路徑，而與其他延時(shí)小的路徑無(wú)關(guān)。在優(yōu)化設(shè)計(jì)過(guò)程中關(guān)鍵路徑法可以反復(fù)使用，直到不可能減少關(guān)鍵路徑延時(shí)為止。EDA工具中綜合器及設(shè)計(jì)分析器通常都提供關(guān)鍵路徑的信息以便設(shè)計(jì)者改進(jìn)設(shè)計(jì)，提高速度。
介紹
關(guān)鍵路徑通常（但并非總是）是決定項(xiàng)目工期的進(jìn)度活動(dòng)序列。它是項(xiàng)目中最長(zhǎng)的路徑，即使很小浮動(dòng)也可能直接影響整個(gè)項(xiàng)目的最早完成時(shí)間。關(guān)鍵路徑的工期決定了整個(gè)項(xiàng)目的工期，任何關(guān)鍵路徑上的終端元素的延遲在浮動(dòng)時(shí)間為零或負(fù)數(shù)時(shí)將直接影響項(xiàng)目的預(yù)期完成時(shí)間（例如在關(guān)鍵路徑上沒(méi)有浮動(dòng)時(shí)間）。但特殊情況下，如果總浮動(dòng)時(shí)間大于零，則有可能不會(huì)影響項(xiàng)目整體進(jìn)度。
一個(gè)項(xiàng)目可以有多個(gè)、并行的關(guān)鍵路徑。另一個(gè)總工期比關(guān)鍵路徑的總工期略少的一條并行路徑被稱為次關(guān)鍵路徑。最初，關(guān)鍵路徑方法只考慮終端元素之間的邏輯依賴關(guān)系。關(guān)鍵鏈方法中增加了資源約束。關(guān)鍵路徑方法是由杜邦發(fā)明的。
步驟
A、從開(kāi)始頂點(diǎn) v1 出發(fā)，令 ve(1)=0，按拓?fù)溆行蛐蛄星笃溆喔黜旤c(diǎn)的可能最早發(fā)生時(shí)間。
Ve(k)=max{ve(j)+dut(
如果得到的拓樸有序序列中頂點(diǎn)的個(gè)數(shù)小于網(wǎng)中頂點(diǎn)個(gè)數(shù)n，則說(shuō)明網(wǎng)中有環(huán)，不能求出關(guān)鍵路徑，算法結(jié)束。
B、從完成頂點(diǎn) 出發(fā)，令，按逆拓?fù)溆行蚯笃溆喔黜旤c(diǎn)的允許的最晚發(fā)生時(shí)間：
vl(j)=min{vl(k)-dut(
C、求每一項(xiàng)活動(dòng)ai（1 ≤ i ≤ m）的最早開(kāi)始時(shí)間e(i)=ve(j)，最晚開(kāi)始時(shí)間l(i)=vl(k)-dut(
若某條弧滿足 e(i)=l(i) ，則它是關(guān)鍵活動(dòng)。
相關(guān)術(shù)語(yǔ)
（1）AOE網(wǎng)
用頂點(diǎn)表示事件，弧表示活動(dòng)，弧上的權(quán)值表示活動(dòng)持續(xù)的時(shí)間的有向圖叫AOE（Activity On Edge Network）網(wǎng)。在建筑學(xué)中也稱為關(guān)鍵路線。AOE網(wǎng)常用于估算工程完成時(shí)間。例如：圖1.有向網(wǎng)絡(luò) 圖1 是一個(gè)網(wǎng)。其中有9個(gè)事件v1,v2,…,v9；11項(xiàng)活動(dòng)a1,a2,…,a11。每個(gè)事件表示在它之前的活動(dòng)已經(jīng)完成，在它之后的活動(dòng)可以開(kāi)始。如 v1表示整個(gè)工程開(kāi)始，v9 表示整個(gè)工程結(jié)束。V5表示活動(dòng)a2和a3已經(jīng)完成，活動(dòng)a7和a8可以開(kāi)始。與每個(gè)活動(dòng)相聯(lián)系的權(quán)表示完成該活動(dòng)所需的時(shí)間。如活動(dòng)a1需要6個(gè)時(shí)間單位可以完成。
一個(gè)AOE網(wǎng)的關(guān)鍵路徑可以不止一條。
只有在某頂點(diǎn)所代表的事件發(fā)生后，從該頂點(diǎn)出發(fā)的各有向邊所代表的活動(dòng)才能開(kāi)始。只有在進(jìn)入某一頂點(diǎn)的各有向邊所代表的活動(dòng)都已經(jīng)結(jié)束，該頂點(diǎn)所代表的事件才能發(fā)生。表示實(shí)際工程計(jì)劃的AOE網(wǎng)應(yīng)該是無(wú)環(huán)的，并且存在唯一的入度為0的開(kāi)始頂點(diǎn)和唯一的出度為0的完成頂點(diǎn)。
（2）活動(dòng)開(kāi)始的最早時(shí)間e(i)；
（3）活動(dòng)開(kāi)始的最晚時(shí)間l(i) 定義e(i)=l(i）的活動(dòng)叫關(guān)鍵活動(dòng)；
（4）事件開(kāi)始的最早時(shí)間ve(i)；
（5）事件開(kāi)始的最晚時(shí)間vl(i)。
應(yīng)用
（1）完成整個(gè)工程至少需要多少時(shí)間；
（2）哪些活動(dòng)是影響工程的關(guān)鍵。
1956年，杜邦提出關(guān)鍵路徑法，并于1957年首先用于1000萬(wàn)美元化工廠建設(shè)，工期比原計(jì)劃縮短了4個(gè)月。杜邦公司在采用關(guān)鍵路徑法的一年中，節(jié)省了100萬(wàn)美元。
算法
（1）輸入e條弧
（2）從源點(diǎn)v1出發(fā)，令ve(1)=0，求 ve(j) ,2<=j<=n；
（3）從匯點(diǎn)vn出發(fā)，令vl(n)=ve(n)，求 vl(i), 1<=i<=n-1；
（4）根據(jù)各頂點(diǎn)的ve和vl值，求每條弧s（活動(dòng)）的最早開(kāi)始時(shí)間e(s)和最晚開(kāi)始時(shí)間l(s)，其中e(s)=l(s)的為關(guān)鍵活動(dòng)。
求關(guān)鍵路徑是在拓?fù)渑判虻那疤嵯逻M(jìn)行的，不能進(jìn)行拓?fù)渑判颍匀灰膊荒芮箨P(guān)鍵路徑。
算法分析
（1）求關(guān)鍵路徑必須在拓?fù)渑判虻那疤嵯逻M(jìn)行，有環(huán)圖不能求關(guān)鍵路徑；
（2）只有縮短關(guān)鍵活動(dòng)的工期才有可能縮短工期；
（3）若一個(gè)關(guān)鍵活動(dòng)不在所有的關(guān)鍵路徑上，減少它并不能減少工期；
（4）只有在不改變關(guān)鍵路徑的前提下，縮短關(guān)鍵活動(dòng)才能縮短整個(gè)工期。
代碼
Status ToplogicalSort(ALGraph G,stack &T){
FindInDegree(G,indegree);
InitStack(S);count=0; ve[0..G.vexnum-1]=0;
while(!StackEmpty(S))
{ Pop(S,j);Push(T,j); ++count;
for(p=G.vertices[j].firstarc;p;p=p->nextarc)
{k=p>adjvex;
if(--indegree[k]==0) Push(S,k);
if(ve[j]+*(p->info)>ve[k]) ve[k]=ve[j]+*(p->info);
}
}
if(count else return OK; } status CriticalPath(ALGraph G){ if(!ToplogicalOrder(G,T)) return ERROR; vl[0..G.vex索納拉姆·泰匹塔克1]=ve[G.vexnum-1]; while(!StackEmpty(T)) for(Pop(T,j),p=G.vertices[j].firstarc;p;p=p->nextarc) {k=p->adjvex; dut=*(p->info); if(vl[k]-dut } for(j=0;j for(p=G.vertices[j].firstarc;p;p=p->nextarc) {k=p>adjvex; dut=*(p->info); ee=ve[j]; el=vl[k]; tag=(ee==el)?’*’：’’； printf(j,kdut,ee,el,tag); } } C++完整代碼 #include #include #include using namespace std; int n,m,w[1001][1001],prev[1001],queue[1001],時(shí)間[1001],l=0,r=0,Pos[1001],path[1001]; void init() { int i,a,b,c; scanf("%d%d",&n,&m); for (i=1;i<=m;i++) { scanf("%d%d%d",&a,&b,&c); w[a][b]=c; prev[b]++; } } inline void Newq(int v) { r++; queue[r]=v; } inline void Del(int v) { int i; for (i=1;i<=n;i++) if (w[v][i]) { prev[i]--; if (!prev[i]) Newq(i); } } void topo() { for (int i=1;i<=n;i++) if (!prev[i]) Newq(i); while (r { l++; Del(queue[l]); } } void crucialpath() { int i,j; memset(時(shí)間,0,sizeof(Time)); for (i=1;i<=n;i++) for (j=1;j<=n;j++) if ((w[j][queue[i]]) && (Time[j]+w[j][queue[i]]>Time[queue[i]])) { Time[queue[i]]=Time[j]+w[j][queue[i]]; Pos[queue[i]]=j; } } void print() { printf("%d\n",時(shí)間[n]); int i=n,k=0; while (i!=1) { k++; path[k]=i; } for (i=k;i>1;i--) printf("%d ",path[i]); printf("%d\n",path); } int main() { init(); TOPO(); crucialpath(); print(); return 0; } 參考資料 >