Модификация алгоритма Дейкстры

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

Вот что я использую:

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

 if (Cost(potential_node) > Cost(current_node) + cost(source , current_node)) then
 cost (potential_node) = cost(current_node) + cost (source, current_node)

Однако, чтобы добраться до обратной стороны, это не работает:

 if (Cost(potential_node) < Cost(current_node) + cost(source , current_node)) then
 cost (potential_node) = cost(current_node) + cost (source, current_node)

Немного запутался, буду очень признателен за отзыв


graph algorithm dijkstra graph-algorithm
person banditKing    schedule 12.10.2012    source источник

Ответы (1)


arrow_upward
6
arrow_downward

проблема с самым длинным путем — это NP-Hard, поэтому известное полиномиальное решение отсутствует.

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

Напомним, что именно это мы и доказываем на алгоритме Дейкстры на каждом шаге (больше "расслаблений" не найдет более короткого пути), но если вы нашли текущий самый длинный путь к вершине с помощью мидификации - это не значит, что он действительно самый длинный - может быть один самый длинный путь, который еще не исследован.

Редактировать — встречный пример, когда это не работает (простите меня, я ужасный ascii-художник)

        A
      /   \
     /     \
    1       2  
   /         \
  B-----5---> C
V = {A,B,C} ;  E = { (A,B,1), (A,C,2), (B,C,5) }

Теперь, начиная с A, этот подход сначала найдет C как "самый длинный путь" и закроет его. Отныне - нет изменений в C по алгоритму Дейкстры, поэтому вы сделаете вывод, что самый длинный путь от A до C имеет длину 2, а путь A->B->C длиннее.

person amit    schedule 12.10.2012