/*
* @title：關鍵路徑
* @input： 有向帶權圖，圖以鄰接表形式表示，頭結點只存儲該頂點的度，後繼結點存儲頂點及權值
* @output： 所有可能關鍵路徑的並集path，path[i][0]及path[i][1]代表邊的頂點，path[i][2]代表權值
*/
import Java.util.*;
public class CriticalPathTest
{
public static void main(String[] args)
{
int[][] graph={{0， 1，6， 2，4， 3，5，}，{1， 4，1，}，{1， 4，1}，{1， 5，2，}，
{2， 6，9， 7，7，}，{1， 7，4，}，{1， 8，2，}，{2， 8，4，}，{2，}，};
int[][] path;
CriticalPath criticalPath=new CriticalPath();
criticalPath.input(graph);
path=criticalPath.getPath();
for(int i=0; i《criticalPath.getLength(); i++){
System.out.println(“邊：” + path[i][0]+ “-” + path[i][1] +“ 權：”+ path[i][2]);
}
}
}
class CriticalPath
{
private int[][] graph;
private int[][] path;
int len;
void input(int[][] graph)
{
this.graph=graph;
path=new int[graph.length-1][];
len=0;
calculate();
}
void calculate()
{
int[] ve=new int[graph.length]; //事件的最發生時間
Stack stack1=new Stack();
Stack stack2=new Stack();
int i，j，v;
for(int t ： ve) t=0;
stack1.push(0);
while(stack1.empty()!=true){
v=(Integer)stack1.pop();
for(i=1; i《graph[v].length; i=i+2){
j=graph[v][i];
if((--graph[j][0])==0){
stack1.push(j);
}
if(ve[v]+graph[v][i+1]》ve[j]){
ve[j]=ve[v]+graph[v][i+1];
}
}
stack2.push(v);
}
int[] vl=new int[graph.length]; //事件的最遲生時間
for(i=0; i《graph.length; i++) vl[i]=1000;
vl[graph.length-1]=ve[graph.length-1];
while(stack2.empty()!=true){
v=(Integer)stack2.pop();
for(i=1; i《graph[v].length; i=i+2){
j=graph[v][i];
if(vl[j]-graph[v][i+1]《vl[v]){
vl[v]=vl[j]-graph[v][i+1];
}
}
}
for(v=0; v《graph.length-1; v++){ //求關鍵路徑的所有邊
for(i=1; i《graph[v].length; i=i+2){
j=graph[v][i];
if(ve[v]==(vl[j]-graph[v][i+1])){
int[][] p={{v， j，graph[v][i+1]，}，};
path[len++]=p[0];
}
}
}
}
int[][] getPath()
{
return path;
}
int getLength()
{
return len;
}
}
結果如下：
邊：0-1 權：6
邊：1-4 權：1
邊：4-6 權：9
邊：4-7 權：7
邊：6-8 權：2
邊：7-8 權：4
易知關鍵路徑有兩條：
0-1-4-6-8 及 0-1-4-7-8
