Нахождение кратчайших и самых длинных путей между двумя вершинами в DAG

14

Учитывая невзвешенный DAG (направленный ациклический граф) D=(V,A) и две вершины s и t , возможно ли найти кратчайший и самый длинный путь от s до t за полиномиальное время? Длина пути измеряется количеством ребер.

Я заинтересован в поиске диапазона возможных длин пути за полиномиальное время.

Ps., Этот вопрос является дубликатом вопроса StackOverflow Самый длинный путь в группе обеспечения доступности баз данных .

robowolverine
источник

Ответы:

10

Для проблемы кратчайшего пути, если мы не заботимся о весах, то поиск в ширину - верный путь. В противном случае алгоритм Дейкстры работает до тех пор, пока нет отрицательных ребер.

Для самого длинного пути вы всегда можете сделать Беллмана-Форда на графе со всеми отрицательными весами ребер. Напомним, что Bellman-Ford работает до тех пор, пока нет циклов с отрицательным весом, и поэтому работает с любыми весами на DAG.

jmite
источник
2
Bellman-Ford - это алгоритм динамического программирования.
Рафаэль
1
@ Рафаэль да, но я думаю, что есть прямой алгоритм DP, чтобы найти максимальный путь, вместо того, чтобы сводить на нет все веса ребер.
jmite
1
@jmite: Почему, конечно: просто измените Bellman-Ford, чтобы сделать преобразование онлайн, или максимизируйте, или ...
Рафаэль
1
Между прочим, я не интуитивно убежден в том, что NP-полная проблема Longest Path легко в P на DAG. Буду признателен за доказательство / ссылку / объяснение.
Рафаэль
2
Также есть более простой и эффективный алгоритм DP для DAG
8

Пусть и м = | E ( G ) | , Обозначим через w ( a b ) вес ребра ( a b ) . Предположим, что вы хотите найти минимальную и максимальную стоимость пути от s до t .n=|V(G)|m=|E(G)|w(ab)(ab)st

Начиная с , выполните следующее:b:=t

  1. Если уже был посещен, вернуть уже вычисленные min ( b ) и max ( b ) . В противном случае отметьте b как посещенный.bmin(b)max(b)b

  2. Определите и запишите и max ( b ) следующим образом.min(b)max(b)

    • Если , запишите min ( s ) : = max ( s ) : = 0 .b=smin(s):=max(s):=0
    • Остальное установить игнорируя вершины, для которыхmin(a)=max(a)=inaccessible. При вычислении минимума и максимума для пустого набора ребер (без входных ребер доbили вообще без учета), установитеmin(b)
      min(b):=minab[w(ab)+min(a)]max(b):=maxab[w(ab)+max(a)]
      min(a)=max(a)=inaccessibleb .min(b):=max(b):=inaccessible

Вы должны быть в состоянии доказать, что этот алгоритм работает за время , пренебрегая временем, необходимым для инициализации всех вершинных переменных.O(m)

Ниль де Бодрап
источник
Этот рекурсивный подход «вытягивания» может быть на самом деле медленнее, чем обычный динамический подход «выталкивания», и для обработки рекурсии необходим стек линейного размера. Обычный подход состоит в том, чтобы брать вершины в топологическом порядке и улучшать промежуточный минимум и максимум для каждого соседа текущего узла. Текущий узел всегда имеет конечное значение минимума и максимума, так как все входящие ребра должны быть уже использованы для их улучшения.
Палек