计算图的关键路径 [英] Calculating the critical path of a graph

问题描述

对于图论的作业，我要求计算（s）关键路线（s） ）和项目的时间松弛：

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

条目应从文件entrada.in将位于
程序文件夹中。如果您的程序提供了通过图形界面从任何路径读取
文件的机会（即，没有
写完整路径），那么将其视为奖励。

$ b $在每个测试用例的第一行中，必须显示以下字符串案例G：持续时间总计P，其中G代表测试次数情况（从1开始）和P总项目持续时间。然后按照与输入相同的格式（除了表示持续时间的整数除外），对项目的（多个）关键路线（s）应表达活动的X行，但此外，边是排序（因为第一优先级应该是从低端到高端节点以及从第二低端到高端的节点）。然后必须按照上面列出的相同顺序遵循对应于非关键活动的Y行。对于每个非关键活动应该显示4个整数，I，J，T和F，其中T和F分别表示每个活动的总松弛和自由松弛。另外，如果活动标有红色标志，则必须在该行的末尾添加一个R.应该避免虚拟活动不是输出关键路径的一部分。

每个测试用例都应该打印一个空白行。
输出应写入文件salida.out。

例如：

我需要告诉我一些关于如何做我需要的东西的想法，我不是要求一个解决方案只是一个小小的帮助（例如伪代码），感谢所有解决方案

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

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

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

伪代码

 ＃为图中每个顶点v计算不完整的
：
为每个v的邻居u：
 indegree [u] + = 1 
 
 queue Q =空队列
距离=数组填充零值
为每个顶点v：
如果indegree [v] = 0：
在Q 
上插入v b  

<3> - 从队列中选择第一个顶点v。对于v的每个邻居u，将距离[u]更新为距离[u] = max（距离[u]，距离[v] +时间（v，u）），其中时间（v，u）执行任务（u，v）。从图中删除V.这可以做我减少其邻居的indegree。排队现在有0个indegree的新顶点。重复此过程，直至处理完所有顶点。

伪代码

 而Q不为空：
v =从v $的每个邻居u得到Q 
的前面元素：
 distance [u] = max（distance [u]，distance [v] + time （v，u））
 indegree [u]  -  = 1 
如果indegree [u] = 0：
在Q 
上插入u  pre> 
 
 
 4  - 现在，选择距离最大的顶点x。这是项目总时间的最小值。
 
 
 
 5  - 我们需要重新构建关键路径。如果时间紧的话，任务（u，v）处于关键路径上，即距离[u] +时间（u，v）=距离[v]。因此，从顶点x开始，搜索到起始顶点的路径，并使用以下约束：如果您在顶点a中，则只能到顶点b，并且有一个边（b，a），使得距离[a] =距离[b] +时间（b，a）。
 
 
 6  - 对于不在路径上的边缘，您需要找到总体松弛和自由松懈。自由松弛很容易：为了不延迟以下任务，您需要计算下一个任务开始到当前结束时间之间的时间量。这可以通过等式：距离[v]  - （距离[u] +时间（u，v））为每个（u，v）找到。 
 
 
 7 - 要发现总的松弛情况，你需要一个新的信息，这是任务可以在不延迟整个项目的情况下开始的最新时间。这可以通过恢复图形边缘的方向来完成。然后，从顶点x开始，使用总的项目持续时间对数组进行初始化。
 
 
 8  - 同样，使用拓扑顺序，只要您为顶点v出列顶点v它的邻居ü，你迟到[u] = min（late [u]，late [v]  -  time（v，u））。在恢复方向bacj之后，很容易看到每个边缘（u，v）的总延迟由迟到[v]  - （late [u] + time（u，v））给出。
 
 
 9  - 最后，据我所知，你必须标记一个 R 所有边的总松弛>自由松弛。 / p> 
for homework of graph theory, I asked to calculate the (s) Critical (s) Routes (s) and timing slack of a project under the following format:

Entry: 
The first line of input will be an integer C, which indicates the number of test cases (graphs modeling the activities of a project). The first line of each test case contains two integers N and M respectively, where N represents the number of nodes in the project and the amount M of activities. Then come m lines, each with 3 integers I, J and D, where I and J represent the start and end node of an activity.

The entry should be read from the file "entrada.in" which will be in the
program folder. Be considered a bonus if your program provides the opportunity to read
the file from any path through a graphical interface (ie, without
write the full path).

Output:

In the first line of each test case must display the following string "Case G: Duration Total P", where G represents the number of test case (starting at 1) and P the total project duration. Then X lines on which activities should be expressed for the (s) Critical (s) Route (s)  of the project, following the same format as the input (except the integer that represents the duration), but additionally, the edges are be ordered (as the first priority should be taking home nodes from lower to higher and end nodes as the second lowest to highest). Then must follow "Y" lines, corresponding to noncritical activities, following the same order listed above. For each noncritical activity should show 4 integers, I, J, T and F, where T and F represent the total slack and free slack of each activity respectively. Additionally you must add an R at the end of the line if the activity is marked with a red flag. Should obviate the dummy activities are not part of the critical path for output.

After each test case should print a blank line.
The output should be written in the file "salida.out. "

Example: 


I need to tell me some idea of how to do what I required, I am not asking for a solution just a little help (pseudocode for example), Thanks to all
解决方案
First of all, I'm assuming we have a directed acyclic graph (DAG). 

1 - We need to find, for each vertex, the minimum possible starting time of each activity. This is like finding the longest path for each vertex in the graph. For general graphs this is NP-hard, but since the graph is a DAG, we may use a topological sort to do this in polynomial time.

2 - Compute the indegree of each vertex (that is, count the number of edges entering them). Since the graph is acyclic, there is at least one vertex that has indegree zero. Put all such vertices on a queue. Also, initialize an array of distances as 0.

Pseudo-code
# 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 - Select the first vertex v from the queue. For each neighbor u of v, update distance[u] as distance[u] = max(distance[u], distances[v] + time(v, u)), where time(v, u) is the time necessary to perform task (u, v). Remove v from the graph. This can be done my decreasing the indegree of each of its neighbors. Enqueue any new vertex that now have 0 indegree. Repeat this procedure until all vertex are processed.

Pseudo-code
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 - Now, select the vertex x with the largest distance. This is the minimum total project duration.

5 - We need to re-construct the critical path. A task (u, v) is on the critical path if has tight times, that is, distance[u] + time(u, v) = distance[v]. So, start with vertex x and search for a path to a starting vertex, with the following constraint: if you're in a vertex a, you can only go to vertex b, with there's an edge (b, a) such that distance[a] = distance[b] + time(b, a).

6 - For the edges that were not on the path, you need to find the total slack and the free slack. The free slack is easy: to not delay the following task, you need to compute the amount of time between the start of the next task and the end time of the current one. This can be found by the equation: distance[v] - (distance[u] + time(u, v)) for each (u, v).

7 - To find the total slack you'll need a new piece of information, that is the latest time a task may begin without delaying the whole project. This can be done by reverting the direction of the edges of your graph. Then, starting with vertex x, initialize an array late with the total project duration.

8 - Again, using the topological order, whenever you dequeue a vertex v, for all its neighbors u, you do late[u] = min(late[u], late[v] - time(v, u)). After reverting the directions bacj, it's easy to see that the total slack is given by late[v] - (late[u] + time(u, v)) for each edge (u, v).

9 - Finally, as far as I understood, you have to mark with an R all edges that have total slack > free slack.

                        
这篇关于计算图的关键路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！