《关键路径的java实现.doc》由会员分享，可在线阅读，更多相关《关键路径的java实现.doc（5页珍藏版）》请在三一文库上搜索。
1、关键路径的java实现/* title：关键路径* input: 有向带权图，图以邻接表形式表示，头结点只存储该顶点的度，后继结点存储顶点及权值* output: 所有可能关键路径的并集path，pathi0及pathi1代表边的顶点，pathi2代表权值*/import java.util.*;public class CriticalPathTestpublic 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,;in
2、t path;CriticalPath criticalPath=new CriticalPath();criticalPath.input(graph);path=criticalPath.getPath();for(int i=0; i System.out.println(边： + pathi0+ - + pathi1 + 权：+ pathi2);class CriticalPathprivate int graph;private int path;int len;void input(int graph)this.graph=graph;path=new intgraph.lengt
3、h-1;len=0;calculate();void calculate()int ve=new intgraph.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=graphvi;if(-graphj0)=0)stack1.push(j);if(vev+graphvi+1vej)vej=vev+
4、graphvi+1;stack2.push(v);int vl=new intgraph.length; /事件的最迟生时间for(i=0; i vlgraph.length-1=vegraph.length-1;while(stack2.empty()!=true)v=(Integer)stack2.pop();for(i=1; i j=graphvi;if(vlj-graphvi+1VLV) vlv=vlj-graphvi+1;for(v=0; v for(i=1; i j=graphvi;if(vev=(vlj-graphvi+1)int p=v, j,graphvi+1,;pathlen+=p0;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