1. **Énoncé du problème :** Déterminer le plus court chemin du sommet A au sommet F dans un graphe pondéré. 2. **Données du graphe :** Les sommets sont A, B, C, D, E, F. Les arêtes avec poids sont : - A-B : 3 - A-C : 4 - B-D : 2 - B-C : 9 - C-D : 2 - B-E : 2 - D-F : 3 - E-F : 1 - C-E : 5 3. **Formule et méthode utilisée :** Nous utilisons l'algorithme de Dijkstra pour trouver le plus court chemin dans un graphe pondéré sans poids négatifs. 4. **Étapes de calcul :** - Initialisation : distance(A) = 0, distance(autres) = \infty. - Visiter les voisins de A : distance(B) = 3, distance(C) = 4. - Choisir le sommet avec la plus petite distance non visitée : B (3). - Mettre à jour les distances via B : distance(D) = min(\infty, 3 + 2) = 5, distance(C) = min(4, 3 + 9) = 4 (reste 4), distance(E) = min(\infty, 3 + 2) = 5. - Choisir le sommet suivant : C (4). - Mettre à jour les distances via C : distance(D) = min(5, 4 + 2) = 5 (reste 5), distance(E) = min(5, 4 + 5) = 5 (reste 5). - Choisir le sommet suivant : D (5). - Mettre à jour la distance via D : distance(F) = min(\infty, 5 + 3) = 8. - Choisir le sommet suivant : E (5). - Mettre à jour la distance via E : distance(F) = min(8, 5 + 1) = 6. - Choisir le sommet suivant : F (6). 5. **Chemin le plus court :** Pour retrouver le chemin, on remonte : F a été atteint via E (car 6 = 5 + 1), E a été atteint via B (5 = 3 + 2), B a été atteint via A (3). Donc le chemin est : $$A \to B \to E \to F$$ avec une distance totale de $$3 + 2 + 1 = 6$$. **Réponse finale :** Le plus court chemin de A à F est $$A \to B \to E \to F$$ avec une distance de 6.