图的关键路径--最早开始时间和最晚开始时间

（实验内容只是求关键路径的一部分，在网站找不到只含这一部分的参考，所以自己给搞了一下，欢迎大佬指正。）

题目描述：给定有向图无环的边信息，求每个顶点的最早开始时间、最迟开始时间。

输入

第一行图的顶点总数

第二行边的总数

第三行开始，每条边的时间长度，格式为源结点   目的结点   长度

输出

第一行：第个顶点的最早开始时间

第二行：每个顶点的最迟开始时间

样例输入：

9
12
0 1 3
0 2 10
1 3 9
1 4 13
2 4 12
2 5 7
3 6 8
3 7 4
4 7 6
5 7 11
6 8 2
7 8 5

样例输出：

0 3 10 12 22 17 20 28 33 
0 9 10 23 22 17 31 28 33 

代码（含解析）：

#include
#include
using namespace std;
int main()
{
    int vexnum;
    int arcnum;
    cin >> vexnum >> arcnum;
    int* in = new int[vexnum];
    int* ve = new int[vexnum];//最早开始时间
    int* vl = new int[vexnum];//最晚开始时间
    int** p;
    p = new int* [vexnum];
    for (int i = 0; i < vexnum; i++) {
        in[i] = 0;
        p[i] = new int[vexnum];
        for (int j = 0; j < vexnum; j++)
            p[i][j] = 0;
    }
    int s1, s2, length;
    for (int i = 0; i < arcnum; i++)
    {
        cin >> s1 >> s2 >> length;
        p[s1][s2] = length;
        if (p[s1][s2] != 0)
        {
            in[s2] += 1;
        }
    }
    queueQ;
    for (int i = 0; i < vexnum; i++)
    {
        if (in[i] == 0)
            Q.push(i);
    }
    int* list = new int[vexnum+1];//建立一个数组存放拓扑排序的结果
    int i = 0;
    while (!Q.empty())
    {
        int t = Q.front();
        Q.pop();
        for (int j = 0; j < vexnum; j++)
        {
            if (p[t][j] != 0)
            {
                in[j]--;
                if (in[j] == 0)
                    Q.push(j);
            }
        }
        list[i] = t; 
        i++;
    }
    ve[0] = 0;
    for (int i = 0; i < vexnum; i++)
        vl[i] = 0;
    for (int j = 1; j < vexnum; j++)
    {
        int max = 0;
        for (int i = 0; i < vexnum; i++)
        {
            if (p[list[i]][list[j]]!=0&&(p[list[i]][list[j]] + ve[i])> max)
            {
                max = p[list[i]][list[j]] + ve[i];
            }
        }
        ve[j] = max;
    }
    for (int i = 0; i < vexnum; i++)
    {
        for (int j = 0; j < vexnum; j++)//题目输出按照拓扑排序的顺序，需要进行这一步查找
            if (list[j] == i)
                cout << ve[j] << " ";
    }
    cout << endl;
    vl[vexnum - 1] = ve[vexnum - 1];
    for (int i = vexnum - 2; i > 0; i--)
    {
        int min = 1000;
        for (int j = vexnum - 1; j >= 0; j--)
        {
            if (p[list[i]][list[j]] != 0 && (vl[j] - p[list[i]][list[j]]) < min)
            {
                min = vl[j] - p[list[i]][list[j]];
            }
        }
        vl[i] = min;
    }
    for (int i = 0; i < vexnum; i++)
    {
        for(int j=0;j 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5611442.html