La terminaison

Comme pour tout algorithme, il faut étudier sa terminaison. Le coût d'une solution est strictement positif. Si chaque itération amène un gain non nul, l'algorithme s'achève en un nombre fini d'itérations. Il ne peut donc y avoir un problème que si une itération ne réduit pas le coût de la solution. Cette situation se produit lorsque l'arc sortant est de poids nul. On dit qu'une telle itération est dégénérée.

 

Figure: Une itération dégénérée

Il y a cyclage si l'algorithme se "bloque" sur une suite infinie d'itérations dégénérées. S'il n'y a pas cyclage, la terminaison de l'algorithme est assurée.