Graphe orienté valué { S , A , B , C , D , E , T } : S → A = 5 , S → B = 3 , A → C = 4 , A → D = 2 , B → A = 1 , B → D = 6 , C → T = 3 , D → C = 1 , D → E = 4 , E → T = 2 . 1. Dijkstra. 2. Arbre. 3. Chemin S → T . 4. Pourquoi poids positifs nécessaires ?

Dijkstra et arbre des plus courts chemins

Difficile Inspiré BAC France

Exercice inspiré d'un BAC France

Énoncé et solution adaptés au programme français. Voir crédits.

Énoncé

Graphe orienté valué ${S, A, B, C, D, E, T}$ : $S \to A = 5$ , $S \to B = 3$ , $A \to C = 4$ , $A \to D = 2$ , $B \to A = 1$ , $B \to D = 6$ , $C \to T = 3$ , $D \to C = 1$ , $D \to E = 4$ , $E \to T = 2$ . 1. Dijkstra. 2. Arbre. 3. Chemin $S \to T$ . 4. Pourquoi poids positifs nécessaires ?

Indices

— clique pour révéler

1 Indice 1

Applique l'algorithme de Dijkstra en partant de $S$ : a chaque etape, choisis le sommet non visite ayant la plus petite distance provisoire, puis mets a jour les distances de ses voisins.

2 Indice 2

Note a chaque etape le sommet precedent qui a permis d'obtenir la distance minimale : c'est ce qui te permettra de reconstituer l'arbre des plus courts chemins et le chemin final vers $T$.

3 Indice 3

Pour la derniere question, reflechis a ce qui se passerait si un sommet deja marque comme definitif pouvait encore voir sa distance diminuer a cause d'une arete de poids negatif.

Bloqué sur cet exercice ?

Léo peut t'expliquer pas à pas, en s'adaptant à ton niveau.

Demander à Léo

Exercice Terminé? 🎉

Validez votre réponse pour enregistrer votre progression et gagner des points

Chaîne de Markov : voiture ou transports en commun ? Retour au chapitre Distribution stationnaire — Chaîne à deux états

Dijkstra et arbre des plus courts chemins

Énoncé

Indices

Correction détaillée

Débloque le corrigé complet

Exercice Terminé? 🎉

Dijkstra et arbre des plus courts chemins

Énoncé

Indices

Correction détaillée

Débloque le corrigé complet

Exercice Terminé? 🎉

Valider votre réponse

Tu as vu 5 exercices aujourd'hui 🎯