必威体育Betway必威体育官网
当前位置:首页 > IT技术

经典算法之关键路径

时间:2019-10-11 02:14:33来源:IT技术作者:seo实验室小编阅读:64次「手机版」
 

关键路径

问题提出:

设一个工程有11项活动,9个事件,事件V1 ----- 表示整个工程开始,事件V9 ----- 表示整个工程结束。

每个事件的开始必须是它之前的活动已完成。例如:事件V2,V3,V4的开始必须是活动a1,a2,a3完成了。

这时我们会关注两个问题:

(1)完成整个项目需要多少时间?

(2)哪些活动是影响工程进度的关键?

定义:

关键路径:AOE-网中,从起点到终点最长的路径的长度(长度指的是路径上边的权重和)

关键活动:关键路径上的活动

AOE网:也叫边表示活动的网。AOE网是一个带权的有向无环图,其中顶点表示事件,弧表示活动,权表示活动持续的时间。

Ve[j] :表示事件j 的最早发生时间

VI[j]: 表示事件j 的最迟发生时间

e[i]:表示活动ai的最早开始时间

l[i]:表示活动ai的最迟开始时间

方法:

以邻接矩阵作为存储结构

1、从原点V1出发,令Ve[1] = 1,拓扑排序求各个顶点的Ve[i]

2、从Vn出发,令Vl[n] = Ve[n] ,逆拓扑排序求出各个顶点的Vl[i]

3、根据各顶点的Ve和Vl值,计算每条弧的e[i] 和 l[i],找出e[i] = l[i] 的关键活动

简单来说:

顺拓扑排序取大值求出Ve数组,逆拓扑序列取小值求出Vl数组,最后找出Ve[i] = Vl[i] 的顶点,即关键路径上的顶点,将这些顶点连接起来的路径叫关键路径。

实现:

手动实现:

代码实现:

#include <iOStream>
#include <cstring>
using namespace std;
#define N 13
int main()
{
    int map[N][N]; //邻接矩阵
    // 初始化矩阵的值全部为0表示各个顶点间没有边连接
    for(int i = 0; i <= N-1; i++){
        for(int j = 0; j <= N-1; j++){
            map[i][j] = -1;
        }
    }

    int a,b,values;  //定义a,b,用来输入,values存储权值
    int v,l;  //顶点数和边数

    cout << "请输入顶点数:";
    cin >> v;
    cout << "请输入边数:";
    cin >> l;
    cout << "请输入边:" << endl;

    for(int i = 1; i <= l; i++){
            cin >> a >> b >> values;
            map[a][b] = values; // 表示顶点a指向顶点b的边,且权值为values
    }

    int k; //用于计算度数
    int ID[N],OD[N];  //储存各顶点的入度和出度
    int ve[N],vl[N];  //顺拓扑序列取大,逆拓扑序列取小
    memset(ve,0,sizeof(ve));  //初始化ve数组全为0

    for(int i = 1; i <= v; i++){  // 计算入度
        k = 0;
        for(int j = 1; j <= v; j++){
            if(map[j][i] != -1) //如果顶点j到顶点i有边,则顶点i的入度+1
                k++;
        }
        ID[i] = k;
    }
    for(int i = 1; i <= v; i++){  //顺拓扑序列
        if(ID[i] == 0){
            for(int j = 1; j <= v; j++){
                if(map[i][j] != -1){     //如果顶点j与顶点i有边,则删除这条边,并且顶点j的入度-1
                    if(ve[j] < map[i][j] + ve[i])  //取大值
                        ve[j] = map[i][j] + ve[i];
                    ID[j]--;
                }
            }
        }
    }
    for(int i = 1; i <= v; i++){  // 计算出度
        k = 0;
        for(int j = 1; j <= v; j++){
            if(map[i][j] != -1)
                k++;
        }
        OD[i] = k;
    }

    k = v;
    for(int i = 1; i <= v; i++)    //将 vl 数组全部初始化为ve最后一顶点的值
       vl[i] = ve[k];

    for(int i = k; i>=1; i--){  //逆拓扑序列
        if(OD[i] == 0){
            for(int j = 1; j <= v; j++){
                if(map[j][i] != -1){
                    if(vl[j] > vl[i] - map[j][i])   //取小值
                        vl[j] = vl[i] - map[j][i];
                    OD[j]--;
                }
            }
        }
    }
    cout << "****************************\n";
    cout << "Ve数组:";
    for(int i = 1; i <= k; i++){
        cout << ve[i] << " ";
    }
    cout << endl;
    cout << "Ve数组:";
    for(int i = 1; i <= k; i++){
        cout << vl[i] << " ";
    }
    cout << "\n****************************\n";

    cout << "关键路径:";
    for(int i = 1; i <= k - 1; i++){
        if(ve[i] == vl[i]){
            cout << i << "->";
        }
    }
    cout << k << endl;
    return 0;
}

结果:

相关阅读

经典SQL语句大全-【转载自】博客园,作者博客:YuBinfeng

因最近学习MySQL,闲来无事逛帖子时,发现这篇较为经典的博客,特转载以防备用学习,同时希望也可以帮到他人,废话不多说,进入正文  一、

机器学习算法(3)之决策树算法

前言:首先,在了解树模型之前,自然想到树模型和线性模型有什么区别呢?其中最重要的是,树形模型是一个一个特征进行处理,之前线性模型是所

Machine Learning学习笔记(七)粒子群优化算法

粒子群优化算法( PARTICAL SWARMS OPTIMIZATION) 粒子群优化,是除了蚁群算法,鱼群算法之外的一种群体智能的优化算法,源自对鸟类捕

flume之退避算法backoff algorithm

flume之退避算法backoff algorithm什么是退避算法:In a single channel contention based medium access control (MAC) protocols

八大排序算法--堆排序

序言 对于堆排序的学习,实际上就是对于 堆 这一种数据结构的学习,把堆学会了,堆排序自然也就学会了。1、为什么使用堆这种数据结构

分享到:

栏目导航

推荐阅读

热门阅读