计算图的关键路径

Question

对于图论作业，我要求按照以下格式计算项目的关键路线和时序裕度：

输入：输入的第一行是一个整数 C，它表示测试用例的数量（对项目活动进行建模的图表）。每个测试用例的第一行分别包含两个整数N和M，其中N代表项目中的节点数和活动量M。然后是m行，每行有3个整数I、J和D，其中I和J代表活动的开始和结束节点。

该条目应从程序文件夹中的文件“entrada.in”中读取。如果您的程序提供了通过图形界面从任何路径读取文件的机会（即无需写入完整路径），则可以视为奖励。

输出：

在每个测试用例的第一行必须显示以下字符串“Case G：Duration Total P”，其中G代表测试用例的数量（从1开始），P代表项目总持续时间。然后应在 X 行上表达项目的关键路线的活动，遵循与输入相同的格式（表示持续时间的整数除外），但此外，边是有序（因为第一优先级应该是从低到高的家庭节点，以及从第二低到最高的终端节点）。然后必须遵循与非关键活动相对应的“Y”线，遵循上面列出的相同顺序。对于每个非关键活动，应显示 4 个整数：I、J、T 和 F，其中 T 和 F 分别代表每个活动的总松弛时间和自由松弛时间。此外，如果活动标有红旗，则必须在行尾添加 R。应避免虚拟活动不属于输出的关键路径。

每个测试用例之后应该打印一个空行。输出应写入文件“salida.out”。

例子：

我需要告诉我一些如何做我所需要的事情的想法，我不是在寻求解决方案，只是需要一点帮助（例如伪代码），感谢所有人

Answer 1

首先，我假设我们有一个有向无环图（DAG）。

1 - 我们需要为每个顶点找到每个活动的最小可能开始时间。这就像寻找图中每个顶点的最长路径一样。对于一般图来说，这是 NP 困难的，但由于图是 DAG，我们可以使用拓扑排序在多项式时间内完成此操作。

2 - 计算每个顶点的入度（即计算进入顶点的边数）。由于该图是非循环的，因此至少有一个顶点的入度为零。将所有这样的顶点放入队列中。另外，将距离数组初始化为 0。

伪代码

# Compute the indegree
for each vertex v from the graph:
    for each neighbor u of v:
        indegree[u] += 1

queue Q = empty queue
distance = array filled with zeroes
for each vertex v:
    if indegree[v] = 0:
        insert v on Q

3 - 从队列中选择第一个顶点 v。对于 v 的每个邻居 u，将 distance[u] 更新为 distance[u] = max(distance[u], distances[v] + time(v, u))，其中 time(v, u) 是执行任务（u，v）。从图中删除 v。这可以通过减少每个邻居的入度来完成。将现在入度为 0 的任何新顶点放入队列。重复此过程，直到处理完所有顶点。

伪代码

while Q is not empty:
    v = get front element from Q
    for each neighbor u of v:
        distance[u] = max(distance[u], distance[v] + time(v, u))
        indegree[u] -= 1
        if indegree[u] = 0:
            insert u on Q

4 - 现在，选择距离最大的顶点 x。这是项目的最短总工期。

5 - 我们需要重新构建关键路径。如果时间紧迫，则任务 (u, v) 位于关键路径上，即距离[u] + 时间(u, v) = 距离[v]。因此，从顶点 x 开始，搜索到起始顶点的路径，并具有以下约束：如果您位于顶点 a，则只能前往顶点 b，并且存在一条边 (b, a)，使得距离[a] = 距离[b] + 时间(b, a)。

6 - 对于不在路径上的边，您需要找到总松弛和自由松弛。自由松弛很简单：为了不延迟后续任务，您需要计算下一个任务的开始与当前任务的结束时间之间的时间量。这可以通过以下方程找到：对于每个 (u, v)，距离[v] - (距离[u] + 时间(u, v))。

7 - 要找到总的松弛时间，您需要一条新信息，即任务在不延迟整个项目的情况下可以开始的最晚时间。这可以通过恢复图形边缘的方向来完成。然后，从顶点 x 开始，用总项目持续时间初始化一个数组。

8 - 再次使用拓扑顺序，每当您将顶点 v 出列时，对于其所有邻居 u，您都会执行 Late[u] = min(late[u], Late[v] - time(v, u))。恢复方向 bacj 后，很容易看出总松弛度由每条边 (u, v) 的 Late[v] - (late[u] + time(u, v)) 给出。

9 - 最后，据我了解，您必须用R具有总松弛>自由松弛的所有边缘进行标记。