Comment trouver le chemin le plus long dans un graphique cyclique entre deux nœuds?

Question

J'ai déjà résolu la plupart des questions postées here, toutes sauf la plus longue. J'ai lu l'article de Wikipédia sur les plus longs chemins et il semble que ce soit facile si le graphique était acyclique, ce qui n'est pas le cas.

Comment puis-je résoudre le problème? Force brute, en vérifiant tous les chemins possibles? Comment est-ce que je commence même à faire ça?

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

Au moins, j'ai fait toutes les tâches requises et j'ai une preuve de concept qui fonctionne, mais il n'y a pas de meilleure façon sur les graphiques cycliques. Mais je ne sais pas par où commencer à vérifier tous ces chemins ...

Answer 1

La solution est de le forcer brutalement. Vous pouvez faire quelques optimisations pour l'accélérer, certaines sont triviales, d'autres très compliquées. Je doute que vous pouvez le faire fonctionner assez rapidement pour 18 000 nœuds sur un ordinateur de bureau, et même si vous ne pouvez pas avoir aucune idée de comment. Voici comment la bruteforce fonctionne cependant.

Remarque: Dijkstra et l'un des autres algorithmes de chemin le plus court ne fonctionneront 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; 
} 

Lançons 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 sur l'enfant suivant pour chaque nœud, car il peut changer entre différentes itérations de la boucle while et même se réinitialiser (le pointeur se réinitialise lorsque vous e topStack.node noeud hors de la pile, alors assurez-vous de le réinitialiser). Ceci est plus facile à implémenter sur des listes liées, cependant vous devez utiliser soit des listes int[] soit des listes vector<int>, afin de pouvoir stocker les pointeurs et avoir un accès aléatoire, car vous en aurez besoin. Vous pouvez conserver par exemple next[i] = next child of node i in its adjacency list et mettre à jour en conséquence. Vous pouvez avoir des cas de contour et avoir besoin de situations différentes: une situation normale et une autre qui se produit lorsque vous visitez un nœud déjà visité, auquel cas les pointeurs n'ont pas besoin d'être réinitialisés. Peut-être déplacer la condition visitée avant de décider de pousser quelque chose sur la pile pour éviter cela.

Voyez pourquoi j'ai dit que vous ne devriez pas déranger? :)