Wie findet man den längsten Pfad in einem zyklischen Graph zwischen zwei Knoten?

Question

Ich habe schon die meisten Fragen here gelöst, alle außer dem längsten Pfad eins. Ich habe den Wikipedia-Artikel über die längsten Pfade gelesen und es scheint ein einfaches Problem zu sein, wenn der Graph azyklisch ist, was meiner nicht ist.

Wie löse ich das Problem dann? Brute force, indem alle möglichen Wege überprüft werden? Wie mache ich das überhaupt?

Ich weiß, es wird eine Menge auf einem Graph mit ~ 18000 nehmen. Aber ich möchte es trotzdem entwickeln, weil es für das Projekt benötigt wird und ich werde es einfach testen und es dem Instruktor in einem kleineren Graphen zeigen, wo die Ausführungszeit nur ein oder zwei Sekunden beträgt.

Zumindest habe ich alle Aufgaben benötigt und ich habe einen laufenden Beweis des Konzepts, dass es funktioniert, aber es gibt keinen besseren Weg auf zyklische Graphen. Aber ich habe keine Ahnung, wo ich anfangen soll, alle diese Wege zu überprüfen ...

Answer 1

Die Lösung ist, es brutal zu zwingen. Sie können einige Optimierungen durchführen, um es zu beschleunigen, einige sind trivial, einige sind sehr kompliziert. Ich bezweifle, dass Sie es schnell genug für 18 000 Knoten auf einem Desktop-Computer arbeiten können, und selbst wenn Sie können ich keine Ahnung, wie. So funktioniert die Bruteforce jedoch.

Hinweis: Dijkstra und alle anderen Algorithmen für den kürzesten Pfad funktionieren NICHT für dieses Problem, wenn Sie an einer genauen Antwort interessiert sind.

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; 
} 

Sagen wir es von Hand auf dieser Grafik laufen: 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. 

Hier ist, wie es iterativ aussehen würde (nicht getestet, nur eine grundlegende Idee):

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(); 
    } 
} 

(*) - Dies ist ein kleines Problem - Sie müssen einen Zeiger auf das nächste Kind für jeden Knoten halten, da es zwischen verschiedenen Iterationen der while-Schleife wechseln und sich selbst zurücksetzen kann (der Zeiger setzt sich selbst zurück, wenn Sie die Taste drücken) e topStack.node Knoten vom Stapel, also stellen Sie sicher, dass Sie ihn zurücksetzen). Dies ist am einfachsten in verketteten Listen zu implementieren, aber Sie sollten entweder int[] Listen oder vector<int> Listen verwenden, um die Zeiger zu speichern und wahlfreien Zugriff zu haben, weil Sie es brauchen. Sie können zum Beispiel next[i] = next child of node i in its adjacency list beibehalten und das entsprechend aktualisieren. Sie haben möglicherweise einige Randfälle und müssen möglicherweise verschiedene end: Situationen: eine normale und eine, die geschieht, wenn Sie einen bereits besuchten Knoten besuchen, in diesem Fall müssen die Zeiger nicht zurückgesetzt werden. Verschiebe den Zustand vielleicht, bevor du etwas auf den Stapel schiebst, um dies zu vermeiden.

Sehen Sie, warum ich sagte, Sie sollten nicht stören? :)