алгоритм алгоритма

Question

Как мне найти все доступные пути для каждой вершины, которые не вызывают цикл?Какой алгоритм использовать?Пожалуйста, будьте краткими и предоставьте ссылки, если это возможно, и задавайте вопросы, если что-то не понятно из замечательной диаграммы ниже :)

Я не ищу кратчайший путь или что-то подобноеВместо этого я просто хочу знать, какие пути я все еще могу нарисовать на своем графике, не вызывая цикл / цикл.Например, L4 может перейти L1, L2, L5 И L2 может перейти L5 ... и т. Д.использовать и как?

Answer 1

Алгоритм кратчайшего пути, такой как Bellman-Ford или Dijkstra, имеет побочный эффект, сообщая вам, к каким узлам вы можете добраться из заданного узла "A", - это точно список узлов, от которых ребра до"A" будет образовывать петлю.

Я подозреваю, что есть способ изменить Bellman-Ford для генерации всех этих списков за один раз, вместо того, чтобы запускать алгоритм отдельно для каждого узла, но я оставлю это как упражнение для читателя. :)

Answer 2

Следующее - не ответ, а просто способ думать об этой проблеме.
Вы можете думать о проблеме с противоположной стороны. Найдите все пути, у которых ровно одно ребро отсутствует, чтобы образовать цикл (я не думал об этом, как). Тогда эти недостающие края - это не те края, которые вы ищете. Примите все, кроме этого.

Answer 3

Посмотрите алгоритм Форда

http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm

Наслаждайтесь ',