Plus courts chemins entre toutes les paires de sommets dans un graphe orienté et pondéré - Algorithme Floyd-Warshall

Algorithme Floyd-Warshall

Le problème des plus courts chemins est un pilier de la théorie des graphes. Jusqu'ici, nous avons étudié des algorithmes à source unique :

• Dijkstra
• \(A^{*}\)

L'algorithme de Floyd-Warshall change de paradigme. Son objectif est de calculer simultanément les distances minimales pour tous les couples de sommets \((i,j)\). C'est un outil indispensable pour l'analyse de réseaux denses (où le nombre d'arêtes \(A\) est proche de \(S^2\)) et pour la détection de structures pathologiques comme les cycles de poids négatifs.

Cadre d'étude et Formalisation

Soit \(G=(S,A, w)\) un graphe orienté pondéré à \(n\) sommets, où chaque arête \((i,j)\) possède un poids \(w_{i,j} \in \mathbb{R}\).

• Le graphe peut contenir des arcs de poids négatifs.
• Le graphe ne doit pas contenir de cycle de poids négatif. Si un tel cycle existe, la notion de "plus court chemin" s'effondre car on peut diminuer la distance indéfiniment en bouclant.

On utilise une matrice d'adjacence A de taille \(n\times n\) :

\[ A_{i, j} = \begin{cases} 0 & \text{si } i = j \\ w_{i, j} & \text{si } (i, j) \in A\\ \infty & \text{sinon}\\ \end{cases} \]

Le principe : Programmation dynamique

L'idée géniale de Floyd-Warshall est d'introduire une contrainte de passage. On numérote les sommets de \(1\) à \(n\).

Pour calculer \(d_k(i,j)\), nous regardons si l'introduction du sommet \(k\) permet d'améliorer le chemin trouvé à l'étape \(k-1\).

1. Le sommet \(k\) n'est pas utile : Le meilleur chemin reste celui trouvé avec \(\{1, \dots, k-1\}\). La distance est : \(d_{k-1}(i,j)\)
2. Le sommet \(k\) améliore le chemin : Le chemin passe par \(k\). Il se décompose alors en un chemin de \(i\) à \(k\) et un chemin de \(k\) à \(j\), utilisant uniquement des intermédiaires dans \(\{1, \dots, k-1\}\). La distance est : \(d_{k-1}(i, k) + d_{k-1}(k, j)\)

Donc :

\[ d_k(i, j) = \min (d_{k-1}(i,j), d_{k-1}(i, k) + d_{k-1}(k, j)) \]

Interprétation

Imaginez que les sommets sont des villes. L'algorithme de Floyd-Warshall débloque les villes une par une pour servir de hubs :

• \(k=1\) : On regarde si passer par la ville n°1 permet de raccourcir des trajets.
• \(k=2\) : On regarde si passer par la ville n°2 permet de raccourcir des trajets (en sachant qu'on peut déjà utiliser la ville n°1 si besoin).
• ...
• \(k=n\) : Toutes les villes sont autorisées comme escales. On a alors la distance minimale absolue.

Algorithme et implémentation

Représentation des distances

On utilise une matrice de distances :

\[ D = (d(i,j))_{1 \le i, j \le n} \]

où :

• \(d(i,j) =\) coût minimal pour aller de \(i\) vers \(j\)

\[ D_{i, j} = \begin{cases} 0 & \text{si } i = j \\ w_{i, j} & \text{si } (i, j) \in A\\ \infty & \text{sinon}\\ \end{cases} \]

Cette matrice correspond exactement au graphe sans sommets intermédiaires.

On n'a pas besoin de stocker toutes les matrices \(d_k\) : on met à jour en place une seule matrice \(D\).

Exemple détaillé

On considère le graphe suivant et on effectue l'algorithme de Floyd-Warshall.

Pour faciliter les calculs, associons les sommets aux indices : \(1:A,\quad 2:B,\quad 3:C,\quad 4:D,\quad 5:E,\quad 6:F,\quad 7:G\).

Étape 0 : Initialisation - Matrice \(d_0\) (aucun sommet intermédiaire autorisé)

On remplit la matrice avec les poids directs des arêtes. On met \(0\) sur la diagonale et \(\infty\) là où il n'y a pas d'arête.

Pour chaque étape \(k\), nous allons autoriser le sommet \(k\) comme intermédiaire et mettre à jour la matrice.

Étape 1 : \(k = 0\) (intermédiaire A autorisé) - Matrice \(d_1\)

On regarde si passer par le sommet A (indice 0) permet d'obtenir des chemins plus courts.

Pour une paire \((i,j)\), la nouvelle distance possible via A est : \(d(i,0) + d(0,j)\).

Paires améliorées :

• \(d_1(B, C)\) = \(\min(d_0(B, C), d_0(B, A) + d_0(A, C))\)
  \(d_0(B, C) = \infty\), \(d_0(B, A) = 3\), \(d_0(A, C) = 4\)
  \(3 + 4 = 7\) → \(d_1(B, C) = 7\)
• \(d_1(B, D)\) = \(\min(d_0(B, D), d_0(B, A) + d_0(A, D))\)
  \(d_0(B, D) = 13\), \(d_0(B, A) = 3\), \(d_0(A, D) = 1\)
  \(3 + 1 = 4\) → \(d_1(B, D) = 4\) (amélioration)
• \(d_1(C, D)\) = \(\min(d_0(C, D), d_0(C, A) + d_0(A, D))\)
  \(d_0(C, D) = 9\), \(d_0(C, A) = 4\), \(d_0(A, D) = 1\)
  \(4 + 1 = 5\) → \(d_1(C, D) = 5\) (amélioration)
• \(d_1(B, B)\) = \(\min(0, d_0(B, A) + d_0(A, B)) = \min(0, 3 + 3 = 6)\) → 0 (inchangé)
• \(d_1(C, C)\) = \(\min(0, d_0(C, A) + d_0(A, C)) = \min(0, 4 + 4 = 8)\) → 0 (inchangé)

Matrice \(d_1\) après étape 1 :

Étape 2 : \(k = 1\) (intermédiaire B autorisé) - Matrice \(d_2\)

On autorise maintenant le sommet B (indice 1) comme intermédiaire supplémentaire. On utilise la matrice \(d_1\) comme point de départ.

Pour une paire \((i,j)\), la nouvelle distance possible via B est : \(d(i,1) + d(1,j)\).

Paires améliorées :

• \(d_2(A, E)\) = \(\min(d_1(A, E), d_1(A, B) + d_1(B, E))\)
  \(d_1(A, E) = \infty\), \(d_1(A, B) = 3\), \(d_1(B, E) = 6\)
  \(3 + 6 = 9\) → \(d_2(A, E) = 9\)
• \(d_2(C, E)\) = \(\min(d_1(C, E), d_1(C, B) + d_1(B, E))\)
  \(d_1(C, E) = \infty\), \(d_1(C, B) = 7\), \(d_1(B, E) = 6\)
  \(7 + 6 = 13\) → \(d_2(C, E) = 13\)
• \(d_2(D, E)\) = \(\min(d_1(D, E), d_1(D, B) + d_1(B, E))\)
  \(d_1(D, E) = 10\), \(d_1(D, B) = 4\), \(d_1(B, E) = 6\)
  \(4 + 6 = 10\) → \(d_2(D, E) = 10\) (inchangé)
• \(d_2(C, A)\) déjà 4, via B : \(7 + 3 = 10\) → inchangé
• \(d_2(C, C)\) = 0, via B : \(7 + 7 = 14\) → inchangé

Matrice \(d_2\) après étape 2 :

Étape 3 : \(k = 2\) (intermédiaire C autorisé) - Matrice \(d_3\)

On autorise maintenant le sommet C (indice 2) comme intermédiaire supplémentaire. On utilise la matrice \(d_2\).

Pour une paire \((i,j)\), la nouvelle distance possible via C est : \(d(i,2) + d(2,j)\).

Paires améliorées :

• \(d_3(A, F)\) = \(\min(d_2(A, F), d_2(A, C) + d_2(C, F))\)
  \(d_2(A, F) = \infty\), \(d_2(A, C) = 4\), \(d_2(C, F) = 2\)
  \(4 + 2 = 6\) → \(d_3(A, F) = 6\)
• \(d_3(B, F)\) = \(\min(d_2(B, F), d_2(B, C) + d_2(C, F))\)
  \(d_2(B, F) = \infty\), \(d_2(B, C) = 7\), \(d_2(C, F) = 2\)
  \(7 + 2 = 9\) → \(d_3(B, F) = 9\)
• \(d_3(D, F)\) = \(\min(d_2(D, F), d_2(D, C) + d_2(C, F))\)
  \(d_2(D, F) = 7\), \(d_2(D, C) = 5\), \(d_2(C, F) = 2\)
  \(5 + 2 = 7\) → \(d_3(D, F) = 7\) (inchangé)
• \(d_3(E, F)\) = \(\min(d_2(E, F), d_2(E, C) + d_2(C, F))\)
  \(d_2(E, F) = \infty\), \(d_2(E, C) = 13\), \(d_2(C, F) = 2\)
  \(13 + 2 = 15\) → \(d_3(E, F) = 15\)
• \(d_3(G, F)\) = \(\min(d_2(G, F), d_2(G, C) + d_2(C, F))\)
  \(d_2(G, F) = 8\), \(d_2(G, C) = \infty\), donc inchangé

Matrice \(d_3\) après étape 3 :

Étape 4 : \(k = 3\) (intermédiaire D autorisé) - Matrice \(d_4\)

On autorise maintenant le sommet D (indice 3) comme intermédiaire supplémentaire. On utilise la matrice \(d_3\).

Pour une paire \((i,j)\), la nouvelle distance possible via D est : \(d(i,3) + d(3,j)\).

Paires améliorées :

• \(d_4(A, G)\) = \(\min(d_3(A, G), d_3(A, D) + d_3(D, G))\)
  \(d_3(A, G) = \infty\), \(d_3(A, D) = 1\), \(d_3(D, G) = 11\)
  \(1 + 11 = 12\) → \(d_4(A, G) = 12\)
• \(d_4(B, G)\) = \(\min(d_3(B, G), d_3(B, D) + d_3(D, G))\)
  \(d_3(B, G) = \infty\), \(d_3(B, D) = 4\), \(d_3(D, G) = 11\)
  \(4 + 11 = 15\) → \(d_4(B, G) = 15\)
• \(d_4(C, G)\) = \(\min(d_3(C, G), d_3(C, D) + d_3(D, G))\)
  \(d_3(C, G) = \infty\), \(d_3(C, D) = 5\), \(d_3(D, G) = 11\)
  \(5 + 11 = 16\) → \(d_4(C, G) = 16\)
• \(d_4(E, G)\) = \(\min(d_3(E, G), d_3(E, D) + d_3(D, G))\)
  \(d_3(E, G) = 1\), \(d_3(E, D) = 10\), \(d_3(D, G) = 11\)
  \(10 + 11 = 21\) → inchangé (1)
• \(d_4(F, G)\) = \(\min(8, d_3(F, D) + d_3(D, G)) = \min(8, 7 + 11 = 18)\) → inchangé

Matrice \(d_4\) après étape 4 :

Étape 5 : \(k = 4\) (intermédiaire E autorisé) - Matrice \(d_5\)

On autorise maintenant le sommet E (indice 4) comme intermédiaire supplémentaire. On utilise la matrice \(d_4\).

Pour une paire \((i,j)\), la nouvelle distance possible via E est : \(d(i,4) + d(4,j)\).

Paires améliorées :

• \(d_5(A, G)\) = \(\min(d_4(A, G), d_4(A, E) + d_4(E, G))\)
  \(d_4(A, G) = 12\), \(d_4(A, E) = 9\), \(d_4(E, G) = 1\)
  \(9 + 1 = 10\) → \(d_5(A, G) = 10\) (amélioration)
• \(d_5(B, G)\) = \(\min(d_4(B, G), d_4(B, E) + d_4(E, G))\)
  \(d_4(B, G) = 15\), \(d_4(B, E) = 6\), \(d_4(E, G) = 1\)
  \(6 + 1 = 7\) → \(d_5(B, G) = 7\) (amélioration)
• \(d_5(C, G)\) = \(\min(d_4(C, G), d_4(C, E) + d_4(E, G))\)
  \(d_4(C, G) = 16\), \(d_4(C, E) = 13\), \(d_4(E, G) = 1\)
  \(13 + 1 = 14\) → \(d_5(C, G) = 14\) (amélioration)
• \(d_5(D, G)\) = \(\min(11, d_4(D, E) + d_4(E, G)) = \min(11, 10 + 1 = 11)\) → inchangé
• \(d_5(F, G)\) = \(\min(8, d_4(F, E) + d_4(E, G)) = \min(8, 15 + 1 = 16)\) → inchangé
• \(d_5(C, F)\) = \(\min(2, d_4(C, E) + d_4(E, F)) = \min(2, 13 + 15 = 28)\) → inchangé

Matrice \(d_5\) après étape 5 :

Étape 6 : \(k = 5\) (intermédiaire F autorisé) - Matrice \(d_6\)

On autorise maintenant le sommet F (indice 5) comme intermédiaire supplémentaire. On utilise la matrice \(d_5\).

Pour une paire \((i,j)\), la nouvelle distance possible via F est : \(d(i,5) + d(5,j)\).

Paires améliorées :

• \(d_6(C, G)\) = \(\min(d_5(C, G), d_5(C, F) + d_5(F, G))\)
  \(d_5(C, G) = 14\), \(d_5(C, F) = 2\), \(d_5(F, G) = 8\)
  \(2 + 8 = 10\) → \(d_6(C, G) = 10\) (amélioration)
• \(d_6(A, G)\) = \(\min(10, d_5(A, F) + d_5(F, G)) = \min(10, 6 + 8 = 14)\) → inchangé
• \(d_6(B, G)\) = \(\min(7, d_5(B, F) + d_5(F, G)) = \min(7, 9 + 8 = 17)\) → inchangé
• \(d_6(D, G)\) = \(\min(11, d_5(D, F) + d_5(F, G)) = \min(11, 7 + 8 = 15)\) → inchangé
• \(d_6(E, G)\) = \(\min(1, d_5(E, F) + d_5(F, G)) = \min(1, 15 + 8 = 23)\) → inchangé
• \(d_6(C, E)\) = \(\min(13, d_5(C, F) + d_5(F, E)) = \min(13, 2 + 15 = 17)\) → inchangé

Matrice \(d_6\) après étape 6 :

Étape 7 : \(k = 6\) (intermédiaire G autorisé) - Matrice \(d_7\) (finale)

On autorise maintenant le sommet G (indice 6) comme intermédiaire supplémentaire. On utilise la matrice \(d_6\).

Pour une paire \((i,j)\), la nouvelle distance possible via G est : \(d(i,6) + d(6,j)\).

Paires améliorées :

• \(d_7(C, E)\) = \(\min(d_6(C, E), d_6(C, G) + d_6(G, E))\)
  \(d_6(C, E) = 13\), \(d_6(C, G) = 10\), \(d_6(G, E) = 1\)
  \(10 + 1 = 11\) → \(d_7(C, E) = 11\) (amélioration)
• \(d_7(E, F)\) = \(\min(d_6(E, F), d_6(E, G) + d_6(G, F))\)
  \(d_6(E, F) = 15\), \(d_6(E, G) = 1\), \(d_6(G, F) = 8\)
  \(1 + 8 = 9\) → \(d_7(E, F) = 9\) (amélioration)
• \(d_7(C, F)\) = \(\min(2, d_6(C, G) + d_6(G, F)) = \min(2, 10 + 8 = 18)\) → inchangé
• \(d_7(A, E)\) = \(\min(9, d_6(A, G) + d_6(G, E)) = \min(9, 10 + 1 = 11)\) → inchangé
• \(d_7(B, E)\) = \(\min(6, d_6(B, G) + d_6(G, E)) = \min(6, 7 + 1 = 8)\) → inchangé
• \(d_7(D, E)\) = \(\min(10, d_6(D, G) + d_6(G, E)) = \min(10, 11 + 1 = 12)\) → inchangé

Matrice finale \(d_7\) après étape 7 :

Résultats finaux : plus courts chemins entre tous les couples

La matrice \(d_7\) donne les distances minimales entre tous les couples de sommets :

Exemples de chemins optimaux :

• A → G : distance 10 (A → B → E → G ou A → C → F → G)
• B → G : distance 7 (B → E → G)
• C → G : distance 10 (C → F → G)
• E → F : distance 9 (E → G → F)
• C → E : distance 11 (C → F → G → E ou C → D → E)

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define INF INT_MAX
#define N 7

// Fonction pour initialiser la matrice
void initialiserMatrice(int M[N][N], int valeurs[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            M[i][j] = valeurs[i][j];
        }
    }
}

// Algorithme de Floyd-Warshall
void floydWarshall(int D[N][N]) {
    for (int k = 0; k < N; k++) {       // Sommet intermédiaire autorisé
        for (int i = 0; i < N; i++) {   // Départ
            for (int j = 0; j < N; j++) { // Arrivée
                if (D[i][k] != INF && D[k][j] != INF && 
                    D[i][k] + D[k][j] < D[i][j]) {
                    D[i][j] = D[i][k] + D[k][j];
                }
            }
        }
    }
}

// Fonction pour afficher la matrice
void afficherMatrice(int M[N][N]) {
    char* sommets[] = {"A", "B", "C", "D", "E", "F", "G"};
    
    printf("    ");
    for (int j = 0; j < N; j++) {
        printf("%3s ", sommets[j]);
    }
    printf("\n");
    
    for (int i = 0; i < N; i++) {
        printf("%3s ", sommets[i]);
        for (int j = 0; j < N; j++) {
            if (M[i][j] == INF)
                printf("  ∞ ");
            else
                printf("%3d ", M[i][j]);
        }
        printf("\n");
    }
}

int main() {
    // Matrice initiale (graphe exemple)
    // A=0, B=1, C=2, D=3, E=4, F=5, G=6
    int initial[N][N] = {
        {0, 3, 4, 1, INF, INF, INF}, // A
        {3, 0, INF, 13, 6, INF, INF}, // B
        {4, INF, 0, 9, INF, 2, INF}, // C
        {1, 13, 9, 0, 10, 7, 11},    // D
        {INF, 6, INF, 10, 0, INF, 1}, // E
        {INF, INF, 2, 7, INF, 0, 8}, // F
        {INF, INF, INF, 11, 1, 8, 0} // G
    };
    
    int D[N][N];
    initialiserMatrice(D, initial);
    
    printf("Matrice initiale d0 :\n");
    afficherMatrice(D);
    
    floydWarshall(D);
    
    printf("\nMatrice finale des plus courts chemins :\n");
    afficherMatrice(D);
    
    // Détection de cycle négatif (vérification sur la diagonale)
    printf("\nVérification des cycles négatifs :\n");
    for (int i = 0; i < N; i++) {
        if (D[i][i] < 0) {
            printf("Cycle négatif détecté sur le sommet %d !\n", i);
        }
    }
    
    return 0;
}

import copy

def floyd_warshall(A):
    """
    Implémentation de l'algorithme de Floyd-Warshall.
    
    Paramètres:
    A : matrice d'adjacence du graphe (liste de listes)
    
    Retourne:
    D : matrice des distances minimales entre tous les couples
    """
    n = len(A)
    # Initialisation
    D = copy.deepcopy(A)
    
    for k in range(n):       # Sommet intermédiaire autorisé
        for i in range(n):   # Départ
            for j in range(n): # Arrivée
                D[i][j] = min(D[i][j], D[i][k] + D[k][j])
    return D

def afficher_matrice(M, sommets):
    """Affiche la matrice avec les noms des sommets"""
    print("    ", end="")
    for s in sommets:
        print(f"{s:3} ", end="")
    print()
    
    for i in range(len(M)):
        print(f"{sommets[i]:3} ", end="")
        for j in range(len(M[i])):
            if M[i][j] == float('inf'):
                print("  ∞ ", end="")
            else:
                print(f"{M[i][j]:3} ", end="")
        print()

# Graphe exemple
inf = float('inf')
graphe = [
    [0,   3,   4,   1,   inf, inf, inf], # A
    [3,   0,   inf, 13,  6,   inf, inf], # B
    [4,   inf, 0,   9,   inf, 2,   inf], # C
    [1,   13,  9,   0,   10,  7,   11],  # D
    [inf, 6,   inf, 10,  0,   inf, 1],   # E
    [inf, inf, 2,   7,   inf, 0,   8],   # F
    [inf, inf, inf, 11,  1,   8,   0]    # G
]

sommets = ['A', 'B', 'C', 'D', 'E', 'F', 'G']

print("Matrice initiale d0 :")
afficher_matrice(graphe, sommets)

D = floyd_warshall(graphe)

print("\nMatrice finale des plus courts chemins :")
afficher_matrice(D, sommets)

# Détection de cycle négatif
print("\nVérification des cycles négatifs :")
for i in range(len(D)):
    if D[i][i] < 0:
        print(f"Cycle négatif détecté sur le sommet {sommets[i]} !")

Matrice initiale d0 :
     A   B   C   D   E   F   G 
  A   0   3   4   1   ∞   ∞   ∞ 
  B   3   0   ∞  13   6   ∞   ∞ 
  C   4   ∞   0   9   ∞   2   ∞ 
  D   1  13   9   0  10   7  11 
  E   ∞   6   ∞  10   0   ∞   1 
  F   ∞   ∞   2   7   ∞   0   8 
  G   ∞   ∞   ∞  11   1   8   0 

Matrice finale des plus courts chemins :
     A   B   C   D   E   F   G 
  A   0   3   4   1   9   6  10 
  B   3   0   7   4   6   9   7 
  C   4   7   0   5  11   2  10 
  D   1   4   5   0  10   7  11 
  E   9   6  11  10   0   9   1 
  F   6   9   2   7   9   0   8 
  G  10   7  10  11   1   8   0

Analyse de complexité

Comparaison avec les algorithmes à source unique

Détection des cycles négatifs

Floyd-Warshall permet également de détecter la présence de cycles négatifs. Après l'exécution de l'algorithme, il suffit de vérifier la diagonale de la matrice :

En effet, \(d(i,i)\) représente la longueur du plus court chemin de \(i\) à \(i\). Normalement, ce devrait être 0 (rester sur place). Une valeur négative indique qu'on peut revenir à \(i\) avec un coût total négatif, donc qu'il existe un cycle négatif.

Extension : Reconstruction des chemins

Pour reconstruire les chemins eux-mêmes (pas seulement les distances), on peut ajouter une matrice de prédécesseurs \(P\) où \(P[i][j]\) stocke le dernier sommet intermédiaire avant \(j\) sur le plus court chemin de \(i\) à \(j\).

def floyd_warshall_chemins(A):
    n = len(A)
    D = copy.deepcopy(A)
    P = [[-1 if i == j or A[i][j] == float('inf') else i for j in range(n)] for i in range(n)]
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if D[i][k] + D[k][j] < D[i][j]:
                    D[i][j] = D[i][k] + D[k][j]
                    P[i][j] = P[k][j]  # Le prédécesseur de j devient celui du chemin via k
    return D, P

def reconstruire_chemin(P, i, j):
    """Reconstruit le chemin de i à j à partir de la matrice des prédécesseurs"""
    if P[i][j] == -1:
        return None
    chemin = [j]
    while i != j:
        j = P[i][j]
        chemin.insert(0, j)
    return chemin