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

Question

Я уже решил большинство вопросов, размещенных here, все, кроме самого длинного пути один. Я прочитал статью в Википедии о самых длинных путях, и кажется, что любая легкая проблема, если график был ацикличен, а мой нет.

Как мне решить проблему? Грубая сила, проверяя все возможные пути? Как я даже начинаю это делать?

Я знаю, что это займет ЛОТО на графике с ~ 18000. Но я просто хочу его развить, потому что это необходимо для проекта, и я просто проверю его и покажу его инструктору на графике меньшего масштаба, где время выполнения - всего лишь секунда или два.

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

Answer 1

Решение заключается в том, чтобы переборщить его. Вы можете сделать некоторые оптимизации, чтобы ускорить его, некоторые из них тривиальны, некоторые из них очень сложны. Я сомневаюсь, что вы можете заставить его работать достаточно быстро для 18 000 узлов на настольном компьютере, и даже если вы можете я понятия не имею, как это сделать. Вот как работает bruteforce.

Примечание: Dijkstra и любые другие алгоритмы кратчайшего пути НЕ будут работать для этой проблемы, если вас интересует точный ответ.

Start at a root node *root* 
Let D[i] = longest path from node *root* to node i. D[*root*] = 0, and the others are also 0. 

void getLongestPath(node, currSum) 
{ 
    if node is visited 
     return; 
    mark node as visited; 

    if D[node] < currSum 
     D[node] = currSum; 

    for each child i of node do 
     getLongestPath(i, currSum + EdgeWeight(i, node)); 

    mark node as not visited; 
} 

Давайте запустим его вручную на этом графике: 1 - 2 (4), 1 - 3 (100), 2 - 3 (5), 3 - 5 (200), 3 - 4 (7), 4 - 5 (1000)

Let the root be 1. We call getLongestPath(1, 0); 
2 is marked as visited and getLongestPath(2, 4); is called 
D[2] = 0 < currSum = 4 so D[2] = 4. 
3 is marked as visited and getLongestPath(3, 4 + 5); is called 
D[3] = 0 < currSum = 9 so D[3] = 9. 
4 is marked as visited and getLongestPath(4, 9 + 7); is called 
D[4] = 0 < currSum = 16 so D[4] = 16. 
5 is marked as visited and getLongestPath(5, 16 + 1000); is called 
D[5] = 0 < currSum = 1016 so D[5] = 1016. 
getLongestPath(3, 1016 + 200); is called, but node 3 is marked as visited, so nothing happens. 
Node 5 has no more child nodes, so the function marks 5 as not visited and backtracks to 4. The backtracking will happen until node 1 is hit, which will end up setting D[3] = 100 and updating more nodes. 

Вот как это будет выглядеть итеративно (не проверял, только основная идея):

Let st be a stack, the rest remains unchanged; 
void getLongestPath(root) 
{ 
    st.push(pair(root, 0)); 

    while st is not empty 
    { 
     topStack = st.top(); 
     if topStack.node is visited 
      goto end; 
     mark topStack.node as visited; 

     if D[topStack.node] < topStack.sum 
      D[topStack.node = topStack.sum; 

     if topStack.node has a remaining child (*) 
      st.push(pair(nextchild of topStack.node, topStack.sum + edge cost of topStack.node - nextchild)) 

     end: 
     mark topStack.node as not visited 
     st.pop(); 
    } 
} 

(*) - это немного проблема - вам нужно держать указатель на следующий дочерний элемент для каждого узла, поскольку он может меняться между разными итерациями цикла while и даже сбрасывать себя (указатель сбрасывается, когда вы e topStack.node узел из стека, поэтому обязательно установите его). Это проще всего реализовать в связанных списках, однако вы должны использовать либо списки int[], либо списки vector<int>, чтобы иметь возможность хранить указатели и иметь произвольный доступ, потому что он вам понадобится. Вы можете сохранить, например, next[i] = next child of node i in its adjacency list и обновить это соответственно. Возможно, у вас могут быть случаи с краем и, возможно, потребуется различная ситуация end:: обычная и одна, которая происходит при посещении уже посещенного узла, и в этом случае указатели не требуют сброса. Возможно, переместите условие посещения, прежде чем вы решите нажать что-то в стеке, чтобы этого избежать.

Посмотрите, почему я сказал, что вам не следует беспокоиться? :)