Présentation : En informatique, l’algorithme de Floyd-Warshall est un algorithme pour déterminer la distance du plus court chemin entre toutes les paires de sommets dans un graphe orienté et pondéré.
Histoire : L’algorithme de Floyd-Warshall 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. Il devrait donc être simplement appelé algorithme de Roy par argument d’antériorité.
L’algorithme : 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 sommet, le poids minimal parmi tous les chemins entre ces deux sommets.
Exemple:
Voici le diagramme sur lequel nous allons exécuter l’algorithme:
Pour k=0, les seuls chemins sont les arcs directs. Le plus court est A->C
Pour K=1, on regarde les chemins ou le sommet A peut être un sommet intermédiaire. On trouve le chemin D->A->C qui est moins lourd que D->C.
Pour k=2, maintenant, le sommet D peut être un sommet intermédiaire. Notons que le chemins B->D->C n’est pas pris en compte n’est pas considéré car c’est D->A->C qui est le chemin le plus léger obtenu à l’itération précédente et non D->C.
Pour K=3:
Pour k=4 On a trouvé le plus court chemin entre tous les sommets:
Graphes et Algorithmes 