【数据结构】什么的图的关键路径?关键路径相关概念?关键路径算法实现?

简介: 【数据结构】什么的图的关键路径?关键路径相关概念?关键路径算法实现?

一、什么是关键路径?


关键路径:若有向图中,各顶点表示事件,各有向边表示活动持续事件,则该图为活动边网络,简称AOE网。AOE网中的关键路径,就是完成整个网络所需的最短时间,亦最长路径,AOE网中,往往有若干项活动可以平行的进行,因此,从开始顶点到最后一个顶点的最长路径称为关键路径。


569085ba95654997a372e93332a13d18.png


1、现实问题


问题:


假设以有向图表示一个施工流图,弧上的权值表示完成该项子工程所需时间。


问:整个工程完成的最短时间?以及哪些活动将是影响整个工程如期完成的关键所在?


使用图描述上面情况:


弧表示活动


弧上的数字表示完成该项活动所需的时间。


32855a7a47344687b0e1391571dc2acc.png


二、关键路径相关概念?


1、AOE(Activity On Edge)网:若以弧表示活动,弧上的权值表示进行该项活动所需的时间,以顶点表示事件Event,称这种有向网为==边活动网络==,简称为AOE。


2、事件:是一个关于某几项活动开始或完成的断言。


指向它的弧表示的活动已经完成。


而从它出发的弧表示的活动开始进行


整个有向图也表示了活动之间的优先关系


这样的有向网也是不允许存在环的


e1a5ea6c9f4a480e91642230c8dd2e47.png


3、源点和汇点:


源点:表示工程开始事件的顶点的入度为零。


汇点:表示工程结束事件的顶点的出度为零。


一个工程AOE网应该是只有一个源点和一个汇点的有向无环图


4、关键路径和关键活动:


关键路径:由于AOE网中某些活动可以并行进行,故完成整个工程的最短时间即为从源点到汇点==最长路径的长度==,这个路径称为关键路径。


关键活动:构成关键路径的弧即为关键活动。


实例:下图工程从开始到完成需要18天


a1、a4、a8和a11四项活动必须按时开始并按时完成,否则将延误整个工程的工期,使整个工程不能在18天内完成。


于是,称a1、a4、a8和a11为AOE图的关键活动。


由a1、a4、a8和a11构成的路径称为关键路径。


5c98084698d64b169229ce7fe722ee02.png


三、关键路径算法实现?


1、算法分析


相关概念


假设顶点v0为源点,vn-1 为汇点


时间v0的发生时刻为0时刻


从v0到vi的最长路径叫做事件vi的最早发生时间


用e(i)表示==活动的最早开始时间==。(这个时间决定了所有以vi为尾的弧所表示活动的最早开始时间)


用l(i)表示==活动的最晚开始时间==。


两者之差l(i)-e(i)意味着完成活动ai的时间余量


当l(i)=e(i)时的活动成为==关键活动==。


用ve(j)表示==事件vj的最早开始时间==。


用vl(j)表示==事件vj的最晚开始时间==。


关键路径和非关键路径分析


668426c4ae00446bb9afad474ed3cb1e.png


顶点v0到v8的一条关键路径是:(v0, v1, v4, v6, v8) ,路径长度为18。


活动a6不是关键活动,它的最早开始时间为5,最晚开始时间为8,时间余量为3。也就是说a6延迟3天,并不会影响整个工程的完成。


588942030a0f440fb594653196709bf9.png


总结:


1.要缩短整个工程,必须先找到关键路径,提高关键活动的工效。


2.由于关键路径上的活动都是关键活动,所以,提前完成非关键活动并不能加快工程的进度。


2、算法步骤


1、从源点v0触发,令ve(0) = 0,按拓扑有序序列求其余各顶点的ve(j)=maxi {ve(i) + |vi, vj| } , <vi, vj> ∈ T,其中:T是所有以vj为头的弧的集合。若得到的拓扑有序序列中顶点的个数小于网中的顶点个数n,则说明网中有环,不能求出关键路径,算法结束。


2d6d18263c7f47c5b0e352c267a0644c.png


2、从汇点vn-1出发,令vl(n-1) = ve(n-1) ,按逆拓扑有序序列求其余各顶点的 vl(i)=minj {vl(j) - |vi, vj| } , <vi, vj> ∈ S,其中:S是所有以vj为尾的弧的集合。

0754a4e238ff41a88feec9b9f71767e2.png



3、求每一项活动ai(1<=i<=n)的最早开始时间e(i)=ve(j),vj是ai的起点。

d8ed1f26944741faaadd928aaf6857b7.png



4、求每一项活动ai的最晚开始时间l(i) = vl(j) - |vi, vj| , vi是ai的起点, vj是ai的终点。


e9b24648b1894d0a963be0b836304224.png


5、若对于满足e(i) = l (i) ,则它是关键活动


d4dcf341f4e44192a6fc4780d5020ae4.png


两条关键路径:


ed7af04427f04330abd90adf116aa929.png


3、算法实现

public class CriticalPath {
  private LinkStack T = new LinkStack();  // 拓扑逆序列顶点栈
  private int[] ve, vl;         // 各顶点的最早发生时间和最迟发生时间
  // 有向图G采用邻接表存储,求各顶点的最早发生时间ve,若G无回路,则用栈T返回G的一个拓扑序列,且函数返回true,否则为false
  public boolean topologicalOrder(ALGraph G) throws Exception {
    int count = 0;                    // 输出顶点计数
    int[] indegree = TopologicalSort.findInDegree(G); // 求各个顶点的入度
    LinkStack S = new LinkStack();            // 建零入度顶点栈S
    for (int i = 0; i < G.getVexNum(); i++)
      if (indegree[i] == 0)             // 入度为0者进展
        S.push(i);
    ve = new int[G.getVexNum()];            // 初始化
    while (!S.isEmpty()) {
      int j = (Integer) S.pop();
      T.push(j);                    // j号顶点入T栈并计数
      ++count;
      for (ArcNode arc = G.getVexs()[j].firstArc; arc != null; arc = arc.nextArc) {
        int k = arc.adjVex;
        if (--indegree[k] == 0)           // 对j号顶点的每个邻接点的入度减1
          S.push(k);                // 若入度减为0,则入栈
        if (ve[j] + arc.value > ve[k])
          ve[k] = ve[j] + arc.value;
      }
    }
    if (count < G.getVexNum())
      return false;                 // 该有向图有回路
    else
      return true;
  }
  // G为有向图,输出G的各项关键活动
  public boolean criticalPath(ALGraph G) throws Exception {
    if (!topologicalOrder(G))
      return false;
    vl = new int[G.getVexNum()];
    for (int i = 0; i < G.getVexNum(); i++)
      // 初始化顶点时间的最迟发生时间
      vl[i] = ve[G.getVexNum() - 1];
    while (!T.isEmpty()) {          // 按拓扑逆序列求各顶点的vl值
      int j = (Integer) T.pop();
      for (ArcNode arc = G.getVexs()[j].firstArc; arc != null; arc = arc.nextArc) {
        int k = arc.adjVex;
        int value = arc.value;
        if (vl[k] - value < vl[j])
          vl[j] = vl[k] - value;
      }
    }
    System.out.println("ve:事件最早发生时间、vl事件最晚发生时间");
    System.out.println("事件ve\tvl");
    for (int j = 0; j < G.getVexNum(); j++) {
      int ee = ve[j];
      int el = vl[j];
      System.out.println(G.getVex(j) + "\t" + ee + "\t" + el);    // 输出关键事件
    }
    System.out.println("e:活动最早开始时间、l:活动最晚开始时间");
    System.out.println("源点-->\t汇点权值\te\tl\tl-e\t关键活动");
    for (int j = 0; j < G.getVexNum(); j++)
      // 求ee,el和关键活动
      for (ArcNode arc = G.getVexs()[j].firstArc; arc != null; arc = arc.nextArc) {
        int k = arc.adjVex;
        int value = arc.value;
        int ee = ve[j];
        int el = vl[k] - value;
        char tag = (ee == el) ? '*' : ' ';
        System.out.println(G.getVex(j) + "\t->\t" + G.getVex(k) + "\t"
            + value + "\t" + ee + "\t" + el + "\t" + (el-ee) + "\t" + tag);   // 输出关键活动
      }
    return true;
  }
  public static void main(String[] args) throws Exception {
    ALGraph G = GenerateGraph.generateALGraph();
    CriticalPath p = new CriticalPath();
    p.criticalPath(G);
  }
}
// 调试结果:
//ve:事件最早发生时间、vl事件最晚发生时间
//事件  ve  vl
//v0  0 0
//v1  6 6
//v2  4 6
//v3  5 8
//v4  7 7
//v5  7 10
//v6  16  16
//v7  14  14
//v8  18  18
//e:活动最早开始时间、l:活动最晚开始时间
//源点--> 汇点  权值  e l l-e 关键活动
//v0  ->  v3  5 0 3 3
//v0  ->  v2  4 0 2 2
//v0  ->  v1  6 0 0 0 *
//v1  ->  v4  1 6 6 0 *
//v2  ->  v4  1 4 6 2
//v3  ->  v5  2 5 8 3
//v4  ->  v7  7 7 7 0 *
//v4  ->  v6  9 7 7 0 *
//v5  ->  v7  4 7 10  3
//v6  ->  v8  2 16  16  0 *
//v7  ->  v8  4 14  14  0 *


相关文章
|
17天前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
51 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
20天前
|
存储 算法
数据结构与算法学习二二:图的学习、图的概念、图的深度和广度优先遍历
这篇文章详细介绍了图的概念、表示方式以及深度优先遍历和广度优先遍历的算法实现。
33 1
数据结构与算法学习二二:图的学习、图的概念、图的深度和广度优先遍历
|
20天前
|
机器学习/深度学习 存储 缓存
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
文章主要介绍了排序算法的分类、时间复杂度的概念和计算方法,以及常见的时间复杂度级别,并简单提及了空间复杂度。
18 1
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
|
13天前
|
存储 算法 Java
Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性
Java Set因其“无重复”特性在集合框架中独树一帜。本文解析了Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性,并提供了最佳实践建议,包括选择合适的Set实现类和正确实现自定义对象的hashCode()与equals()方法。
30 4
|
17天前
|
数据采集 监控 安全
厂区地图导航制作:GIS技术与路径导航算法融合
在智能化、数字化时代,GIS技术为厂区的运营管理带来了革命性变化。本文探讨了如何利用GIS技术,通过数据采集、地图绘制、路径规划、位置定位和信息查询等功能,打造高效、精准的智能厂区地图导航系统,提升企业的竞争力和管理水平。
22 0
厂区地图导航制作:GIS技术与路径导航算法融合
|
20天前
|
搜索推荐 算法
数据结构与算法学习十四:常用排序算法总结和对比
关于常用排序算法的总结和对比,包括稳定性、内排序、外排序、时间复杂度和空间复杂度等术语的解释。
14 0
数据结构与算法学习十四:常用排序算法总结和对比
|
20天前
|
存储 缓存 分布式计算
数据结构与算法学习一:学习前的准备,数据结构的分类,数据结构与算法的关系,实际编程中遇到的问题,几个经典算法问题
这篇文章是关于数据结构与算法的学习指南,涵盖了数据结构的分类、数据结构与算法的关系、实际编程中遇到的问题以及几个经典的算法面试题。
26 0
数据结构与算法学习一:学习前的准备,数据结构的分类,数据结构与算法的关系,实际编程中遇到的问题,几个经典算法问题
|
23天前
|
分布式计算 Hadoop Unix
Hadoop-28 ZooKeeper集群 ZNode简介概念和测试 数据结构与监听机制 持久性节点 持久顺序节点 事务ID Watcher机制
Hadoop-28 ZooKeeper集群 ZNode简介概念和测试 数据结构与监听机制 持久性节点 持久顺序节点 事务ID Watcher机制
39 1
|
20天前
|
机器学习/深度学习 搜索推荐 算法
探索数据结构:初入算法之经典排序算法
探索数据结构:初入算法之经典排序算法
|
20天前
|
算法 Java 索引
数据结构与算法学习十五:常用查找算法介绍,线性排序、二分查找(折半查找)算法、差值查找算法、斐波那契(黄金分割法)查找算法
四种常用的查找算法:顺序查找、二分查找(折半查找)、插值查找和斐波那契查找,并提供了Java语言的实现代码和测试结果。
16 0