Algorithmes sur les arbres et les graphes

Parcours d'un arbre : en profondeur (préfixe, infixe, suffixe) et en largeur#

Standardeduscol-programme-nsi-terminale

Un même arbre lu selon les trois ordres de parcours en profondeur

Fig. 1Le même arbre, lu de trois façons en profondeur. Préfixe (racine, gauche, droite) : A B D E C F. Infixe (gauche, racine, droite) : D B E A F C. Suffixe (gauche, droite, racine) : D E B F C A.

Parcourir un arbre, c'est visiter chacun de ses nœuds une et une seule fois selon un ordre choisi. La nature récursive de l'arbre (un nœud, un sous-arbre gauche, un sous-arbre droit) donne directement les algorithmes récursifs de parcours.

Parcours en PROFONDEUR (DFS) — trois variantes selon la position de la visite de la racine : PRÉFIXE = Racine, puis Gauche, puis Droit (R-G-D) ; INFIXE = Gauche, Racine, Droit (G-R-D) ; SUFFIXE = Gauche, Droit, Racine (G-D-R). Dans les trois cas on descend d'abord aussi loin que possible dans une branche avant de remonter.

Parcours en LARGEUR (BFS) : on visite les nœuds niveau par niveau (la racine, puis tous ses enfants, puis tous les petits-enfants, etc.). Il s'appuie sur une FILE : on défile un nœud, on le visite, puis on enfile ses enfants.

Le parcours en profondeur s'écrit naturellement de façon récursive (la pile d'appels joue le rôle de pile) ; il peut aussi s'écrire itérativement avec une PILE explicite. Le parcours en largeur, lui, n'est PAS naturellement récursif : il réclame une FILE explicite.

Propriété clé (réutilisée en section 2) : sur un arbre binaire de recherche, le parcours INFIXE restitue les clés dans l'ordre croissant — c'est un moyen simple d'obtenir une liste triée.

\text{prefixe}(a) = [\text{racine}] + \text{prefixe}(g) + \text{prefixe}(d)

Parcours préfixe (récursif)

On visite la racine, puis récursivement le sous-arbre gauche g, puis le sous-arbre droit d. Cas de base : l'arbre vide donne la liste vide.

\text{infixe}(a) = \text{infixe}(g) + [\text{racine}] + \text{infixe}(d)

Parcours infixe (récursif)

La racine est visitée entre les deux sous-arbres. Sur un ABR, ce parcours fournit les clés triées en ordre croissant.

\text{suffixe}(a) = \text{suffixe}(g) + \text{suffixe}(d) + [\text{racine}]

Parcours suffixe (récursif)

La racine est visitée en dernier, après ses deux sous-arbres. Utile par exemple pour libérer/supprimer un arbre des feuilles vers la racine.

Parcours en largeur (niveau par niveau) et état de la file

Fig. 2Le parcours en largeur (BFS) utilise une FILE : on défile un nœud, on enfile ses enfants. Niveau par niveau, on obtient l'ordre A B C D E F (cellule mise en évidence).

Exemple corrigé

Les quatre parcours d'un arbre binaire

On considère l'arbre binaire de racine A, dont le sous-arbre gauche a pour racine B (de fils gauche D et fils droit E) et dont le sous-arbre droit a pour racine C (de fils gauche F, sans fils droit). Donner l'ordre des nœuds visités pour les parcours préfixe, infixe, suffixe et en largeur.

Préfixe (Racine-Gauche-Droit)
On visite A, puis on traite tout le sous-arbre gauche (B puis ses fils D, E), puis tout le sous-arbre droit (C puis son fils F).
Infixe (Gauche-Racine-Droit)
Dans le sous-arbre gauche : D, puis B, puis E. Ensuite la racine A. Puis le sous-arbre droit : F (fils gauche) puis C.
Suffixe (Gauche-Droit-Racine)
Sous-arbre gauche d'abord (D, E, puis B), puis sous-arbre droit (F, puis C), enfin la racine A.
Largeur (par niveaux, avec une file)
Niveau 0 : A. Niveau 1 : B puis C. Niveau 2 : D, E (enfants de B) puis F (enfant de C).

Résultat : Préfixe : A B D E C F. Infixe : D B E A F C. Suffixe : D E B F C A. Largeur : A B C D E F.

Schritt-für-Schritt Erklärung4 Schritte

1
Un arbre se parcourt de façon récursive : on traite la racine et l'on rappelle la même fonction sur le sous-arbre gauche puis sur le sous-arbre droit. Tout tient dans la position de la visite de la racine.
2
Si l'on visite la racine en premier, c'est le parcours préfixe : Racine, Gauche, Droit.
3
Au milieu, c'est l'infixe ; il a une vertu remarquable sur un arbre binaire de recherche : il restitue les clés triées.
4
En dernier, c'est le suffixe. Et pour visiter niveau par niveau, on abandonne la récursivité au profit d'une file : c'est le parcours en largeur.

Erreurs fréquentes

Confondre l'ordre des trois parcours en profondeur : le mot (PRÉfixe / INfixe / SUFfixe) indique seulement OÙ se place la visite de la racine — au début, au milieu, à la fin — les sous-arbres restant toujours dans l'ordre gauche puis droit.
Croire que le parcours en largeur peut s'obtenir avec une pile : avec une pile on obtient un parcours en profondeur. Le BFS exige une file (FIFO).
Oublier le cas de base (arbre vide) dans la fonction récursive, ce qui provoque une erreur en tentant de lire le sous-arbre d'un nœud absent.

Révision active

On considère l'arbre binaire de racine A, dont le sous-arbre gauche a pour racine B (de fils gauche D et fils droit E) et dont le sous-arbre droit a pour racine C (de fils gauche F, sans fils droit). Donner l'ordre des nœuds visités pour les parcours préfixe, infixe, suffixe et en largeur.

Rappel actif

Rappelle-toi les points clés — puis révèle.

Sources : Programme de spécialité NSI — classe terminale (voie générale), BO spécial n° 8 du 25 juillet 2019 (Ministère de l'Éducation nationale) · Programmes et ressources en NSI — voie générale (Éduscol) (Éduscol — Ministère de l'Éducation nationale)

Arbre binaire de recherche : recherche et insertion d'une valeur#

Standardeduscol-programme-nsi-terminale

Arbre binaire de recherche : invariant d'ordre et chemin de recherche

Fig. 3Invariant de l'ABR : gauche < nœud < droite. Le parcours INFIXE donne les clés triées : 1 3 4 6 7 8 10 13 14. Chercher 7 suit le chemin mis en évidence 8 → 3 → 6 → 7, en O(hauteur).

DÉFINITION : un arbre binaire de recherche (ABR) est un arbre binaire dont les clés vérifient, pour tout nœud, que TOUTES les clés du sous-arbre gauche sont inférieures à la clé du nœud, et TOUTES les clés du sous-arbre droit lui sont supérieures (cas d'un arbre sans clés répétées).

RECHERCHE : on compare la valeur cherchée à la clé de la racine ; si elle est égale, c'est trouvé ; si elle est plus petite, on continue dans le sous-arbre gauche ; sinon dans le sous-arbre droit. À chaque comparaison on élimine tout un sous-arbre : c'est la dichotomie appliquée à un arbre.

INSERTION : on suit le même chemin de descente que la recherche jusqu'à atteindre un emplacement vide (un sous-arbre absent) ; on y accroche un nouveau nœud portant la valeur. L'invariant de l'ABR est ainsi préservé.

COÛT : recherche et insertion parcourent au plus une branche, donc un nombre d'étapes égal à la hauteur de l'arbre. Si l'arbre est équilibré, la hauteur est de l'ordre de log₂(n), d'où une recherche très rapide ; s'il est filiforme (dégénéré), la hauteur vaut n−1 et la recherche redevient linéaire.

LIEN AVEC LE PARCOURS : un parcours infixe d'un ABR énumère toujours les clés en ordre croissant — c'est une conséquence directe de la propriété d'ordre, et un bon moyen de vérifier qu'un arbre est bien un ABR.

v < \text{cle}(n) \Rightarrow \text{aller a gauche}, \quad v > \text{cle}(n) \Rightarrow \text{aller a droite}

Règle de descente dans un ABR

Cette règle gouverne aussi bien la recherche que l'insertion ; à chaque étape on écarte tout un sous-arbre.

\forall x \in g(n),\ x < \text{cle}(n) \quad\text{et}\quad \forall x \in d(n),\ x > \text{cle}(n)

Invariant d'ordre de l'ABR

g(n) et d(n) désignent les sous-arbres gauche et droit du nœud n. Cet invariant doit être vrai pour tout nœud de l'arbre.

C_{\text{recherche}} = O(h) \ \text{avec}\ \log_2(n+1) - 1 \le h \le n - 1

Coût en fonction de la hauteur h

Le coût d'une recherche est proportionnel à la hauteur h. Équilibré, h vaut environ log₂(n) ; filiforme, h vaut n−1.

Exemple corrigé

Construire un ABR, lire le parcours infixe et tracer une recherche

On insère successivement dans un ABR initialement vide les valeurs 8, 3, 10, 1, 6, 14, 4, 7, 13. Donner le parcours infixe de l'arbre obtenu et décrire le chemin de comparaisons pour rechercher 7 puis 5.

Insérer 8, 3, 10
8 devient la racine. 3 < 8 : fils gauche de 8. 10 > 8 : fils droit de 8.
Insérer 1, 6, 14
1 < 8 puis 1 < 3 : fils gauche de 3. 6 < 8 puis 6 > 3 : fils droit de 3. 14 > 8 puis 14 > 10 : fils droit de 10.
Insérer 4, 7, 13
4 < 8, 4 > 3, 4 < 6 : fils gauche de 6. 7 < 8, 7 > 3, 7 > 6 : fils droit de 6. 13 > 8, 13 > 10, 13 < 14 : fils gauche de 14.
Parcours infixe (Gauche-Racine-Droit)
Le parcours infixe d'un ABR restitue les clés triées. On lit donc l'arbre de la plus petite à la plus grande clé.
Rechercher 7 puis 5
Pour 7 : 7 < 8 (gauche), 7 > 3 (droite), 7 > 6 (droite), 7 = 7 : TROUVÉ après le chemin 8, 3, 6, 7. Pour 5 : 5 < 8 (gauche), 5 > 3 (droite), 5 < 6 (gauche), 5 > 4 (droite) ; le sous-arbre droit de 4 est vide : 5 est ABSENT.

Résultat : Parcours infixe : 1 3 4 6 7 8 10 13 14 (clés triées). Recherche de 7 : trouvé par 8→3→6→7. Recherche de 5 : absent (chemin 8→3→6→4, puis sous-arbre vide).

Erreurs fréquentes

Inverser le sens des comparaisons (aller à droite pour une valeur plus petite) : on perd alors l'invariant et la recherche échoue.
Croire que la forme de l'ABR ne dépend pas de l'ordre d'insertion : insérer une liste déjà triée produit un arbre filiforme, donc une recherche lente.
Confondre ABR et arbre binaire quelconque : un arbre binaire n'est un ABR que si la propriété d'ordre est vérifiée à CHAQUE nœud, pas seulement entre un nœud et ses fils immédiats.

Révision active

On insère successivement dans un ABR initialement vide les valeurs 8, 3, 10, 1, 6, 14, 4, 7, 13. Dessiner l'arbre obtenu, donner son parcours infixe, et décrire le chemin de comparaisons effectué pour rechercher la valeur 7 puis la valeur 5.

Rappel actif

Rappelle-toi les points clés — puis révèle.

Sources : Programme de spécialité NSI — classe terminale (voie générale), BO spécial n° 8 du 25 juillet 2019 (Ministère de l'Éducation nationale) · Programmes et ressources en NSI — voie générale (Éduscol) (Éduscol — Ministère de l'Éducation nationale)

Parcours d'un graphe : en profondeur (pile) et en largeur (file)#

Standardeduscol-programme-nsi-terminale

Graphe non orienté servant de support aux parcours

Fig. 4Le graphe support des parcours, départ au sommet A (mis en évidence). Sommets A à F, arêtes A-B, A-C, B-D, B-E, C-F, E-F. On y déroulera un DFS et un BFS depuis A.

Un graphe peut contenir des CYCLES : contrairement à l'arbre, on risque de repasser indéfiniment par les mêmes sommets. La règle d'or est donc de MARQUER chaque sommet visité (ensemble visités) et de ne jamais le retraiter.

Parcours en PROFONDEUR (DFS) : depuis un sommet, on explore un voisin non visité, puis un voisin de celui-ci, et ainsi de suite aussi loin que possible avant de revenir en arrière (backtracking). Il s'écrit soit récursivement (la pile d'appels gère le retour en arrière), soit itérativement avec une PILE explicite (LIFO).

Parcours en LARGEUR (BFS) : depuis un sommet, on visite d'abord tous ses voisins (distance 1), puis les voisins des voisins (distance 2), etc. Il s'écrit avec une FILE (FIFO) : on défile un sommet, on enfile ses voisins non encore marqués.

Le couple structure ↔ stratégie est central : FILE ⇒ largeur (BFS), PILE (ou récursivité) ⇒ profondeur (DFS). C'est exactement le repère du programme, et il relie ce thème à celui des structures de données linéaires.

Sur un graphe NON pondéré, le BFS a une propriété forte : il découvre chaque sommet par un chemin comportant le nombre minimal d'arêtes. C'est le plus court chemin « en nombre d'arêtes » (mais pas forcément en poids — d'où Dijkstra en section 5).

\text{DFS} \Longleftrightarrow \text{PILE (LIFO) ou recursivite} \qquad \text{BFS} \Longleftrightarrow \text{FILE (FIFO)}

Le repère structure ↔ parcours

Repère fondamental du programme : la structure de données choisie détermine la stratégie d'exploration.

\text{visiter}(u): \ \text{marquer } u,\ \text{puis pour chaque voisin } v \notin \text{visites} : \text{visiter}(v)

Squelette du DFS récursif

Le marquage de u avant la descente garantit qu'on ne repasse jamais par un sommet déjà vu, même en présence de cycles.

Pourquoi une pile donne le DFS et une file le BFS

Fig. 5La structure d'attente décide du parcours : une PILE (LIFO) explore d'abord le dernier sommet découvert (en profondeur, DFS) ; une FILE (FIFO) explore dans l'ordre de découverte (en largeur, BFS).

Exemple corrigé

Dérouler un BFS et un DFS depuis A

Soit le graphe non orienté d'arêtes A-B, A-C, B-D, B-E, C-F, E-F (voisins pris dans l'ordre alphabétique). Dérouler un parcours en largeur puis un parcours en profondeur récursif depuis A.

BFS — initialisation
On enfile A et on le marque. File = [A], visités = {A}.
BFS — défiler A
On visite A ; ses voisins B et C ne sont pas marqués : on les enfile et on les marque. File = [B, C], visités = {A, B, C}.
BFS — défiler B puis C
B : voisins non marqués D et E enfilés (file = [C, D, E]). C : voisin non marqué F enfilé (A et E déjà vus). File = [D, E, F].
BFS — vider la file
On défile D, E, F : aucun voisin nouveau. Ordre de visite complet obtenu.
DFS récursif
On visite A, on descend chez B (premier voisin), puis chez D (premier voisin non marqué de B). D n'a pas d'autre voisin nouveau : on remonte chez B et l'on descend chez E, puis chez F (voisin de E). Les voisins de F sont C et E : E est déjà marqué, mais C ne l'est pas, donc on visite C. Ordre obtenu : A, B, D, E, F, C.

Résultat : BFS depuis A : A B C D E F (par couches). DFS récursif depuis A : A B D E F C (on descend au plus profond avant de remonter).

Schritt-für-Schritt Erklärung3 Schritte

1
Sur un graphe, le danger ce sont les cycles. La toute première règle d'un parcours est donc de marquer chaque sommet visité pour ne jamais y revenir.
2
Avec une file, on traite les sommets dans leur ordre d'arrivée : on explore d'abord tous les voisins immédiats. C'est le parcours en largeur.
3
Avec une pile, ou par récursivité, on plonge au plus profond d'une branche avant de remonter. C'est le parcours en profondeur.

Erreurs fréquentes

Oublier de marquer les sommets visités : sur un graphe cyclique, le parcours boucle indéfiniment (récursion infinie ou file qui ne se vide jamais).
Marquer un sommet au mauvais moment en BFS : il faut le marquer dès qu'on l'ENFILE (et non quand on le défile), sinon un même voisin peut être enfilé plusieurs fois.
Confondre les ordres : utiliser une file croyant faire du DFS (on obtient un BFS) ou une pile croyant faire du BFS (on obtient un DFS).

Révision active

Soit le graphe non orienté dont les arêtes sont A-B, A-C, B-D, B-E, C-F et E-F (les voisins de chaque sommet sont considérés dans l'ordre alphabétique). Dérouler un parcours en largeur puis un parcours en profondeur récursif depuis A, en donnant à chaque étape l'état de la file ou de la pile d'exploration.

Rappel actif

Rappelle-toi les points clés — puis révèle.

Sources : Programme de spécialité NSI — classe terminale (voie générale), BO spécial n° 8 du 25 juillet 2019 (Ministère de l'Éducation nationale) · Programmes et ressources en NSI — voie générale (Éduscol) (Éduscol — Ministère de l'Éducation nationale)

Existence d'un chemin, détection de cycle et test de connexité#

Standardeduscol-programme-nsi-terminale

Cycle mis en évidence et graphe non connexe

Fig. 6Deux composantes connexes ⇒ le graphe n'est PAS connexe. La première, {A, B, C, D}, contient un CYCLE A-B-C-A (l'arête A-B est mise en évidence) ; la seconde, {E, F}, est isolée.

EXISTENCE D'UN CHEMIN : pour savoir s'il existe un chemin du sommet s au sommet t, on lance un parcours (DFS ou BFS) depuis s ; un chemin existe si et seulement si t fait partie des sommets atteints. Le BFS fournit en prime un chemin de longueur minimale (en nombre d'arêtes).

TEST DE CONNEXITÉ : un graphe (non orienté) est connexe si, depuis un sommet quelconque, le parcours atteint TOUS les sommets. On compare donc le nombre de sommets marqués au nombre total de sommets : égalité ⇔ graphe connexe.

COMPOSANTES CONNEXES : si un parcours depuis un sommet ne marque pas tout le graphe, les sommets non atteints forment d'autres composantes connexes. On relance un parcours depuis un sommet non marqué pour explorer chaque composante.

DÉTECTION DE CYCLE : pendant un DFS d'un graphe non orienté, si l'on rencontre un voisin DÉJÀ marqué qui n'est pas le sommet d'où l'on vient (le « parent »), c'est qu'on a trouvé un cycle. Autre repère utile : un graphe non orienté connexe à n sommets est un arbre (donc sans cycle) si et seulement s'il possède exactement n−1 arêtes.

On retient que ces trois questions (chemin, connexité, cycle) ne réclament aucun nouvel algorithme : ce sont des LECTURES différentes du même parcours (DFS ou BFS) muni du marquage des sommets.

\text{chemin de } s \text{ a } t \iff t \in \text{Atteints}(s)

Existence d'un chemin

Atteints(s) est l'ensemble des sommets marqués par un parcours partant de s. Il suffit de tester l'appartenance de t.

\text{connexe} \iff |\text{Atteints}(s)| = n \quad (n = \text{nombre de sommets})

Test de connexité

Un seul parcours suffit : si tous les sommets sont marqués, le graphe est connexe.

G \text{ connexe sans cycle} \iff G \text{ est un arbre} \iff (\,G \text{ connexe et } m = n - 1\,)

Arbre = connexe + (n−1) arêtes

m est le nombre d'arêtes. Un arbre est exactement un graphe connexe à n−1 arêtes (donc sans cycle).

Exemple corrigé

Chemin, connexité et cycle sur un même graphe

Graphe non orienté de sommets A, B, C, D, E, F et d'arêtes A-B, B-C, C-A, B-D, E-F. Existe-t-il un chemin de A à D ? de A à E ? Le graphe est-il connexe et combien a-t-il de composantes connexes ? Identifier un cycle.

Parcours depuis A
On part de A et l'on marque les sommets atteints : A → B (arête A-B) → C (B-C) et D (B-D) ; depuis C on retrouve A (déjà marqué). Atteints(A) = {A, B, C, D}.
Chemin A→D et A→E
D ∈ Atteints(A) : il existe un chemin de A à D (par exemple A-B-D). E ∉ Atteints(A) : il n'existe AUCUN chemin de A à E.
Connexité et composantes
Atteints(A) compte 4 sommets pour n = 6 : le graphe n'est pas connexe. En relançant un parcours depuis E, on atteint {E, F}. Il y a donc DEUX composantes connexes : {A, B, C, D} et {E, F}.
Détection de cycle
Lors du DFS, depuis C (atteint par A puis B) on rencontre le voisin A, déjà marqué et différent du parent C... ici le parent de C est B, et A ≠ B : on referme le triangle. Le cycle est A-B-C-A.

Résultat : Chemin A→D : oui (A-B-D). Chemin A→E : non. Graphe non connexe, 2 composantes connexes {A,B,C,D} et {E,F}. Cycle présent : A-B-C-A.

Erreurs fréquentes

Conclure à la non-connexité parce qu'on n'a pas atteint un sommet, alors qu'on a simplement oublié de marquer/explorer certains voisins, ou parti d'une seule composante sans relancer le parcours.
En détection de cycle sur un graphe non orienté, oublier d'exclure le « parent » : retrouver le sommet d'où l'on vient n'est PAS un cycle, c'est simplement l'arête qu'on vient d'emprunter.
Appliquer la règle « n−1 arêtes ⇔ pas de cycle » sans vérifier la connexité : la caractérisation des arbres exige le graphe connexe ET n−1 arêtes.

Révision active

On considère le graphe non orienté de sommets A, B, C, D, E, F et d'arêtes A-B, B-C, C-A, B-D, E-F. Déterminer s'il existe un chemin de A vers D, puis de A vers E ; dire si le graphe est connexe et combien il a de composantes connexes ; enfin, identifier un cycle et justifier sa présence.

Rappel actif

Rappelle-toi les points clés — puis révèle.

Sources : Programme de spécialité NSI — classe terminale (voie générale), BO spécial n° 8 du 25 juillet 2019 (Ministère de l'Éducation nationale) · Programmes et ressources en NSI — voie générale (Éduscol) (Éduscol — Ministère de l'Éducation nationale)

Plus court chemin dans un graphe pondéré : algorithme de Dijkstra#

Approfondissementeduscol-programme-nsi-terminale

Graphe pondéré et plus court chemin de A à E (Dijkstra)

Fig. 7Graphe pondéré ; les poids sont portés sur les arêtes. Le plus court chemin de A à E est A-B-C-D-E, de longueur 2 + 1 + 3 + 1 = 7. Distances finales depuis A : A = 0, B = 2, C = 3, D = 6, E = 7. Voir Fig. suivante pour le déroulé de Dijkstra.

CONTEXTE : dans un graphe PONDÉRÉ, chaque arête porte un poids (distance, durée, coût). Le « plus court chemin » de s à t est celui dont la SOMME des poids est minimale. Le BFS ne suffit plus (il minimise le nombre d'arêtes, pas la somme des poids).

HYPOTHÈSE : l'algorithme de Dijkstra exige des poids POSITIFS (ou nuls). Sous cette condition, il calcule la plus courte distance de la source s vers tous les autres sommets.

PRINCIPE : on maintient pour chaque sommet une distance provisoire (∞ au départ, 0 pour s). À chaque étape, on choisit le sommet NON encore fixé de plus petite distance provisoire, on le « fixe » (sa distance devient définitive), puis on RELÂCHE ses arêtes : pour chaque voisin v, si dist(u) + poids(u,v) est plus petit que dist(v), on met à jour dist(v) et on retient u comme prédécesseur.

TERMINAISON ET RÉSULTAT : une fois tous les sommets fixés, les distances sont les plus courtes distances depuis s. En suivant les prédécesseurs de t vers s, on reconstruit un plus court chemin. On utilise souvent une FILE de priorité pour choisir efficacement le sommet de plus petite distance.

APPLICATION : Dijkstra est au cœur du calcul d'itinéraires (GPS) et du routage réseau — par exemple le protocole OSPF — ce qui relie ce thème à celui des réseaux et protocoles.

d(s,t) = \min_{\text{chemins } s \to t} \ \sum_{\text{aretes } (u,v) \text{ du chemin}} \text{poids}(u,v)

Définition du plus court chemin pondéré

On minimise la somme des poids des arêtes le long d'un chemin de s à t (et non leur nombre).

\text{si } \text{dist}(u) + \text{poids}(u,v) < \text{dist}(v) \ \text{alors} \ \text{dist}(v) \leftarrow \text{dist}(u) + \text{poids}(u,v)

Relâchement d'une arête

Cœur de l'algorithme : on améliore la distance provisoire de v si passer par u est plus court ; on mémorise alors u comme prédécesseur de v.

Dérouler Dijkstra depuis A : distances et mises à jour

Fig. 8À chaque étape, Dijkstra FIXE le sommet non visité de plus petite distance, puis relâche ses arêtes (on garde la plus courte). On obtient dist(E) = 7 (cellule mise en évidence), via le chemin A-B-C-D-E.

Exemple corrigé

Dérouler Dijkstra et reconstruire le plus court chemin

Graphe pondéré non orienté d'arêtes A-B (2), A-C (5), B-C (1), B-D (7), C-D (3), C-E (6), D-E (1). Appliquer Dijkstra depuis A : distances minimales vers chaque sommet, puis un plus court chemin de A à E et sa longueur.

Initialisation
dist(A)=0 ; tous les autres à +∞. Aucun sommet n'est encore fixé.
Fixer A (dist 0), relâcher
Voisins de A : B (0+2=2) et C (0+5=5). On met à jour dist(B)=2 (préd. A) et dist(C)=5 (préd. A).
Fixer B (plus petite, dist 2), relâcher
Voisins de B : C (2+1=3 < 5 → dist(C)=3, préd. B) et D (2+7=9 → dist(D)=9, préd. B).
Fixer C (dist 3), relâcher
Voisins de C : D (3+3=6 < 9 → dist(D)=6, préd. C) et E (3+6=9 → dist(E)=9, préd. C).
Fixer D (dist 6), relâcher
Voisin restant E : 6+1=7 < 9 → dist(E)=7, préd. D. Puis on fixe E (dist 7) : terminé.
Reconstruire le chemin A→E
Prédécesseurs : E←D←C←B←A. On remonte donc E, D, C, B, A puis on inverse.

Résultat : Distances minimales depuis A : A=0, B=2, C=3, D=6, E=7. Plus court chemin de A à E : A-B-C-D-E, de longueur totale 7.

Schritt-für-Schritt Erklärung4 Schritte

1
Dans un graphe pondéré, on ne compte plus les arêtes : on additionne leurs poids. Le plus court chemin est celui de somme minimale.
2
Dijkstra part de la source à distance zéro, tout le reste à l'infini. À chaque tour, il fixe le sommet non traité le plus proche.
3
Puis il relâche les arêtes de ce sommet : si passer par lui raccourcit un voisin, on met à jour la distance et le prédécesseur.
4
Quand tous les sommets sont fixés, on remonte les prédécesseurs pour reconstruire le chemin. Ici, A vers E coûte sept.

Erreurs fréquentes

Appliquer Dijkstra avec des poids NÉGATIFS : l'algorithme peut alors donner un résultat faux (un sommet fixé trop tôt ne sera plus corrigé).
Confondre « plus court en nombre d'arêtes » (BFS) et « plus court en poids » (Dijkstra) : un chemin à plus d'arêtes mais à poids plus faible peut être le plus court.
Oublier de mettre à jour le prédécesseur lors d'un relâchement : on retrouve la bonne distance mais on est incapable de reconstruire le chemin.

Révision active

Soit le graphe pondéré non orienté de sommets A, B, C, D, E et d'arêtes : A-B (2), A-C (5), B-C (1), B-D (7), C-D (3), C-E (6), D-E (1). Appliquer l'algorithme de Dijkstra depuis A : donner la distance la plus courte de A à chaque sommet, puis un plus court chemin de A à E avec sa longueur totale.

Rappel actif

Rappelle-toi les points clés — puis révèle.

Sources : Programme de spécialité NSI — classe terminale (voie générale), BO spécial n° 8 du 25 juillet 2019 (Ministère de l'Éducation nationale) · Programmes et ressources en NSI — voie générale (Éduscol) (Éduscol — Ministère de l'Éducation nationale)

Points clés

Les quatre parcours d'un arbre binaire

Points clés

Construire un ABR, lire le parcours infixe et tracer une recherche

Points clés

Dérouler un BFS et un DFS depuis A

Points clés

Chemin, connexité et cycle sur un même graphe

Points clés

Dérouler Dijkstra et reconstruire le plus court chemin

Sources

Algorithmes sur les arbres et les graphes

Points clés

Les quatre parcours d'un arbre binaire

Points clés

Construire un ABR, lire le parcours infixe et tracer une recherche

Points clés

Dérouler un BFS et un DFS depuis A

Points clés

Chemin, connexité et cycle sur un même graphe

Points clés

Dérouler Dijkstra et reconstruire le plus court chemin

Sources