1. 首頁 > 生活百科 > >

關鍵路徑是最長的還是最短的,關鍵路徑是事件結點網絡中(( 二 )

路徑生活百科


為了能按逆序拓撲有序序列的順序計算各個頂點的vl值，需記下在拓撲排序的過程中求得的拓撲有序序列，這就需要在拓撲排序算法中，增設一個棧，以記錄拓撲有序序列，則在計算求得各頂點的ve值之后，從棧頂到棧底便為逆拓撲有序序列 。
packagegraph;
importjava.util.*;
publicclassGrph_CriticalPath
{
Graph_AdjListadjList;
Stack<Integer>T=newStack<Integer>();
intve[];
intvl[];
finalintmax=10000;

publicGrph_CriticalPath(Graph_AdjListadjList)//圖的存儲結構是用的鄰接表
{
this.adjList=adjList;
intlength=adjList.vetexValue.length;
ve=newint[length];
vl=newint[length];
for(inti=0;i<length;i++)
{
ve[i]=0;
vl[i]=max;
}
}

publicvoidgetCriticalPath()
{
topologicalOrder();

intt=T.pop();
T.push(t);
vl[t]=ve[t];
while(!T.isEmpty())
{
intj=T.pop();
for(Graph_AdjList.ArcNodep=adjList.vetex[j].firstArc;p!=null;p=p.next)
{
intk=p.adjvex;
if(vl[k]-p.weight<vl[j])
{
vl[j]=vl[k]-p.weight;
}
}
}
for(inti=0;i<ve.length;i++)
{
for(Graph_AdjList.ArcNodep=adjList.vetex[i].firstArc;p!=null;p=p.next)
{
intk=p.adjvex;
intee=ve[i];
intel=vl[k]-p.weight;
if(ee==el)
{
System.out.print(i+","+k+"");
}

}
}
}

publicvoidtopologicalOrder()
{
Stack<Integer>S=newStack<Integer>();
S.push(0);
intcount=0;
while(!S.isEmpty())
{
intj=S.pop();
T.push(j);
count++;
Graph_AdjList.ArcNodep=null;
for(p=adjList.vetex[j].firstArc;p!=null;p=p.next)
{
intk=p.adjvex;
if(--adjList.degree[k]==0)
{
S.push(k);
}
if(ve[j]+p.weight>ve[k])
{
ve[k]=ve[j]+p.weight;
}
}
}
if(count<adjList.vetexValue.length)
{
System.out.println("圖中存在環路！");
return;
}
}

publicvoidprint()
{
while(!T.isEmpty())
{
System.out.print(T.pop()+"");
}
}

publicvoidprintVel()
{
System.out.println();
for(inti=0;i<ve.length;i++)
{
System.out.print(ve[i]+"");
}
System.out.println();
for(inti=0;i<vl.length;i++)
{
System.out.print(vl[i]+"");
}
}


}轉自：http://blog.csdn.net/pigli/article/details/5777048
追問好詳細，謝謝 。。追答舉手之勞
什么叫做關鍵路徑：

關鍵路徑是最長的還是最短的,關鍵路徑是事件結點網絡中(

文章插圖
關鍵路徑是指設計中從輸入到輸出經過的延時最長的邏輯路徑 。優化關鍵路徑是一種提高設計工作速度的有效方法 。一般地，從輸入到輸出的延時取決于信號所經過的延時最大路徑，而與其他延時小的路徑無關 。在優化設計過程中關鍵路徑法可以反復使用，直到不可能減少關鍵路徑延時為止 。EDA工具中綜合器及設計分析器通常都提供關鍵路徑的信息以便設計者改進設計，提高速度 。
關鍵路徑通常是決定項目工期的進度活動序列 。它是項目中最長的路徑，即使很小浮動也可能直接影響整個項目的最早完成時間 。關鍵路徑的工期決定了整個項目的工期，任何關鍵路徑上的終端元素的延遲在浮動時間為零或負數時將直接影響項目的預期完成時間 。[2]但特殊情況下，如果總浮動時間大于零，則有可能不會影響項目整體進度 。
一個項目可以有多個、并行的關鍵路徑 。另一個總工期比關鍵路徑的總工期略少的一條并行路徑被稱為次關鍵路徑 。最初，關鍵路徑方法只考慮終端元素之間的邏輯依賴關系 。關鍵鏈方法中增加了資源約束 。關鍵路徑方法是由杜邦公司發明的

推薦閱讀