路径排序计算法

① 关键路径怎么算

输入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)的为关键活动。

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

(1)路径排序计算法扩展阅读

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

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

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

② 路径分析的最优路径分析方法

1．道路预处理
进行道路数据录入时，往往在道路的交叉接合处出现重叠或相离的情况，不宜计算机处理。因此，需要对原始数据进行预处理，使道路接合符合处理要求。进行预处理时，取每条线段的首末节点坐标为圆心，以给定的阈值为半径作圆域，判断其他线段是否与圆域相交，如果相交，则相交的各个线对象共用一个节点号。
2．道路自动断链
对道路进行预处理之后即可获得比较理想的数据，在此基础上再进行道路的自动断链。步骤如下：
（1）取出所有线段记录数n，从第一条线段开始；
（2）找出所有与之相交的线段并求出交点数m；
（3）将m个交点和该线段节点在判断无重合后进行排序；
（4）根据交点数量，该线段被分成m+1段；
（5）第一段在原始位置不变，后m段从记录尾开始递增；
（6）重复（2）～（5），循环至n。
3．节点匹配
拓扑关系需使用统一的节点。节点匹配方法是按记录顺序将所有线段的始末点加上相应节点号，坐标相同的节点共用一个节点号，与前面所有线段首末点都不相同的节点按自然顺序递增1。
4．迪杰克斯特拉（Dijkstra）算法
经典的图论与计算机算法的有效结合，使得新的最短路径算法不断涌现。目前提出的最短路径算法中，使用最多、计算速度比较快，又比较适合于计算两点之间的最短路径问题的数学模型就是经典的Dijkstra算法。
该算法是典型的单源最短路径算法，由Dijkstra EW于1959年提出，适用于所有弧的权均为非负的情况，主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。该算法的基本思想是：认为两节点间最佳路径要么是直接相连，要么是通过其他已找到的与起始点的最佳路径的节点中转点。定出起始点P0后，定能找出一个与之直接相连且路径长度最短的节点，设为P1，P0到P1就是它们间的最佳路径。
Dijkstra算法的基本流程如下：首先将网络中所有节点分成两组，一组包含了已经确定属于最短路径中点的集合，记为S（该集合在初始状态只有一个源节点，以后每求得一条最短路径，就将其加入到集合S中，直到全部顶点都加入到S中，算法就结束了）；另一组是尚未确定最短路径的节点的集合，记为V，按照最短路径长度递增的次序依次把第二组的顶点加入到第一组中，在加入的过程中总保持从源点到S中各顶点的最短路径长度不大于从源点到V中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点距离就是从源点到此顶点的最短路径长度，V中的顶点距离是从源点到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

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

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

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

④ 关键路径怎么算

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

（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)的为关键活动。

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

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

(4)路径排序计算法扩展阅读：

一、拓扑排序的执行

由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)。

⑤ 高中数学,排列组合：一个网格9×4,从A点到B点共有多少条路径用排列组合的方法

我是这样理解的，你可以看看对不对：从A到B必须要向右走9步，向左走4步。所以总共有的方法数就是从一共走的9+4=13步中选4步来向下走，即就是4C13=715

⑥ excel怎么统计路径

=PERMUT(28,2)
排列就是这个公式
计算结果756
---------------------
图表形式表示？排列是有顺序的，图要怎么显示呢？你模拟个图来看看