经典算法之关键路径

末蓝、 2022-05-19 02:48 183阅读 0赞

# 问题提出： #

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

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

![70][]

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

（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\] 的顶点，即关键路径上的顶点，将这些顶点连接起来的路径叫关键路径。

# 实现： #

### 手动实现： ###

![70 1][]

## 代码实现： ##

#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;
    }

# 结果： #

![70 2][]

[70]: /images/20220519/adaa3b9696c046668fbcbf7004ce90c8.png
[70 1]: /images/20220519/5149488805ea490d9e8f08751855f40e.png
[70 2]: /images/20220519/7a619e114a0a4cc49844ee6ec34d83b7.png