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

Наясно съм с алгоритъма за най-краткия път на Дейкстра. Въпреки това, ако го модифицирам така, че вместо да намери най-краткия път, той ще намери най-дългия път, използвайки алчен алгоритъм. Какво трябва да направя с кода по-долу:

Ето какво използвам:

като функция за сравнение, за да изберете правилния възел във версията на най-краткия път:

 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 и следователно няма известно полиномно решение.

Предложената модификация не работи, защото когато алгоритъмът на dijkstra маркира възел като "затворен", това означава - никога няма да има по-кратък път до него. Твърдението не е вярно, когато се опитвате да го направите за най-дългия път, ако сте затворили възел - това не означава, че вече няма път към него.

Спомнете си, че това е точно това, което доказваме на алгоритъма на Дейкстра на всяка стъпка (повече „релаксации“ няма да намерят по-къс път), но ако намерите текущ най-дълъг път до връх, използвайки midification - това не означава, че наистина е така най-дългият - може да има един най-дълъг път, който все още не е проучен.

Редактиране - контрапример, когато не работи (простете ми, аз съм ужасен 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