Нахождение пути с наибольшим числом узлов в ориентированном графе

Question

Что было бы хорошим способом найти в ориентированном графе путь с наибольшим числом узлов?

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

Упоминание: графикгарантированно не имеет циклов.

Answer 1

У вас есть ориентированный ациклический граф (DAG), и вы хотите найти путь с наибольшим числом узлов.Это фактическое нахождение longest path в DAG.

Эта проблема разрешима для DAG за полиномиальное время.Подробнее об этом здесь: - Википедия.

Answer 2

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

Если граф ациклический: вам следует запустить топологическую сортировку.Тогда:

foreach(node in topological_sort_order) {
   foreach(prev_node in neibhours[node]) {
      // there is edge from prev_node to node
      // since vertices are sorted in topological order than
      // value for longest_path[prev_node] is already computed
      longest_path[node] = max(longest_path[node],  longest_path[prev_node] + 1);
   }
}

Answer 3

Поскольку ваш ввод является ориентированным графом, а не ориентированным ациклическим графом, он является NP-завершенным, и упомянутые решения не работают.Но, как сказал logic_max: это самая длинная проблема пути, и вы уменьшаете ее, давая каждому ребру стоимость одного.