chemin critique

chemin critique

Dans un graphe orienté et valué représentant différentes opérations à réaliser pour accomplir une tâche, chemin dont la valeur est optimale (maximale ou minimale selon le contexte) entre deux sommets appelés le début et la fin de la tâche.

Exemple

Dans le graphe orienté et valué ci-dessous, le chemin critique de valeur maximale est le chemin D-1-6-8-9-F qui a une valeur de 14.

Dans le graphe orienté et valué ci-dessus, le chemin critique de valeur minimale est le chemin D-3-F qui a une valeur de 7.