Алгоритм нахождения всех критических путей

Question

Мне нужно создать алгоритм, который мог бы найти все критические пути в графе.

Я нашел топологический порядок узлов, рассчитал самое раннее время окончания и самое позднее время начала для каждого узла.

Также я нашел все критические узлы (то есть те, которые находятся на критическом пути).

Проблема состоит в том, чтобы собрать все вместе и фактически распечатать все эти пути.Если в графе только 1 критический путь, то я могу с ним справиться, но проблемы начинаются, если существует несколько путей.

Например, один узел является частью нескольких критических путей, несколько начальных узлов, несколько концовузлы и тд.Мне не удалось придумать алгоритм, который мог бы учесть все эти факторы.

Вывод, который я ищу, выглядит примерно так (если a, b, c и т. Д. - все узлы):

• a-> e
• a-> c-> f-> i-> j-> k
• a-> c-> g
• l-> e

Было бы неплохо, если бы кто-то мог написать описание алгоритма, который мог бы найти пути, зная критические узлы, топологический порядок и т. Д. Или, возможно, также в C иликод Java.

РЕДАКТИРОВАТЬ: Вот пример, который должен предоставить вывод, который я опубликовал ранее.Критические пути красного цвета, значения каждого узла отмечены над или около него.

Answer 1

Вычисление последних начальных времен почти также обеспечивает критический путь. Вам нужно построить результаты из терминальных узлов и вернуться назад:

1. найти все узлы, которые имеют максимальное время самого раннего окончания (t = 11, узлов = {e, g, k})
2. для каждого из них найдите все предшественники, которые имеют локально максимальное время самого раннего окончания. Для е, как l, так и k имеют t = 2, поэтому вы получаете l-> e, a-> e. Для g, t = 6, что для узла c, так что вы получите c-> g. Для k t = 10, но только j имеет это как конечное время, так что вы получите j-> k.
3. повторяйте, пока не дойдете до начального узла. l-> e и a-> e уже являются начальными узлами. у c-> g есть единственный предшественник a, поэтому вы получаете a-> c-> g. j-> k имеет t = 9, то есть время окончания i, так что вы получаете я-> J-> K.

Answer 2

Я не совсем понимаю ваш вопрос: что такое критический путь? Вам могут помочь: алгоритм вычисления минимального связующего дерева или алгоритм кратчайшего пути Дейкстры - хотя вы, возможно, уже знали эти алгоритмы.