1. **Énoncé du problème** : Appliquer l'algorithme de Bellman-Ford sur le graphe donné pour trouver les plus courts chemins à partir d'un sommet source. 2. **Description du graphe** : Les sommets sont A, B, C, D, E, F, G avec les arêtes pondérées suivantes : - A-B : 8 - B-C : 2 - B-G : 6 - F-G : 9 - G-C : 14 - A-E : 11 - E-F : 2 - F-D : 7 - D-C : 5 - E-D : 3 3. **Principe de Bellman-Ford** : - Initialiser la distance de la source à 0 et toutes les autres à l'infini. - Relaxer toutes les arêtes $|V|-1$ fois (ici $7-1=6$ fois). - Vérifier l'absence de cycle négatif. 4. **Choix du sommet source** : Le problème ne précise pas, on peut choisir par exemple le sommet C. 5. **Initialisation** : $$ \text{dist}(C) = 0, \quad \text{dist}(v) = \infty \quad \forall v \neq C $$ 6. **Relaxation des arêtes (exemple d'une itération)** : - Pour chaque arête $(u,v)$ avec poids $w$, si $\text{dist}(u) + w < \text{dist}(v)$ alors $\text{dist}(v) = \text{dist}(u) + w$. 7. **Calcul itératif** : - Après plusieurs itérations, on obtient les distances minimales de C vers tous les sommets. 8. **Résultat final** (distances minimales à partir de C) : - $\text{dist}(C) = 0$ - $\text{dist}(B) = 2$ - $\text{dist}(D) = 5$ - $\text{dist}(E) = 8$ - $\text{dist}(F) = 10$ - $\text{dist}(G) = 8$ - $\text{dist}(A) = 16$ 9. **Conclusion** : L'algorithme Bellman-Ford permet de calculer les plus courts chemins même en présence d'arêtes avec poids positifs ou négatifs (ici tous positifs). Il est plus général que Dijkstra mais moins efficace. **Note** : Pour appliquer à partir de F, on réinitialise et répète le même processus avec $\text{dist}(F)=0$.