Самый длинный ациклический путь в направленном невзвешенном графике

19

Какой алгоритм можно использовать для поиска самого длинного пути в невзвешенном ориентированном ациклическом графе?

    
задан Hellnar 26.03.2010 в 18:26
источник

4 ответа

22

Динамическое программирование . Он также ссылается на Самая длинная проблема пути , учитывая, что это 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))
    
ответ дан Larry 26.03.2010 в 18:30
  • Это возвращает только длину пути. Можно ли легко изменить код, чтобы вернуть путь? –  oschrenk 02.04.2012 в 22:46
  • Да, так же, как и большинство проблем с DP - отслеживайте предыдущее и возвращайтесь к нему. –  Larry 17.07.2012 в 18:34
  • topOrder (G) - это список вершин G в топологическом порядке –  Andre Holzner 29.10.2016 в 16:22
  • поэтому цикл начинается с «источников» (без входящих ребер) и заканчивается «потоками» (без исходящих ребер) –  Andre Holzner 29.10.2016 в 16:57
  • бумага с одним и тем же алгоритмом, но проще следовать логическому обоснованию в случае необходимости. –  Andrei Petre 19.04.2017 в 22:16
6

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

EDIT: Очевидно, вам нужен алгоритм кратчайшего пути, поддерживающий отрицательные веса. Кроме того, алгоритм из Википедии, похоже, имеет лучшую временную сложность, но я оставлю свой ответ здесь для справки.

    
ответ дан Can Berk Güder 26.03.2010 в 18:31
  • и сохраним отрицательные веса как отрицательные? :п –  Hellnar 27.03.2010 в 01:26
  • @Hellnar: нет, если у вас есть отрицательные веса в исходном графе, они должны стать положительными. w '= - (w) –  Can Berk Güder 27.03.2010 в 10:55
2

В Википедии есть алгоритм: Ссылка

Похоже, что они используют весовые коэффициенты, но должны работать с весами, установленными на 1.

    
ответ дан Dan 26.03.2010 в 18:31
1

Может быть решена методом критического пути:
1. Найти топологическое упорядочение
2. Найдите критический путь см. [Horowitz 1995], Основы структур данных на C ++, Computer Science Press, Нью-Йорк.

Жадная стратегия (например, Дейкстра) не будет работать, не важно: 1. используйте «max» вместо «min» 2. преобразуйте положительные веса в отрицательные 3. дайте очень большое число M и используйте M-w как вес.

    
ответ дан Monkeycanfly 16.03.2013 в 04:02