Algorithme de Floyd‑Warshall : calcul de toutes les distances minimales en O(n³)

Introduction

L’algorithme de Floyd‑Warshall est un classique de l’informatique théorique. Il calcule, en une seule passe, la distance minimale entre chaque paire de sommets d’un graphe orienté ou non, pondéré (poids positifs ou négatifs, à condition qu’il n’y ait pas de cycle de poids négatif). Cette capacité le rend indispensable pour les certifications qui portent sur les graphes, les algorithmes dynamiques ou la complexité algorithmique.

Principe de l’algorithme

L’idée fondamentale repose sur la programmation dynamique. On considère une matrice dist[i][j] qui représente la meilleure distance connue entre le sommet i et le sommet j après l’introduction d’un sous‑ensemble de sommets intermédiaires. Le processus s’articule autour de trois boucles imbriquées :

1. Initialisation : dist[i][j] vaut le poids de l’arête directe i→j s’il existe, sinon ∞. La diagonale dist[i][i] est mise à 0.
2. Itération : pour chaque sommet k comme intermédiaire, on teste si le chemin i → k → j améliore la distance actuelle :

   dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
   

3. Détection de cycles négatifs : après la dernière passe, si dist[i][i] < 0 pour un sommet i, le graphe contient un cycle de poids négatif.

La complexité temporelle est O(V³) (où V est le nombre de sommets) et la complexité mémoire O(V²).

Implémentation en Python

Voici une version concise et idiomatique, adaptée aux exercices de certification :

import math
from typing import List, Tuple

def floyd_warshall(vertices: int, edges: List[Tuple[int, int, int]]) -> List[List[float]]:
    """Retourne la matrice des plus courtes distances.

    Args:
        vertices: nombre de sommets du graphe (numérotés de 0 à vertices-1).
        edges: liste d'arêtes sous la forme (src, dst, poids).
    """
    # Initialisation
    dist = [[math.inf] * vertices for _ in range(vertices)]
    for i in range(vertices):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = min(dist[u][v], w)  # garde le poids minimal en cas de multi‑arêtes

    # Boucle principale
    for k in range(vertices):
        for i in range(vertices):
            # petite optimisation : ignorer les i dont dist[i][k] est inf
            if dist[i][k] == math.inf:
                continue
            for j in range(vertices):
                if dist[k][j] == math.inf:
                    continue
                new_dist = dist[i][k] + dist[k][j]
                if new_dist < dist[i][j]:
                    dist[i][j] = new_dist

    # Détection de cycles négatifs
    for i in range(vertices):
        if dist[i][i] < 0:
            raise ValueError("Graphe contenant un cycle de poids négatif")

    return dist

# Exemple d’usage
if __name__ == "__main__":
    V = 4
    E = [
        (0, 1, 5), (0, 3, 10),
        (1, 2, 3), (2, 3, 1),
        (3, 1, -2)
    ]
    try:
        d = floyd_warshall(V, E)
        for row in d:
            print(row)
    except ValueError as e:
        print(e)

Points clés de l’implémentation

• math.inf représente l’infini. Il évite les dépassements d’entier lorsqu’on additionne des poids inconnus.
• La double vérification if dist[i][k] == math.inf et if dist[k][j] == math.inf réduit le nombre d’opérations inutiles, ce qui améliore les performances sur les graphes clairsemés.
• La fonction lève une exception dès qu’un cycle négatif est détecté, ce qui correspond à la plupart des exigences d’examen où la robustesse est évaluée.

Optimisations et cas d’usage

Utilisation de numpy

Sur des graphes de taille moyenne (quelques centaines de sommets), remplacer les listes Python par des numpy.ndarray accélère le calcul grâce aux opérations vectorisées :

import numpy as np

def floyd_warshall_numpy(dist: np.ndarray) -> np.ndarray:
    n = dist.shape[0]
    for k in range(n):
        # broadcasting : dist[:, k][:, None] + dist[k, :]
        dist = np.minimum(dist, dist[:, k][:, None] + dist[k, :])
    return dist

Cette version ne gère pas automatiquement la détection de cycles négatifs, mais elle illustre comment exploiter la puissance du calcul matriciel.

Quand choisir Floyd‑Warshall ?

• Petits à moyens graphes (V ≤ 500) où la simplicité du code prime sur la complexité asymptotique.
• Analyse de réseaux où l’on a besoin de toutes les distances (ex. : calcul du diamètre, centralité de proximité).
• Pré‑traitement d’algorithmes plus avancés, comme la recherche de chemins disjoints ou les algorithmes de flot max.

Alternatives

Pour des graphes très denses ou très grands, on privilégiera généralement :

• Algorithme de Johnson (O(V·E·log V)) qui combine Dijkstra et re‑pondération des poids.
• Algorithme de Dijkstra exécuté V fois, efficace lorsque les poids sont non négatifs. Ces alternatives sont à connaître pour les questions de comparaison de complexité dans les certifications.

Conclusion

L’algorithme de Floyd‑Warshall reste une référence incontournable pour maîtriser la programmation dynamique appliquée aux graphes. Sa mise en œuvre en Python est courte, lisible et facilement extensible (détection de cycles, utilisation de numpy, gestion des graphes multi‑arêtes). Savoir expliquer son principe, son coût et ses limites constitue un avantage certain lors des examens de certification orientés algorithmes.