Учитывая невзвешенный DAG (направленный ациклический граф) и две вершины и , возможно ли найти кратчайший и самый длинный путь от до за полиномиальное время? Длина пути измеряется количеством ребер.
Я заинтересован в поиске диапазона возможных длин пути за полиномиальное время.
Ps., Этот вопрос является дубликатом вопроса StackOverflow Самый длинный путь в группе обеспечения доступности баз данных .
источник
Пусть и м = | E ( G ) | , Обозначим через w ( a → b ) вес ребра ( a → b ) . Предположим, что вы хотите найти минимальную и максимальную стоимость пути от s до t .n=|V(G)| m=|E(G)| w(a→b) (a→b) s t
Начиная с , выполните следующее:b:=t
Если уже был посещен, вернуть уже вычисленные min ( b ) и max ( b ) . В противном случае отметьте b как посещенный.b min(b) max(b) b
Определите и запишите и max ( b ) следующим образом.min(b) max(b)
Вы должны быть в состоянии доказать, что этот алгоритм работает за время , пренебрегая временем, необходимым для инициализации всех вершинных переменных.O(m)
источник