Come trovare il percorso più lungo in un grafico ciclico tra due nodi?

Question

Ho già risolto la maggior parte delle domande pubblicate here, tutte tranne il percorso più lungo. Ho letto l'articolo di Wikipedia sui percorsi più lunghi e sembra un problema facile se il grafico fosse aciclico, il mio non lo è.

Allora come risolvo il problema? Forza bruta, controllando tutti i possibili percorsi? Come posso iniziare a farlo?

So che ci vorrà molto su un grafico con ~ 18000. Ma voglio solo svilupparlo comunque, perché è richiesto per il progetto e lo testerò e lo mostrerò all'istruttore su un grafico su scala più piccola dove il tempo di esecuzione è solo di un secondo o due.

Almeno ho eseguito tutte le attività richieste e ho una dimostrazione di funzionamento che funziona, ma non c'è modo migliore sui grafici ciclici. Ma non ho idea di dove iniziare a controllare tutti questi percorsi ...

Answer 1

La soluzione è quella di forza bruta. Puoi fare alcune ottimizzazioni per accelerarlo, alcune sono banali, alcune sono molto complicate. Dubito che tu possa farlo funzionare abbastanza velocemente per 18.000 nodi su un computer desktop, e anche se tu non posso avere idea di come. Ecco come funziona la bruteforce.

Nota: Dijkstra e qualsiasi altro algoritmo di percorso più breve NON funzionano per questo problema se si è interessati a una risposta esatta.

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

Corriamo a mano su questo grafico: 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. 

Ecco come apparirebbe in modo iterativo (non testato, solo un idea di 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(); 
    } 
} 

(*) - questo è un po 'un problema - devi tenere un puntatore al prossimo figlio per ogni nodo, dato che può cambiare tra diverse iterazioni del ciclo while e persino resettarsi (il puntatore si resetta quando fai il pop e il nodo topStack.node fuori pila, quindi assicuratevi di reimpostarlo). Questo è più facile da implementare negli elenchi concatenati, tuttavia è necessario utilizzare gli elenchi int[] o gli elenchi vector<int>, in modo da poter memorizzare i puntatori e avere accesso casuale, poiché ne avrai bisogno. È possibile mantenere ad esempio next[i] = next child of node i in its adjacency list e aggiornarlo di conseguenza. Potrebbero esserci alcuni casi limite e potrebbero essere necessarie diverse situazioni end:: una normale e una che accade quando si visita un nodo già visitato, nel qual caso non è necessario reimpostare i puntatori. Forse spostare la condizione visitata prima di decidere di spingere qualcosa in pila per evitare questo.

Scopri perché ho detto che non dovresti preoccuparti? :)