1. **Énoncé du problème** : Nous allons illustrer le déroulement de l'algorithme de Floyd pour trouver les plus courts chemins entre tous les couples de nœuds dans un graphe orienté avec poids, donné par les sommets $x_1, x_2, x_3, x_4$ et les arêtes avec poids spécifiés. 2. **Principe de l'algorithme de Floyd** : L'algorithme de Floyd-Warshall calcule les plus courts chemins entre toutes les paires de sommets en utilisant une approche dynamique. La formule de mise à jour est : $$d_{ij}^{(k)} = \min\left(d_{ij}^{(k-1)}, d_{ik}^{(k-1)} + d_{kj}^{(k-1)}\right)$$ Cela signifie que pour chaque sommet intermédiaire $x_k$, on vérifie si passer par $x_k$ améliore le chemin entre $x_i$ et $x_j$. 3. **Initialisation** : On construit la matrice des distances initiales $D^{(0)}$ où $d_{ij}$ est le poids de l'arête $(x_i,x_j)$ si elle existe, sinon $\infty$, et $d_{ii} = 0$. 4. **Matrice initiale $D^{(0)}$** : $$\begin{pmatrix} 0 & 3 & 2 & \infty \\ 3 & 3 & 4 & 2 \\ -2 & \infty & 0 & 1 \\ \infty & 2 & 4 & 0 \end{pmatrix}$$ 5. **Itération $k=1$ (intermédiaire $x_1$)** : On met à jour chaque $d_{ij}$ en comparant $d_{ij}^{(0)}$ et $d_{i1}^{(0)} + d_{1j}^{(0)}$. Par exemple, pour $d_{24}$ : $$d_{24}^{(1)} = \min(d_{24}^{(0)}, d_{21}^{(0)} + d_{14}^{(0)}) = \min(2, 3 + \infty) = 2$$ Aucune amélioration ici. 6. **Itération $k=2$ (intermédiaire $x_2$)** : On calcule $d_{ij}^{(2)} = \min(d_{ij}^{(1)}, d_{i2}^{(1)} + d_{2j}^{(1)})$. Par exemple, pour $d_{13}$ : $$d_{13}^{(2)} = \min(2, 3 + 4) = 2$$ Pas d'amélioration. 7. **Itération $k=3$ (intermédiaire $x_3$)** : On calcule $d_{ij}^{(3)} = \min(d_{ij}^{(2)}, d_{i3}^{(2)} + d_{3j}^{(2)})$. Par exemple, pour $d_{14}$ : $$d_{14}^{(3)} = \min(\infty, 2 + 1) = 3$$ On améliore le chemin de $x_1$ à $x_4$ via $x_3$. 8. **Itération $k=4$ (intermédiaire $x_4$)** : On calcule $d_{ij}^{(4)} = \min(d_{ij}^{(3)}, d_{i4}^{(3)} + d_{4j}^{(3)})$. Par exemple, pour $d_{13}$ : $$d_{13}^{(4)} = \min(2, 3 + 4) = 2$$ Pas d'amélioration. 9. **Résultat final** : La matrice des plus courts chemins est : $$\begin{pmatrix} 0 & 3 & 2 & 3 \\ 3 & 3 & 4 & 2 \\ -2 & 1 & 0 & 1 \\ 5 & 2 & 4 & 0 \end{pmatrix}$$ Cela signifie par exemple que le plus court chemin de $x_1$ à $x_4$ vaut 3, passant par $x_3$. Cette méthode garantit de trouver les plus courts chemins entre tous les couples de sommets, même en présence de poids négatifs, à condition qu'il n'y ait pas de cycle négatif.