资源描述：
《关键路径的java实现.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、关键路径的java实现/* *@title：关键路径 *@input:有向带权图，图以邻接表形式表示，头结点只存储该顶点的度，后继结点存储顶点及权值 *@output:所有可能关键路径的并集path，path[i][0]及path[i][1]代表边的顶点，path[i][2]代表权值 */ importjava.util.*; publicclassCriticalPathTest { publicstaticvoidmain(String[]args) { int[][]graph={{0,1
2、,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; CriticalPathcriticalPath=newCriticalPath(); criticalPath.input(graph); path=criticalPath.getPath(); for(inti=0;i
System.out.println("边："+path[i][0]+"
3、-"+path[i][1]+"权："+path[i][2]); } } } classCriticalPath { privateint[][]graph; privateint[][]path; intlen; voidinput(int[][]graph) { this.graph=graph; path=newint[graph.length-1][]; len=0; calculate(); } voidcalculate() { int[]ve=newint[graph
4、.length];//事件的最发生时间 Stackstack1=newStack(); Stackstack2=newStack(); inti,j,v; for(intt: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); }if(ve[v]+graph[v]
5、[i+1]>ve[j]){ ve[j]=ve[v]+graph[v][i+1]; } } stack2.push(v); } int[]vl=newint[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
6、][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() { returnpath; } intgetLength() { re
7、turnlen; } } 结果如下： 边：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
