Algorithme de Floyd-Warshall
En informatique, l'algorithme de Floyd-Warshall est un algorithme pour déterminer les distances des plus courts chemins entre toutes les paires de sommets dans un graphe orienté et pondéré, en temps cubique au nombre de sommets. Il est parfois appelé algorithme de Roy-Floyd-Warshall car il a été décrit par Bernard Roy en 1959 avant les articles de Floyd et Warshall datant de 1962. L'algorithme de Floyd-Warshall prend en entrée un graphe orienté et valué, décrit par une matrice d'adjacence donnant le poids d'un arc lorsqu'il existe et la valeur ∞ sinon. Le poids d'un chemin entre deux sommets est la somme des poids sur les arcs constituant ce chemin. Les arcs du graphe peuvent avoir des poids négatifs, mais le graphe ne doit pas posséder de circuit de poids strictement négatif. L'algorithme calcule, pour chaque paire de sommets, le poids minimal parmi tous les chemins entre ces deux sommets. L'algorithme de Floyd-Warshall est un exemple de programmation dynamique. On suppose que les sommets de G sont {1, 2, 3, 4, ..., n}. Il résout successivement les sous-problèmes suivants : est le poids minimal d'un chemin du sommet i au sommet j n'empruntant que des sommets intermédiaires dans {1, 2, 3, ..., k} s'il en existe un, et ∞ sinon. On note la matrice des . Pour k = 0, est la matrice d'adjacence définissant G. Maintenant, pour trouver une relation de récurrence, on considère un chemin p entre i et j de poids minimal dont les sommets intermédiaires sont dans {1, 2, 3, ..., k}. De deux choses l'une : soit p n'emprunte pas le sommet k ; soit p emprunte exactement une fois le sommet k (car les circuits sont de poids positifs ou nuls) et p est donc la concaténation de deux chemins, entre i et k et k et j respectivement, dont les sommets intermédiaires sont dans {1, 2, 3, ..., k-1}. L'observation ci-dessus donne la relation de récurrence pour tous i, j et k dans {1, 2, 3, 4..., n}. Ainsi on résout les sous-problèmes par valeur de k croissante. Donnons d'abord une première version d'après l'analyse faite dans la section précédente.
