Как найти количество дорог от узла A к узлу B в ориентированном графе?

Question

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

Пример:

4 узла 1-> 2 2-> 3 3-> 4 3-> 4 1-> 4

Какой оптимальный способ найти количество дорог от узла A к узлу B?

Ответ для примера: 3: 1-> 2-> 3-> 4; 1-> 2-> 3-> 4 и 1-> 4

Предел для узлов и дуг составляет 1 000 000

Я думаю только об алгоритме перебора.

Есть еще идеи? Edit:

график является ациклическим

Answer 1

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

Одна идея, которая может работать на ациклическом ориентированном графе:

• Упорядочить все узлы таким образом, чтобы для любых двух соединенных узлов родительский узел всегда предшествовал дочернему узлу
• Назначить 0 всем узлам
• Назначить 1 начальному узлу
• Выполните итерацию по узлам в указанном порядке, начиная с начального узла, и выполните
  • Если узел является конечным узлом, то все готово
  • Соединение Foreach, начинающееся на этом узле (т.е.это родитель) do
    • Добавить значение текущего узла к дочернему узлу
• Номер, назначенный конечному узлу, является вашимжелаемый результат

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

Answer 2

Не существует оптимального пути.Эта проблема является проблемой NP Complete.http://en.wikipedia.org/wiki/Feedback_vertex_set

Вы можете найти только хорошие решения