Java 实现关键路径分析
Java 实现关键路径分析
Java 实现关键路径分析 K,首先声明，我是用VC的，用Java只是不得已而为之，下面的Java代码中，图和堆栈数据结构是按照java版《数据结构与算法》写的，只是修改了少数成员变量。而算法的实现，由于我对Java不是很熟悉，不了解其内涵，也许代码中会饶弯子，请不要给我指出来。本人现在对Java已经恨厮入骨，恨因1：慢的像我跑50米，恨因2：在MSDN中找不到任何答案，呵呵，要不是必须二字，我才不会用Java。不过我倒不是说Java不好,Sun不对，不过习惯了C++的new delete配对，在搞这没离头的只new不delete的java时自然感到不爽。
一 问题描述
如右图所示，假如某工程项目由0到5个事件组成，每个事件表示它之前的活动已经完成，在它之后的活动可以开始。如顶点0（用v0表示）表示整个项目的开始，因为它的入度为0；而v5的出度为0，则它表示项目的结束。
由于在这样的工程进度图中有些活动可以并行的进行，提前完成并行事件中非关键的事件是不会加快工程进度的。因此有必要知道哪些事件是影响整个项目的关键。
在上图中，事件用顶点表示，最左侧的数字代表事件的编号。右侧上端的数字表示事件的最早开始时间；而下端的数字表示该事件的最迟开始时间。连接两个事件的边代表后继事件依赖于前驱事件的完成，成为一个活动。边上标注的duti表示前后两个事件的持续时间，下方的括号中标注的数字是前后两个事件的机动时间。显然，机动时间越小，事件越关键，而机动时间为0的活动则是整个项目中的关键活动，由它们连接起来的事件顶点组成的图叫做原有向图的关键路径（Critical Path）。
上图标明的各个数字是分析后的结果，而解决问题前的已知参数有：
事件的个数（用顶点表示）和哪些事件之间有活动（用连接顶点的边表示）
活动的持续时间（用dut表示）
显然，起始事件间的最早开始时间是0。关键路径分析问题就是利用以上参数解出新的有向图的问题。
二、 算法思想
由问题描述已经可以清楚的知道寻找关键路径首先需要得到活动的机动时间。机动时间可以按照以下公式获得：
Vj到Vk的机动时间＝Vk的最迟开始时间－Vj的最早开始时间－活动的持续时间dut
也就是说，只要知道了每个事件的最早和最迟开始时间，就可以算出活动的机动时间（活动的持续时间是已知的）。
因此问题转化为计算最早时间和最迟时间。按照图中所示，事件V2的最早开始时间等于活动2的持续时间dut2加上事件V1的最早开始时间，即0+2=2。同样的情况还适合于V1和V4。而对于V3和V5，它们的开始依赖于多个事件的完成，所以它们的最早开始时间应该是依赖事件最早开始时间与活动持续时间之和最大的那个。例如事件V3，它的完成依赖于V1和V2的完成，如果做完V0后先做V2，则V3的最早开始时间为2+4=6；如果做完V0后先做V1，则V3的最早开始时间是3+2=5，所以V3的最早开始时间应该是6，这样才能保证V1和V2都能完成。所以，计算事件Vj的最早开始事件的公式为： Vj的最早开始时间＝MAX{Vi的最早开始时间+从i到j的所有活动的持续时间之和}
其中<i,j>属于所有以顶点j为头的活动集合，而j=1,2,...n-1，n是事件个数。
对于事件的最迟开始时间，则应该从终止事件（V5）向前推算。以活动8为例，显然V5的最终止事件和最早开始时间是相等的，所以V4的最迟开始时间应该是8-dut8=7。对于出度大于1的时间，按照计算最早开始时间的经验，它们的最迟开始时间应该是所有后继顶点最迟开始时间减去活动持续时间后最小的哪个，它的计算公式为：
Vi的最迟开始时间＝Min{Vj的最迟开始时间－从i到j的所有活动的持续时间之和}
其中<i,j>属于所有以顶点i为尾的活动集合，而i=n-2,...0,n是事件个数。
由此得出以下求关键路径的算法思想：
1. 首先建立有向图，输入活动的持续时间。要求该有向图只有一个入度为0的顶点并且只有一个出度为0的顶点。（分别作为项目的起始事件和终止事件）
2. 从起点V0出发，令V0的最早开始时间为0，利用拓扑排序算法求出其余各顶点的最早发生时间。
3. 从终点V5出发，令V5的最迟开始时间等于其最早开始时间，利用逆拓扑排序算出其余各顶点的最迟开始时间。
4. 按照计算机动时间的公式，计算各活动的机动时间，如果机动时间为0，则该活动和活动的两个顶点组成关键路径的一部分，依次2找到其余部分则问题解决。
三 图和堆栈数据结构
这是java版《数据结构与算法》给出的数据结构，不是我写的（只作了少数修改）。看了这个数据结构，我对java接口有了较深刻的认识。
图接口Graph.java
/* * @(#)Graph.java * * 实现通用图结构的Interface * * 王悦 (K!按java的风格写注释真xx的累) */import java.awt.Color;interface Graph { public int numberOfVertices(); //返回顶点个数 public int numberOfEdges(); //返回边的个数 public Edge firstEdgeOfVertex(int v);//返回顶点的第一个边 public Edge nextEdgeOfVertex(Edge e); //返回顶点的下一个边 public boolean isEdge(Edge e); //e是边返回true public boolean isEdge(int i, int j); //e是边返回true public int v1Edge(Edge e); //返回边的起始顶点 public int v2Edge(Edge e); //返回边的终止顶点 public void setEdgeWeight(int i, int j, int weight); //设置边的权 public void setEdgeWeight(Edge e, int weight); //设置边的权 public int getEdgeWeight(int i, int j); //取得边的权 public int getEdgeWeight(Edge e); //取得边的权 public void setMark(int v, int val); //设置顶点标记 public int getMark(int v); //取出顶点标记 public void setVertLocation(int v, int x, int y); //设置顶点坐标 public int getVertX(int v); //获得顶点横坐标 public int getVertY(int v); //获得顶点纵坐标 public void delEdge(Edge e); //删除边 public void delEdge(int i, int j); //删除边 public boolean isCriticalEdge(int v1,int v2); //返回边是否为关键路径 public void setCriticalEdge(int v1,int v2,boolean b); //设置边为关键路径}
图接口的邻接矩阵实现Graphm.java
/*
* @(#)Graphm.java
*
* 通用图结构的邻接矩阵实现
*
* 王悦 02/03/31
*
*/
class Graphm implements Graph
{
private int[][] matrix; //边数组matrix[i][j]表示连接顶点i,j的边
private int numEdge; //边的个数
private int[] Mark; //标记数组
private boolean[][] CriticalEdge; //标记便是否为关键路径
//以下成员用于Applet绘图显示
private int [] X; //行坐标
private int [] Y; //列坐标
public Graphm(int n)
{
//构造函数,建立一个有n个顶点的图
X=new int[n];
Y=new int[n];
Mark=new int[n];
matrix=new int[n][n];
CriticalEdge=new boolean[n][n];
numEdge=0; //最初没有任何边
}
public boolean isCriticalEdge(int v1,int v2)
{
return CriticalEdge[v1][v2];
}
public void setCriticalEdge(int v1,int v2,boolean b)
{
CriticalEdge[v1][v2]=b;
}
public int numberOfVertices()
{
return Mark.length; //顶点数目即Mark数组的长度
}
public int numberOfEdges()
{
return numEdge;
}
public Edge firstEdgeOfVertex(int v)
{
for(int i=0;i<Mark.length;i++)
if(matrix[v][i]!=0)
return new Edgem(v,i);
return null;
}
public Edge nextEdgeOfVertex(Edge e)
{
if(e==null)
return null;
for(int i=e.getV2()+1;i<Mark.length;i++)
if(matrix[e.getV1()][i]!=0)
return new Edgem(e.getV1(),i);
return null;
}
public boolean isEdge(Edge e)
{
if(e==null)
return false;
else
return matrix[e.getV1()][e.getV2()]!=0;
}
public boolean isEdge(int i, int j)
{
return matrix[i][j]!=0;
}
public int v1Edge(Edge e)
{
return e.getV1();
}
public int v2Edge(Edge e)
{
return e.getV2();
}
public void setEdgeWeight(int i, int j, int weight)
{
//本函数连接顶点i,j，然后设置权
//weight不得为0
matrix[i][j]=weight;
numEdge++; //因为是新的边，所以增加边的个数
}
public void setEdgeWeight(Edge e, int weight)
{
//本函数设置现存边的权,但是改边尚未加入数组matrix
//weight不得为0
if(e!=null)
setEdgeWeight(e.getV1(),e.getV2(),weight);
}
public int getEdgeWeight(int i, int j)
{
if(matrix[i][j]==0)
return Integer.MAX_VALUE;
else
return matrix[i][j];
}
public int getEdgeWeight(Edge e)
{
if(matrix[e.getV1()][e.getV2()]==0)
return Integer.MAX_VALUE;
else
return matrix[e.getV1()][e.getV2()];
}
public void setMark(int v, int val)
{
Mark[v]=val;
}
public int getMark(int v)
{
return Mark[v];
}
public void delEdge(Edge e)
{
if(e!=null)
if(matrix[e.getV1()][e.getV2()]!=0)
{
matrix[e.getV1()][e.getV2()]=0;
CriticalEdge[e.getV1()][e.getV2()]=false;
numEdge--;
}
}
public void delEdge(int i, int j)
{
if(matrix[i][j]!=0)
{
matrix[i][j]=0;
CriticalEdge[i][j]=false;
numEdge--;
}
}
public void setVertLocation(int v, int x, int y)
{
X[v]=x;
Y[v]=y;
}
public int getVertX(int v)
{
return X[v];
}
public int getVertY(int v)
{
return Y[v];
}
}
边接口Edge.java /** @(#)Edge.java ** 边的Interface类，由graph调用* **/interface Edge{ public int getV1(); //返回边的起始顶点 public int getV2(); //返回边的终止顶点}
边接口的实现Edgem.java
/*
* @(#)Edgem.java
*
* 边的实现类
*
* 王悦 02/03/31
*
*/
class Edgem implements Edge
{
private int vert1,vert2; //边的两个顶点
public Edgem(int vt1,int vt2)
{
//构造函数
vert1=vt1;
vert2=vt2;
}
public int getV1()
{
//返回起始顶点
return vert1;
}
public int getV2()
{
//返回终止顶点
return vert2;
}
}
堆栈接口Stack.java
/* * @(#)Stack.java * * 堆栈的Interface类 * 王悦 */interface Stack { public void setup(int sz); //初始化堆栈 public void clear(); //清空 public void push(int obj); //obj入栈 public int pop(); //弹出一个obj public boolean isEmpty(); //返回是否栈空}
堆栈接口的顺序站（Array Stack）实现Stack.java
/*
* @(#)AStack.java
*
* 堆栈的实现类 采用顺序栈(Array)方式
*
* 王悦 02/03/31
*
*/
class AStack implements Stack
{
private static final int defaultSize=10; //默认栈长
private int size; //当前栈的长度
private int top; //栈顶位置
private int[] listarray; //对象数组
AStack()
{
//默认构造函数
setup(defaultSize);
}
AStack(int sz)
{
//构造函数
setup(sz);
}
public void setup(int sz)
{
size=sz;
top=0;
listarray=new int[sz];
}
public void clear()
{
top=0;
}
public void push(int obj)
{
listarray[top++]=obj;
}
public int pop()
{
return listarray[--top];
}
public boolean isEmpty()
{
return top==0;
}
}
四 核心算法
重要成员变量：
1 AStack m_stackZero, m_stackTop;
其中AStack是顺序式堆栈(Array Stack)结构，m_stackZero和m_stackTop分别存放入度为0的顶点和拓扑排序后的顶点。
2 int m_nVertCount;
用来表示顶点个数，尽管顶点个数在最初就已经固定，但是使用变量存放顶点个数有利于程序修改
3 int[] m_ve;
事件的最早发生时间，是长度为m_nVertCount的数组，每个顶点分配一个
4 int[] m_vl;
事件最迟发生时间
5 boolean[] m_bCritical;
每个顶点分配一个,如果发现顶点位于关键路径上则置为真
6 Graphm m_Graph;
图结构，为配合关键路径分析，在图结构类中还添加了setCriticalEdge和isCriticalEdge函数，前者设置指定边为关键路径上的活动，后者判断给定边是否为关键路径上的活动。
重要函数：
public void init() {
//建立图结构 m_nVertCount=6; //顶点个数为6: v0-v5 m_bCritical=new boolean[m_nVertCount]; m_Graph=new Graphm(m_nVertCount); //两个堆栈最多放m_nVertCount个顶点 m_stackZero=new AStack(m_nVertCount); m_stackTop=new AStack(m_nVertCount); //建立事件的最早最迟发生时间数组 m_ve=new int[m_nVertCount]; m_vl=new int[m_nVertCount]; //初始化各顶点在屏幕上的位置 m_Graph.setVertLocation(0,40,120); m_Graph.setVertLocation(1,140,40); m_Graph.setVertLocation(2,140,200); m_Graph.setVertLocation(3,240,120); m_Graph.setVertLocation(4,340,40); m_Graph.setVertLocation(5,440,120); //调用初始化控件位置和初始值的函数(略) setLayout(); //重新设置活动持续时间 resetDut();}
public void resetDut(){ //初始化堆栈 m_stackTop.clear(); m_stackZero.clear() //把唯一一个入度是0的顶点0进栈 m_stackZero.push(0); for(int v1=0; v1< m_nVertCount;v1++) { //删除所有的边 for(int v2=0; v2>m_nVertCount; v2++) { m_Graph.delEdge(v1,v2); } //顶点都不在关键路径上 m_bCritical[v1]=false; } //重新设置持续时间 m_Graph.setEdgeWeight(0,1,Integer.parseInt(m_txtDut[0].getText())); m_Graph.setEdgeWeight(0,2,Integer.parseInt(m_txtDut[1].getText())); m_Graph.setEdgeWeight(1,3,Integer.parseInt(m_txtDut[2].getText())); m_Graph.setEdgeWeight(1,4,Integer.parseInt(m_txtDut[3].getText())); m_Graph.setEdgeWeight(2,3,Integer.parseInt(m_txtDut[4].getText())); m_Graph.setEdgeWeight(2,5,Integer.parseInt(m_txtDut[5].getText())); m_Graph.setEdgeWeight(3,5,Integer.parseInt(m_txtDut[6].getText())); m_Graph.setEdgeWeight(4,5,Integer.parseInt(m_txtDut[7].getText())); //设置个顶点的Mask: 入度 m_Graph.setMark(0,0); m_Graph.setMark(1,1); m_Graph.setMark(2,1); m_Graph.setMark(3,2); m_Graph.setMark(4,1); m_Graph.setMark(5,3);}
public void topLogicalOrder(){ //对图的各个顶点进行拓扑排序 m_stackTop.clear();//结果存在m_stackTop栈中 for(int i=0;i< m_nVertCount;i++) m_ve[i]=-1; //初始化顶点的最早发生时间为无穷小 m_ve[0]=0; //起始顶点是最早时间是0 int v1,v2; //临时顶点 while(m_stackZero.isEmpty()==false) { v1=m_stackZero.pop(); m_stackTop.push(v1); for(Edge e=m_Graph.firstEdgeOfVertex(v1);m_Graph.isEdge(e); e=m_Graph.nextEdgeOfVertex(e)) { v2=e.getV2(); m_Graph.setMark(v2,m_Graph.getMark(v2)-1);//对顶点v2的入度减1 if(m_Graph.getMark(v2)==0) m_stackZero.push(v2); //如果入度减为0则入栈 if(m_ve[v1]+m_Graph.getEdgeWeight(e)>m_ve[v2]) m_ve[v2]=m_ve[v1]+m_Graph.getEdgeWeight(e); } }}
public void actionPerformed(ActionEvent event){ if (event.getSource()==m_btnStart) { resetDut(); m_btnStart.setEnabled( false ); topLogicalOrder(); //对每个顶点的最早开始时间排序 for(int i=0;i< m_nVertCount;i++) m_vl[i]=99; //初始化顶点的最迟发生时间为无穷大 //终止顶点的最迟发生时间==最早发生时间 m_vl[m_nVertCount-1]=m_ve[m_nVertCount-1]; //按照Top栈计算最迟时间 int v1,v2; Edge e; String strResult="CriticalPath "; while(m_stackTop.isEmpty()==false) { v1=m_stackTop.pop(); for(e=m_Graph.firstEdgeOfVertex(v1);m_Graph.isEdge(e); e=m_Graph.nextEdgeOfVertex(e)) { v2=e.getV2(); if(m_vl[v2]-m_Graph.getEdgeWeight(e)< m_vl[v1]) m_vl[v1]=m_vl[v2]-m_Graph.getEdgeWeight(e); }//for }//while //求关键活动 for(v1=0;v1< m_nVertCount;v1++) { for(e=m_Graph.firstEdgeOfVertex(v1);m_Graph.isEdge(e); e=m_Graph.nextEdgeOfVertex(e)) { v2=e.getV2(); if(m_vl[v2]-m_ve[v1]-m_Graph.getEdgeWeight(e)==0)//如果机动时间为0 { strResult+="- < V"+v1+",V"+v2+" >"; m_lblResult.setText(strResult); m_bCritical[v1]=true; m_bCritical[v2]=true; m_Graph.setCriticalEdge(v1,v2,true); } }//for }//for m_btnStart.setEnabled(true); repaint(); }//if (e.getSource()==m_btnStart)}
五 完整代码出去四中的几个核心算法，还需以下函数，编译后（包括图实现、边实现、堆栈实现和关键路径程序）即可
以Applet的方式实现演示。输入不同持续时间后，可用蓝色标记处不同的关键路径。
/*
* @(#)CriticalPath.java
*
* 关键路径分析程序
*
* 王悦 02/03/31
*
*/
import java.awt.*;
import java.applet.*;
import java.awt.event.*;
public class CriticalPath extends Applet implements ActionListener
{
//建立m_stackZero存放Top排序时使用的0入度顶点站
//m_stackTop为Top排序顶点站，用于在分析关键路径
//时建立逆顺序Top排序
private AStack m_stackZero, m_stackTop;
private int m_nVertCount;//顶点个数
private int[] m_ve; //事件(顶点)的最早发生时间
private int[] m_vl; //事件(顶点)的最迟发生时间
private boolean[] m_bCritical; //顶点位于关键路径上
private Graphm m_Graph; //图结构
//
private Button m_btnStart;//开始按钮
private Label m_lblResult, m_lblSetDut;//显示结果和显示设置Dut提示
private Label[] m_lblDut; //共8个事件，分别显示事件名称
private TextField[] m_txtDut; //用户输入的8个事件持续时间
public void resetDut()
{
//略，见四
}
public void setLayout()
{
setLayout( null );
m_btnStart = new Button( "Start" );
m_btnStart.setBounds(400, 370, 80, 25);
m_btnStart.addActionListener(this);
add(m_btnStart);
m_lblResult = new Label("Hello World");
m_lblResult.setBounds(10, 395, 380, 25);
add(m_lblResult);
m_lblSetDut = new Label( "Please input dut of each event:" );
m_lblSetDut.setBounds(10, 310, 200, 25);
add(m_lblSetDut);
m_lblDut = new Label[8]; //共8个事件
m_txtDut = new TextField[8];
//第一行的Label和TextBox
int dut;
for(int i=0;i<4;i++)
{
dut=i+1;
m_lblDut[i]=new Label();
m_lblDut[i].setBounds(10+78*i,340,35, 25);
add(m_lblDut[i]);
m_lblDut[i].setText("Dut"+ dut +":");
m_txtDut[i]=new TextField();
m_txtDut[i].setBounds(48+78*i,340,35, 25);
add(m_txtDut[i]);
}
//第二行的Label和TextBox
for(int i=0;i<4;i++)
{
dut=i+5;
m_lblDut[i+4]=new Label();
m_lblDut[i+4].setBounds(10+78*i,370,35, 25);
add(m_lblDut[i+4]);
m_lblDut[i+4].setText("Dut"+ dut +":");
m_txtDut[i+4]=new TextField();
m_txtDut[i+4].setBounds(48+78*i,370,35, 25);
add(m_txtDut[i+4]);
}
//设置各事件默认持续时间
m_txtDut[0].setText("3");
m_txtDut[1].setText("2");
m_txtDut[2].setText("2");
m_txtDut[3].setText("3");
m_txtDut[4].setText("4");
m_txtDut[5].setText("3");
m_txtDut[6].setText("2");
m_txtDut[7].setText("1");
}
public void init()
{
//略，见四
}
public void topLogicalOrder()
{
//略，见四
}
public void paint(Graphics g)
{
int x,y;
//先绘制边
for(int v1=0;v1<m_nVertCount;v1++)
{
for(int v2=0;v2<m_nVertCount;v2++)
{
if(m_Graph.isEdge(v1,v2))
{
//存在边看边是否连接了两个位于关键路径上的顶点
if(m_Graph.isCriticalEdge(v1,v2))
g.setColor(Color.BLUE); //关键路径为蓝色
else
g.setColor(Color.BLACK);
g.drawLine(m_Graph.getVertX(v1)+25,m_Graph.getVertY(v1)+25,m_Graph.getVertX(v2)+25,m_Graph.getVertY(v2)+25);
}
}
}
//再绘制顶点，以遮住顶点内部的边
for(int i=0;i<m_nVertCount;i++)
{
x=m_Graph.getVertX(i);
y=m_Graph.getVertY(i);
g.setColor(m_bCritical[i]?Color.BLUE:Color.WHITE);
g.fillOval(x,y,50,50);
g.setColor(m_bCritical[i]?Color.WHITE:Color.BLACK);
g.drawOval(x,y,50,50);
g.drawLine(x+25,y,x+25,y+50);
g.drawLine(x+25,y+25,x+50,y+25);
g.drawString(Integer.toString(i),x+5,y+29);
g.drawString(Integer.toString(m_ve[i]),x+28,y+20);
g.drawString(Integer.toString(m_vl[i]),x+28,y+42);
}
//绘制持续时间
g.setColor(Color.BLACK);
g.drawString("dut1=" + m_txtDut[0].getText(),72,108);
g.drawString("dut2=" + m_txtDut[1].getText(),105,177);
g.drawString("dut3=" + m_txtDut[2].getText(),218,106);
g.drawString("dut4=" + m_txtDut[3].getText(),240,62);
g.drawString("dut5=" + m_txtDut[4].getText(),172,191);
g.drawString("dut6=" + m_txtDut[5].getText(),258,190);
g.drawString("dut7=" + m_txtDut[6].getText(),336,142);
g.drawString("dut8=" + m_txtDut[7].getText(),416,102);
}
public void actionPerformed(ActionEvent event)
{
//略，见四
}
}
K,完成，高兴ing...
