Comment faire pour trouver les plus long chemin dans un graphe cyclique entre deux noeuds?

Question

Je l'ai déjà résolu la plupart des questions posées ici , tout sauf le plus long chemin. J'ai lu l'article de Wikipedia sur les chemins les plus longs et il semble un problème facile si le graphique était acyclique, ce qui est à moi pas.

Comment puis-je résoudre le problème? Brute force, en vérifiant tous les chemins possibles? Comment puis-je même de commencer à le faire?

Je sais que ça va prendre beaucoup sur un graphique avec ~ 18000. Mais je veux juste développer de toute façon, car il est nécessaire pour le projet et je vais juste le tester et le montrer à l'instructeur sur un petit graphique à grande échelle où le temps d'exécution est juste une seconde ou deux.

Au moins je l'ai fait toutes les tâches nécessaires et j'ai une preuve de concept en cours d'exécution cela fonctionne mais il n'y a pas de meilleure façon sur les graphes cycliques. Mais je n'ai pas la moindre idée où commencer à vérifier tous ces chemins ...

Answer 1

La solution est de force brutale il. Vous pouvez faire quelques optimisations pour accélérer, certains sont trivial, certains sont très compliquées. Je doute que vous pouvez l'obtenir pour travailler assez rapide pour 18 000 nœuds sur un ordinateur de bureau, et même si vous je peux avoir aucune idée de comment. Voici comment le bruteforce fonctionne cependant.

Remarque:. Dijkstra et l'un des autres algorithmes de plus court chemin ne fonctionnera pas pour ce problème si vous êtes intéressé par une réponse exacte

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

run Let la main sur ce graphique: 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.

Voici à quoi il ressemblerait itérativement (non testé, juste une idée de base):

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

(*) - c'est un peu un problème - vous devez garder un pointeur vers le prochain enfant pour chaque nœud, car il peut changer entre les différentes itérations de la boucle tout et même se remet à zéro (le pointeur se remet à zéro lorsque vous pop le noeud topStack.node de la pile, alors assurez-vous de le réinitialiser). Ceci est plus facile à mettre en œuvre sur les listes liées, mais vous devez utiliser soit des listes de int[] ou des listes de vector<int>, afin de pouvoir stocker les pointeurs et ont un accès aléatoire, parce que vous en aurez besoin. Vous pouvez par exemple garder next[i] = next child of node i in its adjacency list et mise à jour en conséquence. Vous pourriez avoir quelques cas de pointe et peut-être besoin de différentes situations de end:: une normale et qui se produit lorsque vous visitez un nœud déjà visité, dans ce cas, les pointeurs ne doivent pas être remis à zéro. Peut-être déplacer l'état visité avant de décider de pousser quelque chose sur la pile pour éviter cela.

Voyez pourquoi je l'ai dit que vous ne devriez pas la peine? :)