1. **Énoncé du problème** : L'algorithme de Floyd permet de calculer les plus courts chemins entre tous les couples de sommets $(i,j)$ dans un graphe simple sans circuit absorbant, en utilisant une matrice d'adjacence des poids $P = (p_{ij})_{1 \leq i,j \leq n}$. 2. **Définition de la matrice $P$ et de $pred$** : - $p_{ii} = 0$ pour tout $i$ (le poids d'un sommet vers lui-même est nul). - $p_{ij} = \infty$ si aucun arc direct ne relie $i$ à $j$. - La matrice $pred = (pred_{ij})$ est définie par : $$pred_{ij} = \begin{cases} 0, & \text{si } p_{ij} = \infty \\ i, & \text{sinon} \end{cases}$$ Cela signifie que si $j$ n'est pas accessible directement depuis $i$, il n'y a pas de prédécesseur (0), sinon le prédécesseur initial est $i$. 3. **Principe de l'algorithme de Floyd** : L'algorithme itère sur tous les sommets $k$ et met à jour les poids $p_{ij}$ en testant si le chemin passant par $k$ est plus court : $$p_{ij} = \min(p_{ij}, p_{ik} + p_{kj})$$ Si cette mise à jour améliore le poids, on met aussi à jour le prédécesseur : $$pred_{ij} = pred_{kj}$$ Cela signifie que le prédécesseur de $j$ sur le plus court chemin de $i$ à $j$ devient le prédécesseur de $j$ sur le chemin de $k$ à $j$. 4. **Rôle de $pred$ dans la reconstruction du chemin** : - $pred_{ij}$ indique le sommet juste avant $j$ sur le plus court chemin de $i$ à $j$. - En suivant récursivement $pred_{ij}$, on peut reconstruire le chemin complet de $i$ à $j$. 5. **Condition d'arrêt et matrice $Q$** : La matrice $Q$ des poids minimaux est obtenue lorsque l'intercalage d'un sommet $k$ ne permet plus d'améliorer aucun poids : $$Q = \min Q \iff T_k Q = Q \quad \forall k$$ avec $$Q = T_n T_{n-1} \cdots T_1 P$$ **En résumé**, $pred$ est mis à jour à chaque amélioration de chemin pour garder la trace du prédécesseur immédiat sur le plus court chemin, ce qui permet de reconstruire facilement les chemins minimaux après l'exécution complète de l'algorithme.