Самый длинный нециклический путь в направленном невзвешенном графике
Что алгоритм может использоваться для нахождения самого длинного пути в невзвешенном направленном графе без петель?
3 ответа
Динамическое программирование . Он также упоминается в Проблема самого длинного пути , учитывая, что это DAG.
Следующий код из Википедии:
algorithm dag-longest-path is
input:
Directed acyclic graph G
output:
Length of the longest path
length_to = array with |V(G)| elements of type int with default value 0
for each vertex v in topOrder(G) do
for each edge (v, w) in E(G) do
if length_to[w] <= length_to[v] + weight(G,(v,w)) then
length_to[w] = length_to[v] + weight(G, (v,w))
return max(length_to[v] for v in V(G))
В Википедии есть алгоритм: http://en.wikipedia.org/wiki/Longest_path_problem
Похоже, они используют весовые коэффициенты, но должны работать со всеми весами, установленными на 1.
{{1} }Пока граф является ациклическим, все, что вам нужно сделать, это отменить веса ребер и запустить любой алгоритм кратчайшего пути.
РЕДАКТИРОВАТЬ: Очевидно, вам нужен алгоритм кратчайшего пути, поддерживающий отрицательные веса. Кроме того, алгоритм из Википедии, кажется, имеет лучшую временную сложность, но я оставлю свой ответ здесь для справки.