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

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

Пример :

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

Как найти оптимальное количество дорог из узла А в узел В?

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

Лимит для узлов и арок 1 000 000

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

Любые другие идеи? Редактировать:

граф ациклический


graph algorithm directed-graph
person Dan Dinu    schedule 28.05.2011    source источник
comment
Разве это не то, что вы ищете? stackoverflow.com/questions/58306   -  person detunized    schedule 28.05.2011
comment
@detunized Я думаю, что другой вопрос хочет перечислить все дороги, а этот хочет только подсчитать их. Подсчет может быть выполнен намного быстрее, чем перечисление, потому что дорог может быть экспоненциально много.   -  person CodesInChaos    schedule 28.05.2011

Ответы (2)


arrow_upward
1
arrow_downward

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

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

  • Упорядочить все узлы таким образом, чтобы для любых двух соединенных узлов родительский узел всегда располагался перед дочерним узлом.
  • Назначить 0 всем узлам
  • Назначьте 1 начальному узлу
  • Iterate over the nodes in that order starting with the start node and do
    • If the node is the end node you're done
    • Foreach connection starting on this node(i.e. it is the parent) do
      • Add the value of the current node to the child node
  • Номер, присвоенный конечному узлу, является желаемым результатом.

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

person CodesInChaos    schedule 28.05.2011

arrow_upward
0
arrow_downward

Оптимального пути нет. Эта задача является NP-полной. http://en.wikipedia.org/wiki/Feedback_vertex_set

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

person User    schedule 28.05.2011
comment
Я не понимаю, как это проблема, описанная в той статье. - person CodesInChaos; 28.05.2011