Comment calculer le chemin critique d'un graphe acyclique directionnel?

Question

Quelle est la meilleure façon (en termes de performances) de calculer le chemin critique d'un graphe directionnel acyclique lorsque les noeuds du graphe ont un poids?

Par exemple, si j'ai la structure suivante:

  Node A (weight 3) 
      /   \ 
    Node B (weight 4)  Node D (weight 7) 
    /    \ 
Node E (weight 2) Node F (weight 3) 

Le chemin critique doit être A> B> F (poids total: 10)

Answer 1

Je n'ai pas la moindre idée de « critique chemins ", mais je suppose que vous voulez dire this. Trouver le plus long chemin dans un graphe acyclique avec des poids n'est possible qu'en parcourant l'arbre entier et ensuite en comparant les longueurs, car on ne sait jamais vraiment comment le reste de l'arbre est pondéré. Vous pouvez trouver plus sur la traversée de l'arbre au Wikipedia. Je suggère, vous allez avec la traversée pré-commande, car il est facile et simple à mettre en œuvre.

Si vous souhaitez interroger souvent, vous pouvez également augmenter les bords entre les noeuds avec des informations sur le poids de leurs sous-arbres lors de l'insertion. Ceci est relativement bon marché, tandis que la traversée répétée peut être extrêmement coûteuse.

Mais il n'y a rien pour vraiment vous sauver d'une traversée complète si vous ne le faites pas. L'ordre n'a pas vraiment d'importance, tant que vous faites traverser et ne passez jamais deux fois le même chemin.

Answer 2

Je résoudrais cela avec la programmation dynamique. Pour trouver le coût maximum de S à T:

• trier les noeuds topologiquement du graphe S = x_0, x 1, ..., x_n = T. (Ignorer les noeuds qui peuvent atteindre S ou être atteint de T.)
• le coût maximal de S à S est le poids de S.
• en supposant que vous avez calculé le coût maximal de S à x_i pour tout i < k, le coût maximal de S à x_k est le coût de x_k plus le coût maximum pour n'importe quel noeud avec un bord à x_k.

Answer 3

Essayez la méthode A *.

A* Search Algorithm

A la fin, pour faire face aux feuilles, il suffit de faire tous les conduire à un dernier point, définir comme objectif.

Answer 4

Il y a un papier qui prétend avoir un algorithme pour cela: "Chemin critique dans un réseau d'activité avec des contraintes de temps". Malheureusement, je n'ai pas trouvé de lien vers une copie gratuite. Bref, je ne peux que soutenir l'idée de modifier http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm ou http://en.wikipedia.org/wiki/A *

MISE À JOUR: Je m'excuse pour le formatage merdique - le moteur de démarque côté serveur est apparemment cassé.

Answer 5

Ma première réponse alors s'il vous plaît excuser pour toute chose non standard par la culture de stackoverflow.

Je pense que la solution est simple. Il suffit de nier les poids et d'exécuter le plus court chemin classique pour DAG (modifié pour les poids de sommets bien sûr). Cela devrait fonctionner assez vite.

Je pense que cela devrait fonctionner comme lorsque vous annulez les poids, le plus grand deviendra le plus petit, le second plus grand sera le second plus petit et ainsi de suite que si puis -a < -b . DAG en cours d'exécution devrait suffire car il trouvera la solution pour le chemin le plus petit de la négation et ainsi trouver le chemin le plus long pour le chemin d'origine