正文
关键路径算法java代码 关键路径的求解
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
有个JAVA问题需要解答
关键路径算法(critical path method,CPM)是一种网络分析技术，它在项目网络图的基础上，从规定的开始日期开始，利用从左到右的正向推导法计算出网络图中每个活动的最早开始和最早结束日期，再从规定的完成日期(通常是正向计算得到的最早完成日期)开始，利用从右到左的逆向推导法计算出网络图中每个活动的最晚结束和最晚开始日期，通过比较网络图中每个活动的最早开始、最早结束和最晚开始、最晚结束日期，确定各个活动的时差情况，如果某条线路上所有活动的时差都为零，该条路径即为关键路径，而时差不为零的路径称为非关键路径。
相关问答
Q1: 关键路径怎么求？求详解。
关键路径的算法是建立在拓扑排序的基础之上的，这个算法中用到关键路径算法java代码了拓扑排序。
1． 什么是拓扑排序？
举个例子先：一个软件专业的学生学习一系列的课程，其中一些课程必须再学完它的基础的先修课程才能开始。如：在《程序设计基础》和《离散数学》学完之前就不能开始学习《数据结构》。这些先决条件定义了课程之间的领先(优先)关系。这个关系可以用有向图更清楚地表示。图中顶点表示课程，有向边表示先决条件。若课程i是课程j的先决条件，则图中有弧i,j。若要对这个图中的顶点所表示的课程进行拓扑排序的话，那么排序后得到的序列，必须是按照先后关系进行排序，具有领先关系的课程必然排在以它为基础的课程之前，若上例中的《程序设计基础》和《离散数学》必须排在《数据结构》之前。进行了拓扑排序之后的序列，称之为拓扑序列。
2． 如何实现拓扑排序？
很简单，两个步骤：
1． 在有向图中选一个没有前驱的顶点且输出。
2． 从图中删除该顶点和以它为尾的弧。
重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。后一种情况则说明有向图中存在环。
3． 什么是关键路径？
例子开头仍然，图1是一个假想的有11项活动的A0E-网。其中有9个事件v1,v2......，v9，每个事件表示在它之前的活动一完成，在它之后的活动可以开始。如v1表示整个工程的开始，v9表示整个工程结束，v5表示a4和a5已完成，a7和a8可以开始。与每个活动相联系的数是执行该活动所需的时间。比如，活动a1需要6天，a2需要4天。
由于整个工程只有一个开始点和一个完成点，故在正常情况(无环)下，网中只有一个入度为零的点(称作源点)和一个出度为零的点(叫做汇点)。
那么该工程待研究的问题是：1.完成整项工程至少需要多少时间？2.哪些活动是影响工程进度的关键？
由于在AOE-网中有些活动可以并行进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度(这里所说的路径长度是指路径上各活动持续时间之和，不是路径上弧的数目)。路径长度最长的路径叫做关键路径(Critical path)。
假设开始点是v1，从v1到vi的最长路径叫做时间vi的最早发生时间。这个时间决定了所有以vi为尾的弧所表示的活动的最早开始时间。我们用e(i)表示活动ai的最早开始时间。还可以定义一个活动开始的最迟时间l(i)，这是在不推迟整个工程完成的前提下，活动ai最迟必须开始进行的时间。两者之差l(i)-e(i)意味着完成活动ai的时间余量。当这个时间余量等于0的时候，也即是l(i)=e(i)的活动，我们称其为关键活动。显然，关键路径上的所有活动都是关键活动，因此提前完成非关键活动并不能加快工程的进度。
因此，分析关键路径的目的是辨别哪些是关键活动，以便争取提高关键活动的功效，缩短整个工期。
4． 如何实现关键路径？
由上面的分析可知，辨别关键活动就是要找e(i)=l(i)的活动。为了求得e(i)和l(i)，首先应求得事件的最早发生时间ve(j)和最迟发生时间vl(j)。如果活动ai由弧j,k表示，其持续时间记为dut(j,k)，则有如下关系
e(i) = ve(j)
l(i) = vl(k) - dut(j,k)
求解ve(j)和vl(j)需分两个步进行：
1） 从ve(0)=0开始向前推进求得ve(j)
Ve(j) = Max{ve(i) + dut(i,j) };i,j属于T，j=1,2...,n-1
其中T是所有以第j个顶点为头的弧的集合。
2） 从vl(n-1) = ve(n-1)起向后推进求得vl(j)
vl(i) = Min{vl(j) - dut(i,j};i,j属于S，i=n-2,...,0
其中，S是所有以第i个顶点为尾的弧的集合。
这两个递推公式的计算必须分别在拓扑有序和逆拓扑有序的前提先进行。也就是说，ve(j-1)必须在vj的所有前驱的最早发生时间求得之后才能确定，而vl(j-1)必须在Vj的所有后继的最迟发生时间求得之后才能确定。因此可以在拓扑排序的基础上计算ve(j-1)和vl(j-1)。
具体算法描述如下：
1． 输入e条弧j,k，建立AOE-网的存储结构。
2． 拓扑排序，并求得ve[]。从源点V0出发，令ve[0]=0,按拓扑有序求其余各顶点的最早发生时间ve[i]。如果得到的拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径，算法终止关键路径算法java代码；否则执行步骤3。
3． 拓扑逆序，求得vl[]。从汇点Vn出发，令vl[n-1] = ve[n-1]，按逆拓扑有序求其余各顶点的最迟发生时间vl[i]。
4． 求得关键路径。根据各顶点的ve和vl值，求每条弧s的最早开始时间e(s)和最迟开始时间l(s)。若某条弧满足条件e(s) = l(s)，则为关键活动。
为了能按逆序拓扑有序序列的顺序计算各个顶点的vl值，需记下在拓扑排序的过程中求得的拓扑有序序列，这就需要在拓扑排序算法中，增设一个栈，以记录拓扑有序序列，则在计算求得各顶点的ve值之后，从栈顶到栈底便为逆拓扑有序序列。
package graph;
import java.util.*;
public class Grph_CriticalPath
{
Graph_AdjList adjList;
StackInteger T = new StackInteger();
int ve[];
int vl[];
final int max = 10000;
public Grph_CriticalPath(Graph_AdjList adjList) //图的存储结构是用的邻接表
{
this.adjList = adjList;
int length = adjList.vetexValue.length;
ve = new int[length];
vl = new int[length];
for(int i=0;ilength;i++)
{
ve[i] = 0;
vl[i] = max;
}
}
public void getCriticalPath()
{
topologicalOrder();
int t = T.pop();
T.push(t);
vl[t] = ve[t];
while(!T.isEmpty())
{
int j = T.pop();
for(Graph_AdjList.ArcNode p = adjList.vetex[j].firstArc; p!=null ;p = p.next)
{
int k = p.adjvex;
if(vl[k]-p.weightvl[j])
{
vl[j] = vl[k]-p.weight;
}
}
}
for(int i=0;ive.length;i++)
{
for(Graph_AdjList.ArcNode p = adjList.vetex[i].firstArc; p!=null ;p = p.next)
{
int k = p.adjvex;
int ee = ve[i];
int el = vl[k]-p.weight;
if(ee==el)
{
System.out.print(i+","+k+" ");
}
}
}
}
public void topologicalOrder()
{
StackInteger S = new StackInteger();
S.push(0);
int count = 0;
while(!S.isEmpty())
{
int j = S.pop();
T.push(j);
count++;
Graph_AdjList.ArcNode p = null;
for(p = adjList.vetex[j].firstArc; p!=null ;p = p.next)
{
int k = p.adjvex;
if(--adjList.degree[k]==0)
{
S.push(k);
}
if(ve[j]+p.weightve[k])
{
ve[k] = ve[j]+p.weight;
}
}
}
if(countadjList.vetexValue.length)
{
System.out.println("图中存在环路！");
return;
}
}
public void print()
{
while(!T.isEmpty())
{
System.out.print(T.pop()+" ");
}
}
public void printVel()
{
System.out.println();
for(int i=0;ive.length;i++)
{
System.out.print(ve[i]+" ");
}
System.out.println();
for(int i=0;ivl.length;i++)
{
System.out.print(vl[i]+" ");
}
}
}
转自：
Q2: java关键字查询算法
import java.io.FileReader;
import java.io.BufferedReader;
import java.io.File;
public class search
{
//查找方法，参数，文件绝对路径，查找关键字
public static boolean search(String filepath,String key)
{
try
{
File f = new File(filepath);
FileReader fr = new FileReader(f);
BufferedReader br = new BufferedReader(fr);
String s = "";
//int i = 1;
while((s = br.readLine()) != null)
{
if(s.indexOf(key) != -1)
{
return true;
}
}
return false;
}
catch(Exception e)
{
e.printStackTrace();
return false;
}
}
public static void main(String args[])
{
System.out.println(search.search("d://t.txt","l2"));
}
}
修改了下，加两个变量，可以指出查找的位置。
import java.io.FileReader;
import java.io.BufferedReader;
import java.io.File;
public class search
{
//查找方法，参数，文件绝对路径，查找关键字
public static String search(String filepath,String key)
{
try
{
File f = new File(filepath);
FileReader fr = new FileReader(f);
BufferedReader br = new BufferedReader(fr);
String s = "";
int i = 1;
int m = 0;
while((s = br.readLine()) != null)
{
if((m = s.indexOf(key)) != -1)
{
return "第"+i+"段,第"+m+"处";
}
i++;
}
return null;
}
catch(Exception e)
{
e.printStackTrace();
return null;
}
}
public static void main(String args[])
{
System.out.println(search.search("d://t.txt","asd"));
}
}
这个，查汉字是没有问题的。
另外，你要全文检索的话，indexOf（）还有个方法，indexOf(int start,String key),指定开始查找的位置跟关键字，你查到一处后，将这个数值加1，做为继续查找的开始位置就可以了。
Q3: 一个简单的算法演示程序(JAVA语言实现)
还真敢要，别说5分了，5块钱也没人帮你做，自己想办法吧，懒鬼
Q4: 求如下有向图的关键路径以及任意两点之间的最短距离?
用CPM算法求有向图关键路径算法java代码的关键路径和用Dijkstra算法求有向图关键路径算法java代码的最短路径的C语言程序如下
#include stdio.h
#include malloc.h
#include stdlib.h
#include string.h
#define MAX 20
#define INF 32767 // 此处修改最大值
#define nLENGTH(a) (sizeof(a)/sizeof(a[0]))
#define eLENGTH(a) (sizeof(a)/sizeof(char))/(sizeof(a[0])/sizeof(char))
typedef struct _graph{
char vexs[MAX]; // 顶点集合
int vexnum; // 顶点数
int edgnum; // 边数
int matrix[MAX][MAX]; // 邻接矩阵
}Graph, *PGraph;
// 边的结构体
typedef struct _EdgeData{
char start; // 边的起点
char end; // 边的终点
int weight; // 边的权重
}EData;
//指向节点的位置
int point_node(PGraph g,char c){
for(int i=0;ig-vexnum;i++){
if(g-vexs[i]==c){
return i;
}
}
return -1;
}
PGraph create_graph(int b[][3],char a[],int n,int e){
char c1,c2; //边的2个顶点
PGraph g; //矩阵
g=(PGraph)malloc(sizeof(Graph));
//memset()第一个参数 是地址关键路径算法java代码，第二个参数是开辟空间的初始值关键路径算法java代码，第三个参数是开辟空间的大小
memset(g, 0, sizeof(Graph));
printf("顶点个数:\n");//顶点数
g-vexnum=n;
printf("%d\n",g-vexnum);
printf("边个数:\n");//边数
g-edgnum=e;
printf("%d\n",g-edgnum);
//初始化顶点
for(int j=0;jg-vexnum;j++){
g-vexs[j]=a[j];
}
for(int i=0;ig-edgnum;i++){
int p1,p2;
c1=char(b[i][0]);
c2=char(b[i][1]);
p1=point_node(g, c1);
p2=point_node(g, c2);
if (p1==-1 || p2==-1){
printf("input error: invalid edge!\n");
free(g);
continue;
}
g-matrix[p1][p2]=b[i][2];
}
for(int i=0;ig-vexnum;i++){
for(int j=0;jg-vexnum;j++){
if(g-matrix[i][j]==0)
g-matrix[i][j]=INF;
}
}
return g;
}
//关键路径的最短时间
//关键路径法（Critical Path Method，CPM）
void CPM_road(PGraph g){
int i,j;
int a[MAX]={0},b[MAX]={-10};
int max=0;//最长路径
for( i=0;ig-vexnum;i++){//列数遍历
for( j=0;jg-vexnum;j++){//行数遍历
//如果g-matrix[j][i]大于0，说明此顶点有前顶点，由前边的遍历可知，前顶点的最长路径a[j]，
//加上g-matrix[j][i]的路径就是当前a[i]的路径
if(g-matrix[j][i]!=INF g-matrix[j][i]+a[j]max){
max=g-matrix[j][i]+a[j];
a[i]=max;
}
}
max=0;
}
//显示最长路径
printf("第一个顶点到每一个顶点的最长路径:");
printf("\n");
for(i=0;ig-vexnum;i++){
printf("V%d\t",i+1);
}
printf("\n");
for(i=0;ig-vexnum;i++){
printf("%d\t",a[i]);
}
printf("\n");
printf("最后一个顶点到每个顶点的最长路径:");
for( i=g-vexnum-1;i=0;i--){ //列数遍历
for( j=g-vexnum-1;j=0;j--){ //行数遍历
//如果g-matrix[j][i]大于0，说明此顶点有前顶点，由前边的遍历可知，前顶点的最长路径a[j]，
//加上g-matrix[j][i]的路径就是当前a[i]的路径
if(g-matrix[i][j]!=INF g-matrix[i][j]+b[j]max){
max=g-matrix[i][j]+b[j];
b[i]=max;
}
}
max=0;
}
//显示最长路径
printf("\n");
for(i=0;ig-vexnum;i++){
printf("V%d\t",i+1);
}
printf("\n");
for(i=0;ig-vexnum;i++){
printf("%d\t",b[i]);
}
printf("\n");
printf("关键路径:\n");
for(i=0;ig-vexnum;i++){
if(a[i]==a[g-vexnum-1]-b[i]){
printf("V%c\t",g-vexs[i]);
}
}
printf("\n");
}
void print_shortest_path(PGraph g,int* distance,int* path,int* used,int start,int end){
// 输出最短距离并打印最短路径
int i = 0, pre, inverse_path[g-vexnum];
char s1[3],s2[3];
sprintf(s1, "V%d", (start+1));
sprintf(s2, "V%d", (end+1));
printf("从%s顶点到%s顶点的最短距离: %d\n", s1, s2, distance
关键路径算法java代码的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于关键路径的求解、关键路径算法java代码的信息别忘了在本站进行查找喔。
);inverse_path[i] = end;
pre = path
关键路径算法java代码的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于关键路径的求解、关键路径算法java代码的信息别忘了在本站进行查找喔。
;if(pre == -1){
printf("没有通路!\n");
}else{
while(pre != start){
inverse_path[++i] = pre;
pre = path[pre];
}
inverse_path[++i] = start;
printf("从%s顶点到%s顶点的最短路径:\n", s1, s2);
for(; i 0; i--){
sprintf(s1, "V%d", (inverse_path[i]+1));
printf("%s - ", s1);
}
sprintf(s1, "V%d", (inverse_path[i]+1));
printf("%s\n", s1);
}
return;
}
void shortest_path(PGraph g,int start, int end){ // 基于Dijkstra算法的最短路径函数
int distance[g-vexnum]; // 用于存放起始点到其余各点的最短距离
int path[g-vexnum]; // 用于存放起始点到其余各点最短路径的前一个顶点
int used[g-vexnum] = { 0 }; // 用于标记该顶点是否已经找到最短路径
int i, j, min_node, min_dis, pass_flag = 0;
for(i = 0; i g-vexnum; i++){
distance[i] = g-matrix[i]; // 初始化距离数组
if(g-matrix[i] INF){
path[i] = start; // 初始化路径数组
}else{
path[i] = -1;
}
}
used = 1;
path = start;
for(i = 0; i g-vexnum; i++){
min_dis = INF;
for(j = 0; j g-vexnum; j++){
if(used[j] == 0 distance[j] min_dis){
min_node = j;
min_dis = distance[j];
pass_flag++; // 标记是否存在通路
}
}
if(pass_flag != 0){
used[min_node] = 1;
for(j = 0; j g-vexnum; j++){
if(used[j] == 0){
if(g-matrix[min_node][j] INF distance[min_node] + g-matrix[min_node][j] distance[j]){
distance[j] = distance[min_node] + g-matrix[min_node][j];
path[j] = min_node;
}
}
}
}
}
print_shortest_path(g,distance, path, used, start, end);
return;
}
int main(){
int i,j;
PGraph gp;
char a[]={'1', '2', '3', '4', '5', '6', '7'};
int b[][3]={{'1', '2',3},
{'1', '3',2},
{'1', '4',6},
{'2', '4',2},
{'2', '5',4},
{'3', '4',1},
{'3', '6',3},
{'4', '5',1},
{'5', '7',3},
{'6', '7',4}};
int n=nLENGTH(a);
int e=eLENGTH(b);
gp=create_graph(b,a,n,e);
//打印邻接矩阵
printf("邻接矩阵:\n");
for (i = 0; i gp-vexnum; i++){
for (j = 0; j gp-vexnum; j++)
printf("%d ", gp-matrix[j][i]);
printf("\n");
}
CPM_road(gp);
printf("\n");
for(i=0;igp-vexnum;i++){
for(j=0;jgp-vexnum;j++){
if(i!=j)
shortest_path(gp,i, j);
}
}
return 0;
}
运行结果
关键路径算法java代码的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于关键路径的求解、关键路径算法java代码的信息别忘了在本站进行查找喔。
