алгоритм графа вопрос

Question

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

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

Я предполагаю, что я хочу ациклический граф Directed и нужно помочь выяснить, какой алгоритм использовать и каким образом?

Answer 1

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

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

Enjoy»,

Answer 2

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

Answer 3

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

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