Problème de chemin maximal

Question

Étant donné le graphique non pondéré orienté et le problème est de trouver un chemin simple de longueur maximale (le sommet de début et le sommet de fin ne sont pas fixes). Il peut évidemment être résolu en O (n^2 * 2^n) mais j'ai entendu qu'il existe un algorithme O (n * 2^n) que je ne connais pas. Alors comment le résoudre en O (n * 2^n)? // n = | V |

Answer 1

Si votre problème est vraiment le Longest Path Problem sur un DAG, l'algorithme de Wikipedia est ci-dessous et fonctionne en O (| V | + | E |):

algorithm dag-longest-path is 
    input: 
     Directed acyclic graph G 
    output: 
     Length of the longest path 

    length_to = array with |V(G)| elements of type int with default value 0 

    for each vertex v in topOrder(G) do 
     for each edge (v, w) in E(G) do 
      if length_to[w] <= length_to[v] + weight(G,(v,w)) then 
       length_to[w] = length_to[v] + weight(G, (v,w)) 

    return max(length_to[v] for v in V(G))