精华内容
下载资源
问答
  • 关键路径算法

    千次阅读 2019-08-27 20:58:50
    关键路径算法算法: 一、先顺着找,求每个顶点的最早发生时间ve(j)=Max{ve(i) + dut(<i,j>)} 1、v1到它的后继结点分别为: v1->v2 = 6 v1->v3 = 4 v1->v4 = 5 则有表: {v1:0,v2:6,v3:4,v4:...

    关键路径算法算法:

    一、先顺着找,求每个顶点的最早发生时间ve(j)=Max{ve(i) + dut(<i,j>)}

    1、v1到它的后继结点分别为:

    v1->v2 = 6

    v1->v3 = 4

    v1->v4 = 5

    则有表:

    {v1:0,v2:6,v3:4,v4:5}

    2、然后看v5

    v2->v5=v1->v2->v5=7

    v3->v5=v1->v3->v5=5

    取大路径则有表:

    {v1:0,v2:6,v3:4,v4:5,v5:7}

    3、然后看v6

    v4->v6=v1->v4->v6=7

    则有表:

    {v1:0,v2:6,v3:4,v4:5,v5:7,v6:7}

    4、然后看v7

    v5->v7=7+9=16

    {v1:0,v2:6,v3:4,v4:5,v5:7,v6:7,v7:16}

    5、然后看v8

    v5->v8=14

    v6->v8=11

    则有表:

    {v1:0,v2:6,v3:4,v4:5,v5:7,v6:7,v7:16,v8:14}

    6、然后看v9

    v7->v9=18

    v8->v9=18

    则有表:

    {v1:0,v2:6,v3:4,v4:5,v5:7,v6:7,v7:16,v8:14,v9:18}

    二、倒着找,找顶点的最晚发生时间vl(i)=Min{vl(j) - dut(<i,j>)}

    1、v9=18

    则有表{v9:18}

    2、看v7 v8

    v7=v9->v7=16

    v8=v9->v8=14

    则有表{v9:18,v8:14,v7:16}

    3、看v5

    v5=v7->v5=7

    v5=v8->v5=7

    则有表{v9:18,v8:14,v7:16,v5:7}

    4、看v6

    v6=v9->v8->v6=10

    则有表{v9:18,v8:14,v7:16,v5:7,v6:10}

    5、看v4

    v4=v6->v4

    则有表{v9:18,v8:14,v7:16,v5:7,v6:10,v4:8}

    6、看v3

    v3=v5->v3=6

    则有表{v9:18,v8:14,v7:16,v5:7,v6:10,v4:8,v3:6}

    7、看v2

    v2=v5->v2=6

    则有表{v9:18,v8:14,v7:16,v5:7,v6:10,v4:8,v3:6,v2:6}

    8、看v1

    v1=v2->v1=0

    v1=v3->v1=2

    v1=v4->v1=3

    则有表{v9:18,v8:14,v7:16,v5:7,v6:10,v4:8,v3:6,v2:6,v1:0}

    三、求一和二相等的元素就是关键路径中的定点集合

    表一(ve):{v1:0,v2:6,v3:4,v4:5,v5:7,v6:7,v7:16,v8:14,v9:18}

    表二(vl):{v9:18,v8:14,v7:16,v5:7,v6:10,v4:8,v3:6,v2:6,v1:0}

    ={v1,v2,v5,v7,v8,v9}

    也就是说v1->v2->v5->v7->v9和v1->v2->v5->v8->v9都是关键路径

    四、求关键活动

    关键路径上的边都是关键活动,但是这里还是要列个表说明下,求关键活动的理论求法,即通过活动的最早和最晚发生时间,最早和最晚发生时间相等的就是关键活动。

    e(i)表示弧<j,k>

    e(i) = ve(j)

    l(i) = vl(k) - dut(<j,k>)

               e(i)      l(i)

    a1      0         6-6=0

    a2      0         6-4=2

    a3      0         8-5=3

    a4      6         7-1=6

    a5      4         7-1=6

    a6      5         10-2=8

    a7      7         16-9=7

    a8      7         14-7=7

    a9      7         14-4=10

    a10    16       18-2=16

    a11    14        18-4=14

    可以找到e(i)等于l(i)的关键活动,分别为 a11  a10  a8  a7   a4 a1

    展开全文
  • [算法]详解关键路径算法

    千次阅读 2017-01-09 10:20:22
    详解关键路径算法#include #include using namespace std; int eventsSize, activitiesSize; int activitiesCostTimes[100][100]; pair, int> activities[100]; int eventEarlyBegin[100], eventLate

    详解关键路径算法

    #include <iostream>
    #include <vector>
    using namespace std;
    int eventsSize, activitiesSize;
    int activitiesCostTimes[100][100];
    pair<int, int> activities[100];
    int eventEarlyBegin[100], eventLatestBegin[100];
    int activityEarlyBegin[100], activityLatestBegin[100];
    
    void init() {
        memset(eventLatestBegin, 0, sizeof(eventLatestBegin));
        memset(eventEarlyBegin, 0, sizeof(eventEarlyBegin));
        memset(activityEarlyBegin, 0, sizeof(eventEarlyBegin));
        memset(activityLatestBegin, 0, sizeof(activityLatestBegin));
    }
    
    void computeEventEarliestBegin() {
        eventEarlyBegin[1] = 0;
        int maxTimes;
        for (int i = 2; i <= eventsSize; ++i) {
            maxTimes = INT_MIN;
            for (int j = 1; j <= eventsSize; ++j) {
                if (activitiesCostTimes[j][i] != 0) {
                    maxTimes = max(maxTimes, eventEarlyBegin[j] +
                                             activitiesCostTimes[j][i]);
                }
            }
            eventEarlyBegin[i] = maxTimes;
        }
    }
    
    void computeEventLatestBegin() {
        eventLatestBegin[eventsSize] = eventEarlyBegin[eventsSize];
        int minCostTimes;
        for (int i = eventsSize - 1; i >= 1; --i) {
            minCostTimes = INT_MAX;
            for (int j = i; j <= eventsSize; ++j) {
                if (activitiesCostTimes[i][j] != 0) {
                    minCostTimes = min(minCostTimes, eventLatestBegin[j] -
                            activitiesCostTimes[i][j]);
                }
            }
            eventLatestBegin[i] = minCostTimes;
        }
    }
    
    void computeActivityEarlyBegin() {
        for (int i = 1; i <= activitiesSize; ++i) {
            activityEarlyBegin[i] = eventEarlyBegin[activities[i - 1].first];
        }
    }
    
    void computeActivityLatestBegin() {
        for (int i = 1; i <= activitiesSize; ++i) {
            activityLatestBegin[i] = eventLatestBegin[activities[i - 1].second] -
                    activitiesCostTimes[activities[i - 1].first][activities[i -
                            1].second];
        }
    }
    
    vector<int> criticalPath() {
        init();
        computeEventEarliestBegin();
        computeEventLatestBegin();
        computeActivityEarlyBegin();
        computeActivityLatestBegin();
        vector<int> vec;
        for (int i = 1; i <= activitiesSize; ++i) {
            if (activityEarlyBegin[i] == activityLatestBegin[i]) {
                vec.push_back(i);
            }
        }
        return vec;
    }
    
    int main() {
        cin >> eventsSize >> activitiesSize;
        int start, end, last;
        for (int i = 0; i < activitiesSize; ++i) {
            cin >> start >> end >> last;
            activitiesCostTimes[start][end] = last;
            activities[i] = make_pair(start, end);
        }
        vector<int> ans = criticalPath();
        for (int j = 0; j < ans.size(); ++j) {
            cout << ans[j] << " ";
        }
        cout << endl;
        return 0;
    }

    测试样例:

    9 11
    1 2 6
    1 3 4
    1 4 5
    2 5 1
    3 5 1
    4 6 2
    5 7 7
    5 8 5
    6 8 4
    7 9 2
    8 9 4

    详情见:

    关键路径MBA
    关键路径

    展开全文
  • 关键路径核心算法

    千次阅读 2018-08-12 12:53:34
    关键路径核心算法:求一条不影响整体工程进度的最优路径方案,下面我将分为三个步骤详细讲解该算法。 第一步:求各个事件(结点)的最早时间(在这里我们用一个数组va[]来存储各个事件的最早时间)和最晚时间(在...

    关键路径核心算法:求一条不影响整体工程进度的最优路径方案,下面我将分为三个步骤详细讲解该算法。

    第一步:求各个事件(结点)的最早时间(在这里我们用一个数组va[]来存储各个事件的最早时间)和最晚时间(在这里我们用一个数组vb[]来存储各个事件的最迟时间),该工程图如下所示。

    这里写图片描述

    首先进行拓扑排序(0,1,2,3)求最早时间,得到:

    va[0]=0;

    va[1]=3;

    va[2]=max{va[0]+a2,va[1]+a3}=7;

    va[3]=max{va[0]+a0,va[1]+a4,va[2]+a5}=12;

    然后逆拓扑排列(3,2,1,0)求最迟时间,得到

    vb[3]=12;

    vb[2]=7;

    vb[1]=min{vb[2]-a3,vb[3]-a4}=3;

    vb[0]=min{vb[3]-a0,vb[2]-a2,vb[1]-a1}=0;

    接下来求该图“边”的最早时间用w(ai)表示,“边”的最迟时间用l(ai)表示;(注意,上面的是结点对应的的最早时间和最短时间,不要混淆)

    最早事件时间,过程如下

    w(a1)=w(a2)=w(a0)=va[0]=0;

    w(a3)=w(a4)=va[1]=3;

    w(a5)=va[2]=7;

    最迟发生时间,过程如下

    l(a0)=vb[3]-a0=7;

    l(a1)=vb[1]-a1=0;

    l(a2)=vb[2]-a2=5;

    l(a3)=vb[2]-a3=3;

    l(a4)=vb[3]-a4=11;

    l(a5)=vb[3]-a5=7;

    最后一步,建一个图表,将边的最早发生时间和边的最晚发生时间对比,如果一样,则这条边就是关键路径上的一条子路径。

    最早发生时间最迟发生时间相同点
    a007×
    a100
    a205×
    a333
    a4311×
    a577

    将相同的提取出来得到关键路径(a1,a3,a5);

    即a1->a3->a5就是这个图的关键路径。

    展开全文
  • 引入灰色理论思想,将传统PERT网络计划已知条件弱化,探索出适合计算机求解的关键线路算法算法适应国内航空产品项目特征,适合大型复杂航空产品项目计算机求解,并在典型航空产品项目得到应用验证。
  • 采用邻接矩阵表示项目活动网络图需要较多的存储空间,且基于结构化程序设计思想实现网络图和关键路径算法都非常繁琐。采用面向对象的类表示活动,基于动态数组表示活动网络图及活动之间的逻辑关系,并据此开发了基于...
  • 大话数据结构 第七章 图(二) 最小生成树、最短路径、拓扑排序、关键路径算法最小生成树定义Prim算法Kruskal算法最短路径Dijkstra算法Floyd算法拓扑排序AOV网拓扑序列拓扑排序算法关键路径AOE网关键路径算法 ...

    大话数据结构 第七章 图(二) 最小生成树、最短路径、拓扑排序、关键路径算法

    最小生成树

    定义

    • 所谓的最小成本,就是n个顶点,用n-1条边把一个连通图连接起来,并且使得权值的和最小
    • 最小生成树:构造连通网的最小代价生成树

    Prim算法

    • 中心思想是以某顶点为起点,逐步找各顶点上最小权值的边来构建最小生成树
    • 假设N=(V,{E})是连通网,TE是N上最小生成树中边的集合。算法从U={u0},TE={}开始。重复执行下述操作:
    • 在所有u∈U,v∈V-U的边(u,v)∈E中找一条代价最小的边(u0,v0)并入集合TE,同时v0并入U,直至U=V为止。此时TE中必有n-1条边,则T=(V,{TE})为N的最小生成树
    • 主要针对稠密图(边数较多时)
    • 算法的时间复杂度为O(n^2)

    Kruskal算法

    • 中心思想是以边为目标去构建,因为权值是在边上,直接去找最小权值得边来构建最小生成树,构建时要考虑是否形成了环路
    • 假设N=(V,{E})是连通网,则令最小生成树的初始状态为只有n个顶点而无边的非连通图T={V, {} },图中每个顶点自成一个连通分量。在E中选择代价最小的边,若该边依附的顶点落在T中不同的连通分量上,则将此边加入到T中,否则舍去此边而选择下一条代价最小的边。以此类推,直至T中所有顶点都在同一连通分量上为止。
    • 主要针对稀疏图
    • 算法的时间复杂度为O(e log e)

    最短路径

    • 对于网图来说,最短路径,是指两顶点之间经过的边上权值之和最小的路径

    Dijkstra算法

    • 是一个按路径长度递增的次序产生最短路径的算法
    • 不是一下子求出了源点到终点的最短路径,而是一步步求出它们之间顶点的最短路径,过程中都是基于已经求出的最短路径的基础上, 求得更远顶点的最短路径
    • 用于解决从某个源点到其余各顶点的最短路径问题,算法复杂度为O(n^2)
    • 若要用于任一顶点到其余所有顶点的最短路径,复杂度为O(n^3)

    Floyd算法

    • 定义两个数组D和P,其中D代表顶点到顶点的最短路径权值和的矩阵,P代表对应顶点的最小路径的前驱矩阵
    • D^0[v][w] = min{D^(-1)[v][w], D^(-1)[v][0] + D^(-1)[0][w]}
    • D0以D^(-1)为基础,D1以D0为基础……直至最后一个顶点Dn
    • 代码间接,时间复杂度为O(n^3)

    拓扑排序

    • 主要是为了解决一个工程能否顺序进行的问题

    AOV网

    • 在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的有限关系,这样的有向图为顶点表示活动的网,我们称为AOV网

    拓扑序列

    • 设G=(V, E)是一个具有n个顶点的有向图,V中的序列v1,v2,…vn,满足若从顶点vi到vj有一条路径,则在顶点序列中顶点vi必在vj之前。则我们称这样的顶点序列为一个拓扑序列

    拓扑排序算法

    • 基本思路是:从AOV网中选择一个入度为0的顶点输出,然后删去此顶点,并删除以此顶点为尾的弧,继续重复此步骤,直到输出全部顶点或者AOV网中不存在入度为0的顶点为止
    • 顶点表结点结构:in(入度的数字),data,firstedge
    • 使用了栈结构(LIFO)
    • 将入度为0的顶点入栈的时间复杂为O(n),入度减1的操作共执行了e次,整个算法的复杂度为O(n+e)

    关键路径

    • 主要为了解决工程完成需要的最短时间问题

    AOE网

    • 在一个表示工程的带权有向图中,用顶点表示事件,用有向边表示活动,用边上的权值表示活动的持续时间,这种有向图的边表示活动的网,称之为AOE网
    • 把路径上各个活动所持续的时间之和称为路径长度,从源点到汇点具有最大长度的路径称为关键路径,在关键路径上的活动称为关键活动

    关键路径算法

    • 只需要找到所有活动的最早开始时间和最晚开始时间,并且比较它们,如果相等就意味着此活动是关键活动,活动间的路径为关键路径
    • 时间复杂度为O(n+e)
    展开全文
  • Floyd算法 Floyd算法又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短...算法思想: 从起始顶点开始,依次加入一个顶点,每加入一个顶点,更新一下各条最短路径长度。各条最短路径长度...
  • 关键路径的概念和算法

    千次阅读 2018-10-02 17:22:43
    AOE网:在一个表示工程的带权有向图中,用顶点表示事件,用有向边表示活动,边上的权值表示活动的持续时间,称这样的有向图叫做边表示活动的网,简称AOE网。AOE网中没有入边的顶点称为始点(或源点),...关键路径...
  • 最短路径算法

    千次阅读 2014-11-22 20:00:59
    问题描述: 最短路径问题是图论研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中两结点之间的最短路径
  • 有关关键路径的概念和算法

    千次阅读 2011-12-23 22:33:05
    AOE网:在一个表示工程的带权有向图中,用顶点表示事件,用有向边表示活动,边上的权值表示活动的持续时间,称这样的有向图叫做边表示活动的网,简称AOE网。AOE网中没有入边的顶点称为始点(或源点),没有...关键路径
  • 最优路径算法(python)

    千次阅读 2019-11-30 01:02:16
    最优路径算法(python实现) 从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径,称为最短路径 主要的最优(最短)路径算法: 一、深度优先算法;二、广度优先算法;三、Dijstra最短路径...
  • Dijkstra最短路径算法 按路径长度的递增次序,逐步产生最短路径的贪心算法 基本思想:首先求出长度最短的一条最短路径,再参照它求出长度次短的一条最短路径,依次类推,直到从顶点v 到其它各顶点的最短路径全部求...
  • AOE算法求解关键路径 问题描述: 输入顶点和边,得到有向图,求出关键路径。 . 关键路径通常(但并非总是)是决定项目工期的进度活动序列。它是项目中最长的路径,即使很小浮动也可能直接影响整个项目的最早...
  • 单源最短路径算法

    千次阅读 2017-10-30 15:37:05
    最短路径问题:如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条,如何找到一条路径使得沿此路径上各边上的权值总和达到最小。当然这只是最基础的应用,关于单源最短路径还有很多变体: 1....
  • 算法思想

    千次阅读 2013-01-12 10:33:31
    Taken from "Introduction to The Design and Analysis of Algorithms" by Anany Levitin ...节选自《算法设计与分析基础》潘彦 译 蛮力法 就像宝剑不是撬棍一样,科学也很少使用蛮力。 ——Edward
  • 最短路径算法对比

    2018-10-22 13:11:10
    目录 ...五、最短路径算法对比分析 一、只有5行的算法---Floyd-Warshall  已知一些点,和这些点间的路径,求任意两个点之间的最短路径,这个问题也被称为“多源最短路径问题”。  最直接想...
  • 图——基本的图算法(四)关键路径

    万次阅读 多人点赞 2018-10-26 17:34:07
    图——基本的图算法(四)关键路径 1. 基本概念 (1)AOV网(Activity On Vertex Network) AOV网是一个表示工程的有向图中,其中的顶点用来表示活动,弧则用来表示活动之间的优先关系。举个简单的例子,假定起床后...
  • 关键路径求解

    千次阅读 2018-07-15 10:29:01
    前言:首先关键路径是针对DAG图来说的,我们通常用AOE网来表示一个工程的进行过程,AOV网可以转换为AOE网,AOE网是没有环的,通常关键路径求解需要弄清楚以下四个概念:事件最早发生时间Ve[u]、事件最晚发生时间Vl[u...
  • 关于最优路径算法

    千次阅读 2018-02-24 14:30:11
    Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历...
  • Astar A*算法 最短路径算法

    万次阅读 2016-10-30 16:29:06
    A*算法 astar算法
  • 五大算法思想

    千次阅读 2015-07-09 13:53:19
    五大算法思想 分治算法 一、基本概念  在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题...
  • 拓扑排序和关键路径

    千次阅读 多人点赞 2020-03-19 14:23:45
    文章目录拓扑排序和关键路径摘 要1:引言2:设计步骤:etv和ltv数组的计算方法算法思想2. 实现代码建立(以邻接表为例)邻接表建立栈的建立拓扑排序关键路径的查找完整代码编译环境3.后记 拓扑排序和关键路径 摘 要 ...
  • 松弛操作Dijkstra算法和BellmanFord算法都是基于这个简单的操作。 下面我们来了解这个简单而重要的操作: 线松弛 线松弛也就是处理 起点到边的两个顶点距离与两个顶点直接距离的问题。 如:假如distTo[4]>distTo...
  • Floyd算法用于求解图中各个顶点之间的最短路径算法用三层for循环中一个if判断就可以求解,相比于对图中每个顶点应用一次Dijkstra算法来求解单源最短路径,Floyd算法的常数项更少,效率更高。 算法思想 本人认为...
  • 这是我们学校做的数据结构课设,要求分别输出关键路径,我查遍资料java版的只能找到关键路径,但是无法分别输出关键... 如上图关键路径被分别输出(采用了DFS算法): 例:AOE 图如下: 算法设计如下: ...
  • 本文主要介绍了拓扑排序、关键路径、AOE、AOV的基本概念,拓扑排序和关键路径算法思想,以及它们的实现。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 44,208
精华内容 17,683
关键字:

关键路径的算法思想