Расчет критического пути графа

Question

для домашней работы по теории графов, я попросил вычислить (ы) Критические (ие) маршруты (и) и временную задержку проекта в следующем формате:

Запись:Первой строкой ввода будет целое число C, которое указывает количество тестовых случаев (графики, моделирующие деятельность проекта).Первая строка каждого тестового примера содержит два целых числа N и M соответственно, где N представляет количество узлов в проекте и количество M действий.Затем идут m строк, каждая с 3 целыми числами I, J и D, где I и J представляют начальный и конечный узел действия.

Запись должна быть прочитана из файла "entrada.in", который будетбыть в папке программы.Считается бонусом, если ваша программа предоставляет возможность считывать файл с любого пути через графический интерфейс (т.е. без записи полного пути).

Вывод:

В первой строкеВ каждом тестовом примере должна отображаться следующая строка «Случай G: общая длительность 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 из очереди. Для каждого соседа u из v обновите расстояние [u] как расстояние [u] = max (расстояние [u], расстояния [v] + время (v, u)), где время (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 - Для краев, которые не были на пути, вам нужно найти полный провал и свободный провал. Свободная простота проста: чтобы не откладывать выполнение следующей задачи, вам нужно вычислить промежуток времени между началом следующей задачи и временем окончания текущей. Это можно найти по уравнению: расстояние [v] - (расстояние [u] + время (u, v)) для каждого (u, v).

7 - Чтобы найти полный провал, вам понадобится новая информация, то есть самое позднее время, когда задача может начаться без задержки всего проекта. Это может быть сделано путем изменения направления краев вашего графика. Затем, начиная с вершины x, инициализируйте массив позже общей продолжительностью проекта.

8 - Опять же, используя топологический порядок, всякий раз, когда вы освобождаете вершину v для всех ее соседей u, вы делаете позднее [u] = min (late [u], позднее [v] - время (v, u) ). После изменения направления bacj, легко увидеть, что полный провал задается в конце [v] - (позднее [u] + время (u, v)) для каждого ребра (u, v).

9 - Наконец, насколько я понял, вы должны пометить R все ребра, которые имеют полный провал> свободный провал.