45. Plus Court Chemin entre Toutes Paires : Introduction à Floyd-Warshall

Parfois, nous n'avons pas seulement besoin du plus court chemin à partir d'une source, mais du plus court chemin entre chaque paire de sommets. C'est le problème du Plus Court Chemin entre Toutes Paires (All-Pairs Shortest Path).

Algorithme de Floyd-Warshall

Floyd-Warshall est un algorithme classique qui utilise la Dynamic Programming (couverte bientôt) pour résoudre ce problème efficacement.

Concept

Il considère chaque sommet possible k comme un nœud intermédiaire pour les chemins entre deux autres nœuds i et j.

Pour chaque paire de sommets (i, j), il vérifie si passer par un sommet intermédiaire k est plus court que le chemin le plus court connu actuellement.

python for k in range(V): for i in range(V): for j in range(V): dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

• Complexité Temporelle : O(V³). Il est efficace lorsque V est relativement petit (des centaines), mais moins pour les graphes massifs.