/*

　　* @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

　　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

　　j=graph[v][i];

　　if((--graph[j][0])==0){

　　stack1.push(j);

　　} [NextPage] 　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

　　vl[graph.length-1]=ve[graph.length-1];

　　while(stack2.empty()!=true){

　　v=(Integer)stack2.pop();

　　for(i=1; i

　　j=graph[v][i];

　　if(vl[j]-graph[v][i+1]

　　vl[v]=vl[j]-graph[v][i+1];

　　}

　　}

　　}

　　for(v=0; v

　　for(i=1; i

　　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