Wie der längsten Weg in einem zyklischen Graph zwischen zwei Knoten finden?

Question

Ich löste bereits die meisten Fragen hier geschrieben , alle bis auf einen der längsten Weg. Ich habe den Wikipedia-Artikel über längste Wege lesen und es scheint, jedes einfaches Problem, wenn der Graph azyklisch war, die Mine nicht.

Wie löse ich das Problem dann? Brute-Force, durch alle möglichen Pfade überprüft? Wie beginne ich auch das zu tun?

Ich weiß, dass es viel mit ~ 18000 auf einem Graph nehmen wird. Aber ich will nur, es trotzdem zu entwickeln, weil es für das Projekt erforderlich ist, und ich werde es einfach testen und zeige es den Lehrer in einem kleineren Maßstab Diagramm, in dem die Ausführungszeit ist nur eine oder zwei Sekunden.

Mindestens habe ich alle Aufgaben benötigt, und ich habe einen laufenden Proof of Concept, dass es funktioniert, aber es gibt keinen besseren Weg, auf zyklische Graphen. Aber ich habe keine Ahnung, wo zu beginnen, alle diese Pfade Überprüfung ...

Answer 1

Die Lösung ist Kraft es Brute. Sie können einige Optimierungen tun um ihn zu beschleunigen, einige sind trivial, einige sind sehr kompliziert. Ich bezweifle, Sie bekommen können es für 18 000 Knoten auf einem Desktop-Computer schnell genug zu arbeiten, und selbst wenn Sie kann ich habe keine Ahnung wie. Hier ist, wie die Brute-Force funktioniert aber.

. Hinweis: Dijkstra und keines des anderen kürzesten Weg Algorithmen wird nicht funktionieren für dieses Problem, wenn Sie in einer exakten 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;
}

Lassen Sie uns laufen sie von Hand auf dieser Grafik: 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 Grundidee):

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

(*) - das ist ein bisschen ein Problem - Sie für jeden Knoten einen Zeiger auf das nächste Kind zu halten haben, da es zwischen den verschiedenen Iterationen der while-Schleife und sogar selbst zurücksetzen (die Zeiger setzt sich ändern kann, wenn pop Sie den topStack.node Knoten aus dem Stapel, so stellen Sie sicher, dass es zurückgesetzt). Dies ist am einfachsten auf verkettete Listen implementieren, jedoch sollten Sie entweder int[] Listen oder vector<int> Listen verwenden, um in der Lage sein, die Zeiger zu speichern und mit wahlfreiem Zugriff haben, weil Sie es brauchen. Sie können, dass entsprechend zum Beispiel next[i] = next child of node i in its adjacency list und Update halten. Sie könnten einige Grenzfälle haben und auf unterschiedliche end: Situationen benötigen: eine normale und eine, wenn Sie einen bereits besuchten Knoten besuchen geschieht, in welchem ??Fall die Zeiger nicht zurückgesetzt sein müssen. Vielleicht den besuchten Zustand bewegen, bevor Sie etwas auf dem Stapel zu schieben, dies zu vermeiden.

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