Le cas général, algorithme de Ford

Dans le cas général, la seule solution consiste à regarder itérativement les arcs en modifiant les distances jusqu'à ce que la condition du théorème (3.1) soit vérifiée pour chacun d'entre eux. L'algorithme général de Ford (dit Label-correcting) est le suivant :

Cet algorithme est très intéressant car il converge quelle que soit la méthode de sélection de l'arc violant les conditions d'optimalité. Notons que cet algorithme permet de détecter la présence d'un circuit négatif lorsqu'une distance devient inférieure à $-nC$ avec $C = \max\limits_{(\ivj) \in G}\vert\cij\vert$. La preuve de correction cet algorithme est immédiate. En effet, à l'issue de l'algorithme, il suffit de remonter la chaîne des prédécesseurs stockée dans le tableau pred pour obtenir des chemins de $s$ vers tous les autres sommets du graphe uniquement constitués d'arcs vérifiant la condition (3.1). Le théorème (3.3) nous garantissant que de tels chemins sont bien des plus courts chemins de $s$ vers les autres sommets. Sous cette forme directe, l'algorithme de Ford est informatiquement inexploitable. C'est pourquoi l'on a recours à l'algorithme modifié qui repose sur l'utilisation d'une liste de sommets. Cette dernière contient les sommets dont les distances ont été modifiées et qui sont donc susceptibles de créer des arcs violant la condition (3.1).

La même remarque s'impose : la convergence est assurée quelle que soit la politique de gestion de la liste. Les performances de cet algorithme sont très intéressantes dans deux cas particuliers :

Gestion File :

C'est la forme la plus répandue car elle permet, moyennant des astuces algorithmiques non négligeables que nous ne détaillerons pas ici, de détecter les circuits de coût négatif. Les sommets sont retirés dans l'ordre où ils sont introduits dans la liste. En pratique, on insère les sommets en fin de liste pour les retirer en tête de liste. Sa complexité est $O(nm)$.

Gestion Dequeue :

C'est l'algorithme (en pratique !) le plus performant pour résoudre les problèmes de plus court chemin dans le cas général. Si l'on retire toujours les sommets en tête de liste, ils sont insérés en fin de liste lors de leur première insertion et en tête de liste s'ils doivent être examinés une nouvelle fois. Il existe une autre variante qui utilise deux listes couplées l'une à l'autre. Très performantes, ces deux implémentations peuvent néammoins avoir un comportement non polynômial sur des réseaux pathologiques.