1. **Énoncé du problème** : Appliquer l'algorithme de Bellman-Ford pour trouver les plus courts chemins depuis un sommet source donné dans le graphe orienté avec poids donnés. 2. **Description du graphe** : Le graphe a 7 sommets (A, B, C, D, E, F, G) et les arêtes avec poids suivants : - A \rightarrow B : 8 - B \rightarrow C : 2 - C \rightarrow G : 14 - G \rightarrow D : 5 - D \rightarrow E : 3 - E \rightarrow F : 2 - F \rightarrow A : 11 - B \rightarrow G : 6 - F \rightarrow G : 9 - F \rightarrow D : 7 3. **Choix du sommet source** : Supposons que le sommet source soit A. 4. **Initialisation** : - Distance(A) = 0 - Distance(v) = \infty pour tout v \neq A 5. **Relaxation des arêtes** : Répéter |V|-1 = 6 fois la relaxation de toutes les arêtes. 6. **Itération 1** : - Distance(B) = min(\infty, 0 + 8) = 8 - Distance(C) = min(\infty, 8 + 2) = 10 - Distance(G) = min(\infty, 10 + 14) = 24 - Distance(D) = min(\infty, 24 + 5) = 29 - Distance(E) = min(\infty, 29 + 3) = 32 - Distance(F) = min(\infty, 32 + 2) = 34 - Distance(A) = min(0, 34 + 11) = 0 (reste 0) - Distance(G) = min(24, 8 + 6) = 14 - Distance(G) = min(14, 34 + 9) = 14 - Distance(D) = min(29, 34 + 7) = 29 7. **Itération 2** : - Distance(B) reste 8 - Distance(C) = min(10, 8 + 2) = 10 - Distance(G) = min(14, 10 + 14) = 14 - Distance(D) = min(29, 14 + 5) = 19 - Distance(E) = min(32, 19 + 3) = 22 - Distance(F) = min(34, 22 + 2) = 24 - Distance(A) reste 0 - Distance(G) = min(14, 8 + 6) = 14 - Distance(G) = min(14, 24 + 9) = 14 - Distance(D) = min(19, 24 + 7) = 19 8. **Itérations 3 à 6** : Les distances ne changent plus, donc l'algorithme converge. 9. **Résultat final** : - Distance(A) = 0 - Distance(B) = 8 - Distance(C) = 10 - Distance(G) = 14 - Distance(D) = 19 - Distance(E) = 22 - Distance(F) = 24 10. **Conclusion** : Les plus courts chemins depuis A vers tous les sommets sont calculés avec les distances ci-dessus.