关键路径算法java

① 关键路径怎么算

关键路径的计算方法如下：

（1） 输入e条弧<j,k>，建立AOE网的存储结构；

（2） 从源点v1出发，令ve(1)=0，求 ve(j) ,2<=j<=n；

（3） 从汇点vn出发，令vl(n)=ve(n)，求 vl(i), 1<=i<=n-1；

（4） 根据各顶点的ve和vl值，求每条弧s（活动）的最早开始时间e(s)和最晚开始时间l(s)，其中e(s)=l(s)的为关键活动。

求关键路径是在拓扑排序的前提下进行的，不能进行拓扑排序，自然也不能求关键路径。

关键路径是指设计中从输入到输出经过的延时最长的逻辑路径。优化关键路径是一种提高设计工作速度的有效方法。一般地，从输入到输出的延时取决于信号所经过的延时最大路径，而与其他延时小的路径无关。

(1)关键路径算法java扩展阅读：

一、拓扑排序的执行

由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。

（1）选择一个入度为0的顶点并输出之；

（2）从网中删除此顶点及所有出边。

循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。

二、关键路径相关术语

（1）AOE网

用顶点表示事件，弧表示活动，弧上的权值表示活动持续的时间的有向图叫AOE网。在建筑学中也称为关键路线。AOE网常用于估算工程完成时间。一个AOE网的关键路径可以不止一条。

只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。只有在进入某一顶点的各有向边所代表的活动都已经结束，该顶点所代表的事件才能发生。

表示实际工程计划的AOE网应该是无环的，并且存在唯一的入度为0的开始顶点和唯一的出度为0的完成顶点。

（2） 活动开始的最早时间e(i)；

（3） 活动开始的最晚时间l(i)；

（4） 事件开始的最早时间ve(i)；

（5） 事件开始的最晚时间vl(i)。

② 关键路径怎么求求详解。

关键路径的算法是建立在拓扑排序的基础之上的，这个算法中用到了拓扑排序。

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天。

packagegraph;
importjava.util.*;
publicclassGrph_CriticalPath
{
Graph_AdjListadjList;
Stack<Integer>T=newStack<Integer>();
intve[];
intvl[];
finalintmax=10000;

publicGrph_CriticalPath(Graph_AdjListadjList)//图的存储结构是用的邻接表
{
this.adjList=adjList;
intlength=adjList.vetexValue.length;
ve=newint[length];
vl=newint[length];
for(inti=0;i<length;i++)
{
ve[i]=0;
vl[i]=max;
}
}

publicvoidgetCriticalPath()
{
topologicalOrder();

intt=T.pop();
T.push(t);
vl[t]=ve[t];
while(!T.isEmpty())
{
intj=T.pop();
for(Graph_AdjList.ArcNodep=adjList.vetex[j].firstArc;p!=null;p=p.next)
{
intk=p.adjvex;
if(vl[k]-p.weight<vl[j])
{
vl[j]=vl[k]-p.weight;
}
}
}
for(inti=0;i<ve.length;i++)
{
for(Graph_AdjList.ArcNodep=adjList.vetex[i].firstArc;p!=null;p=p.next)
{
intk=p.adjvex;
intee=ve[i];
intel=vl[k]-p.weight;
if(ee==el)
{
System.out.print(i+","+k+"");
}

}
}
}

publicvoidtopologicalOrder()
{
Stack<Integer>S=newStack<Integer>();
S.push(0);
intcount=0;
while(!S.isEmpty())
{
intj=S.pop();
T.push(j);
count++;
Graph_AdjList.ArcNodep=null;
for(p=adjList.vetex[j].firstArc;p!=null;p=p.next)
{
intk=p.adjvex;
if(--adjList.degree[k]==0)
{
S.push(k);
}
if(ve[j]+p.weight>ve[k])
{
ve[k]=ve[j]+p.weight;
}
}
}
if(count<adjList.vetexValue.length)
{
System.out.println("图中存在环路！");
return;
}
}

publicvoidprint()
{
while(!T.isEmpty())
{
System.out.print(T.pop()+"");
}
}

publicvoidprintVel()
{
System.out.println();
for(inti=0;i<ve.length;i++)
{
System.out.print(ve[i]+"");
}
System.out.println();
for(inti=0;i<vl.length;i++)
{
System.out.print(vl[i]+"");
}
}


}

转自：http://blog.csdn.net/pigli/article/details/5777048

③ 关键路径怎么算

输入e条弧<j，k>，建立AOE网的存储结构；从源点v1出发，令ve(1)=0，求 ve(j)，2<=j<=n；从汇点vn出发，令vl(n)=ve(n)，求 vl(i)，1<=i<=n-1。

根据各顶点的ve和vl值，求每条弧s（活动）的最早开始时间e(s)和最晚开始时间l(s)，其中e(s)=l(s)的为关键活动。

求关键路径必须在拓扑排序的前提下进行，有环图不能求关键路径；只有缩短关键活动的工期才有可能缩短工期；若一个关键活动不在所有的关键路径上，减少它并不能减少工期；只有在不改变关键路径的前提下，缩短关键活动才能缩短整个工期。

(3)关键路径算法java扩展阅读

在项目管理中，编制网络计划的基本思想就是在一个庞大的网络图中找出关键路径，并对各关键活动，优先安排资源，挖掘潜力，采取相应措施，尽量压缩需要的时间。

而对非关键路径的各个活动，只要在不影响工程完工时间的条件下，抽出适当的人力、物力和财力等资源，用在关键路径上，以达到缩短工程工期，合理利用资源等目的。在执行计划过程中，可以明确工作重点，对各个关键活动加以有效控制和调度。

关键路径法主要为一种基于单点时间估计、有严格次序的一种网络图。它的出现为项目提供了重要的帮助，特别是为项目及其主要活动提供了图形化的显示，这些量化信息为识别潜在的项目延迟风险提供极其重要的依据。

④ 关键路径算法的时间复杂度

所谓关键路径，就是从工程开始到工程结束所用时间最长的路径。这是因为，在途中的每一个阶段开始之前，都要保证此前的准备工作都已完成，要不然后续工程会无法完成，在寻找路径时，只能一条路径一条路径的比较。本题结果是

⑤ 关键路径法的公式计算

上面介绍了活动的最早和最迟时间的计算方法，以上的过程可以用比较简单的公式来表达。 上面所讲述的方法，我们一般称为节点计算法，节点和活动的最早时间按照正推法进行计算，起点节点未规定时间时，我们取其时间为1，即
ETi=1（i=1）
对于任意一个节点，如果其之前只有一条活动时，则其最早时间按照下式计算，
ETj= ETi+Di-j
如果该节点之前有多条活动时，则其最早时间按照下式计算，ETj= max{ETi+Di-j}
其中Di-j为活动i-j的工期
对于活动的最早时间，最早开始时间为：
ESi-j=ETi
最早结束时间为
EFi-j= ESi-j+ Di-j
计划的总工期
T=ETn-1
节点和活动的最迟时间以逆推法计算，计算时，首先令最后一个节点的最迟时间等于其最早时间，即
LTn=ETn
对于其之后只有一条活动的节点，最迟时间如下式所示
LTi=LTj-Di-j
对于其之后有多条活动的节点，最迟时间如下式所示
LTj=min{ LTj-Di-j}
工作i-j的最迟完成时间以下式计算，
LFi-j=LTj
最迟开始时间为
LSi-j=LFj- Di-j 以上的算法是节点计算法，另外，也可以采用一种叫做工作计算法的方法进行活动时间的计算，具体如下。
对于最早时间，采用正推法计算。在没有指定节点的开始时间时，则起点开始活动的最早开始时间定为1，即
ESi-j=1
当工作i-j只有一条紧前工作h-i时，其最早开始时间按如下公式计算ESi-j=ESh-i+ Dh-i
当工作i-j有多条紧前工作时，其最早开始时间按照以下公式计算
ESi-j=max {ESh-j+ Dh-i}
工作i-j的最早完成时间按照下式计算
EFi-j=ESi-j+ Di-j
网络计划的计算工期按照下式确定
T=max {EFi-n}-1
活动的最迟结束时间和最迟开始时间需要采用逆推法计算。
以终点节点为箭头节点的活动的最迟完成时间按照网络计划的工期确定，即
LFi-j=T+1
其它活动的最迟开始时间按照下式计算
LFi-j=min {LFj-k- Dj-k}
活动的最迟开始时间以下式确定
LSi-j=LFi-j- Di-j
对于总时差和自由时差可以采用如下的公式计算。
总时差可以按照下式计算：
TFi-j= LSi-j- ESi-j
或者
TFi-j= LFi-j- EFi-j
当工作i-j有紧后工作j-k时，自由时差可以按照下式计算：
FFi-j=ESi-k- ESi-j- Di-j
或者
FFi-j=ESj-k-EFi-j
由于引入了多种逻辑关系，前导图（PDM）的时间计算和箭线图（ADM）有一些差别。除了前导图（PDM）中不存在节点最早时间和最迟时间，在箭线图（ADM）中提及的其它时间参数也都适合前导图（PDM）。 对于活动的最早开始和最早结束时间，采用正推法计算，其算法如下所示：
⒈将第一个活动的最早开始时间设置为1.
⒉在活动的最早开始时间上加上其工期，得到活动的最早结束时间。
⒊根据该活动与后置活动的逻辑关系，计算后置活动应该的最早开始时间，并与其已有的最早开始时间对比，如果其后置活动还没有设置最早开始时间，则将此时间设为其最早开始时间，如果此时间早于其后置活动已有的最早开始时间，则保留后置活动的原有最早开始时间，如果此时间迟于其后置活动已有的最早开始时间，则将此时间设置为后置活动的最迟开始时间。
⒋重复步骤2和3，直到所有活动的时间被计算完为止。
对于以上所示的最早时间的计算过程，可以以公式的形式表示如下：
当活动间的逻辑关系为SS，则计算如下
ESj=max{ ESi+ STS}
当活动间的逻辑关系为FS，则计算如下
ESj= max{ESi+ Di+ FTS}
当活动间的逻辑关系为FF，计算如下
ESj= max{ESi+ Di- Dj+FTF}
当活动间的逻辑关系为SF，计算如下
ESj=max{ ESi- Dj+STF}
在计算出各个活动的最早开始和结束时间之后，就可以计算活动的自由时差，在计算前导图（PDM）的自由时差时应注意，由于引入了多种逻辑关系，并且活动间可以存在延时，所以其计算方法与箭线图（ADM）的计算方法不一样。 对于前导图（PDM）的活动间，除了延时还可以存在时间间隔（LAG），一般可以按照下面的方式计算。
当活动间的逻辑关系为SS，则计算如下
LAGi-j= ESj- ESi- STS
当活动间的逻辑关系为FS，则计算如下
LAGi-j= ESj- EFi- FTS
当活动间的逻辑关系为FF，计算如下
LAGi-j= EFj- EFi- FTF
当活动间的逻辑关系为SF，计算如下
LAGi-j= EFj- ESi- STF
则对于任意一个活动，其自由时差为
FFi=min{ LAGi-j}
最后一个活动的自由时差为0.
对于总时差，终点节点的总时差为0，对于其它任意一个节点，总时差按照下式进行计算
TFi=min{TFj+ LAGi-j}
对于任意一个活动的最晚开始时间可以由其最早开始时间加上总时差得到，同样，其最晚开始时间可以由最早结束时间加上其总时差得到，公式表示如下
LSi=ESi+TFi
LFi=EFi+TFi

⑥ 题目1:一个简单的算法演示程序(JAVA语言实现)

1. 选择一个算法（提供选择见下），利用各种方法（图形、动画等）演示算法的演示过程。
2. 可以进行手动演示，也可以自动步进式演示。
3. 允许用户设置算法的各个输入参数，以及自动步进式演示中的时间间隔。
4. 不同的算法输入要求见下。
界面要求：
1. 尽量使用图形界面实现，要符合日常软件使用规范来设计菜单和界面。
2. 如果无法实现图形界面，则在命令行方式下也需要提供菜单，方便用户操作。
其他要求：
1. 标识符命名遵循Windows命名规范。
2. 能够注意各种异常处理，注重提高程序运行效率。
提交内容：
1. 全部源代码。
2. 软件设计和使用说明书（UML类图；实现的功能、主要技术；使用帮助文档）
参考算法：
1. 最小生成树算法：Prim算法、Kruskal算法。允许以下方式输入一个图形：绘制图形、输入邻接矩阵、输入边及其关联的顶点。要求在图形方式下进行演示算法执行步骤。
2. 单源最短路算法：Dijkstra算法。允许以下方式输入一个图形：绘制图形、输入邻接矩阵、输入边及其关联的顶点。要求在图形方式下进行演示算法执行步骤。
3. 最优编码算法：Huffman编码算法。允许用户输入一段英文文字，或者打开一个txt文档（英文内容），据此文档内容进行编码。要求动态列出每个字符的出现概率统计结果以及对应编码。
4. 其他可供演示的具有一定难度的算法，如关键路径问题、有向图的极大连通分支等。

⑦ 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，做为继续查找的开始位置就可以了。