graph - 计算图的关键路径

Question

对于图论的作业，我要求计算 (s) Critical (s) Routes (s)以下格式的项目和时间松弛:

条目:输入的第一行将是一个整数 C，表示测试用例的数量(对项目事件进行建模的图表)。每个测试用例的第一行分别包含两个整数N和M，其中N表示项目中的节点数和事件量M。然后是m行，每行3个整数I、J、D，其中I、J分别代表一个事件的起始节点和结束节点。

该条目应从文件“entrada.in”中读取，该文件位于程序文件夹。如果您的类(class)提供阅读机会，则被视为奖励通过图形界面从任何路径的文件(即，没有写完整路径)。

输出:

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

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

例子:

我需要告诉我一些关于如何做我需要的事情的想法，我不是在寻求解决方案只是一点帮助(例如伪代码)，谢谢大家

Answer 1

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

1 - 我们需要为每个顶点找到每个事件的最短可能开始时间。这就像寻找图中每个顶点的最长路径。对于一般图，这是 NP-hard，但由于图是 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)如果时间紧，就在关键路径上，即distance[u] + time(u，v)= distance[v]。因此，从顶点 x 开始并搜索到起始顶点的路径，具有以下约束:如果您在顶点 a 中，则只能到达顶点 b，并且有一条边 (b, a) 这样的距离[a] = 距离[b] + 时间(b, a)。

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

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

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 标记所有具有总松弛度 > 自由松弛度的边缘。