L'algorithme de Floyd-Warshall

Exemple de Floyd-Warshall

Présentation :

En informatique, l'algorithme de Floyd-Warshall va nous permettre de calculer le plus cours chemins, afin de se rendre d'un point A à un point B.

Remarque :Il à besoin d'une matrice adjacente qui représente un graphe orienté et valué (chaque arcs possède un poids). Avec cette matrice, il va pouvoir calculer la valeur de tous les chemins possibles et prendre seulement plus court.

Graphe orienté, connexe et valué

Pseudo code de l'algorithme de Floyd-Warshall :

procedure FloydWarshall (G : matrice n x n)

W := G

for k:= 1 to n

for i:= 1 to n

for j:= 1 to n

W(ij):= min(W(i,j),W(i,k)+W(k,j).