Chemin le plus long simple dans des graphiques cycliques clairs

Question

Soit: un graphique dirigé non pondéré (G = (E, V)), qui peut contenir n'importe quel nombre de cycles.

Objectif: Pour tous les sommets Je veux le plus long chemin simple à un sommet cible X en V

algorithme Idée:

For each v in V 
    v.distanceToTarget = DepthFirstSearch(v) 
Next 

DepthFirstSearch(v as Vertex) 
    if v = target then 
    'Distance towards target is 0 for target itself 
    return 0 
    elseif v.isVisitedInCurrentDFSPath then 
    'Cycle found -> I wont find the target when I go around in cycles -> abort 
    return -infinity 
    else 
    'Return the maximum Distance of all Successors + 1 
    return max(v.Successors.ForEach(Function(v) DepthFirstSearch(v))) + 1 
    end if 

Est-ce correct pour tous les cas? (En supposant que la cible peut être atteinte à partir de chaque sommet)

Le nombre d'arêtes dans mes graphiques est très petit. Supposons | E | < = 3 * | V | tient. Comment calculer la complexité moyenne en temps?

Merci!

Answer 1

La complexité temporelle concerne les valeurs qui influencent le plus votre temps d'exécution. Dans votre cas, vous évaluez tous les chemins possibles entre v et la cible. C'est essentiellement O (nombre de routes). Maintenant, vous devez comprendre comment exprimer le nombre de toutes les routes possibles en termes de E et V.

Résultat le plus probable avec quelque chose comme O (exp (E)) ou O (exp (V)) parce que le nombre de les routes passant par chaque noeud/sommet vont exponentiellement lorsque vous ajoutez de nouvelles routes possibles.

EDIT: J'ai manqué un détail que vous demandiez pour la complexité moyenne du temps qui signifierait la complexité amortie. Mais comme votre algorithme évalue toujours toutes les routes possibles, la complexité du cas le plus défavorable est la même que la complexité moyenne.