Corrigé CCINP 2025 Informatique PC-PSI — Parties III.1 et III.2 (Q22 à Q28) : Organisation d'un trek : plus proche voisin glouton, puis algorithme de Dijkstra

Sujet officiel du concours CCINP, session 2025, épreuve Informatique PC-PSI. Corrigé rédigé par Ibrahim Alame.

Énoncé

Graphe non orienté : sommets = points de départ ou d'arrivée, arêtes = randonnées d'une journée, de poids leur difficulté (de $1$ à $5$ , appelée « distance »). Le graphe $G$ (figure 3) est codé par un dictionnaire de dictionnaires : G['a'] = \{'b':3, 'c':2, 'd':4\}, etc.

Figure 3 — Graphe $G$ .

mystere2(graph, Sd, Sf) part de sTraite = Sd, chemin = [Sd] ; tant que sTraite != Sf, elle ajoute sTraite à dejaVisites, puis (lignes 15 à 19) parcourt les voisins de sTraite et retient dans sInter et d le voisin non visité de poids d'arête strictement minimal (d initialisé à l'infini, sInter à sTraite) ; elle ajoute d à diffChemin, sInter au chemin, et passe à sInter. Elle renvoie (chemin, diffChemin).

Q22. Expliquer les lignes 15 à 19 ; type d'algorithme.
Q23. Que renvoie mystere2(G, "a", "f") ?
Q24. Ce programme trouve-t-il le chemin de difficulté cumulée minimale ?

Dijkstra (code du sujet) : cherche_min(dico, liste) renvoie le premier sommet de liste, présent dans dico, de dico[s][0] strictement minimal. unpas(graph, s, distance, dejaVisites, avisiter) retire s de avisiter, l'ajoute à dejaVisites, puis, pour chaque voisin v non visité, l'ajoute en fin de avisiter s'il n'y est pas (lignes 14 et 15) et pose distance[v] = (distance[s][0] + graph[s][v], s) si v n'est pas une clé ou si cette valeur est meilleure. dijkstra(graph, Sd, Sf) part de aVisiter = [Sd], distance = \{Sd: (0, Sd)\} et répète sTraite = cherche_min(distance, aVisiter) puis unpas(...) tant que sTraite != Sf ; elle renvoie distance.

Q25. Compléter le tableau du DR (variables après chaque tour, X pour une clé absente) pour dijkstra(G, "a", "f").
Q26. Compléter la reconstruction du chemin (lignes 8 à 10 : boucle partant de s = sFin, chemin = [s], puis chemin.reverse()) et la ligne 15 qui affiche la difficulté minimale.
Q27. Comment diminuer le nombre de tests d'appartenance à une liste, notamment lignes 14 et 15 ?

Figure 4 — Graphe $G_{1}$ (voisins rangés par ordre alphabétique).

Q28. Lister les sommets visités par dijkstra(G1, "a1", "j1"), puis par dijkstra(G1, "j1", "a1").

Corrigé

Q22. Les lignes 15 à 19 parcourent les voisins sommet du sommet courant sTraite ; parmi ceux qui ne sont pas encore visités, elles retiennent celui dont l'arête depuis sTraite a la plus petite difficulté : en sortie de boucle, sInter est ce voisin et d la difficulté de la randonnée correspondante (recherche séquentielle d'un minimum, initialisée à l'infini). En une phrase : depuis le point où il se trouve, le randonneur part vers le point voisin non encore visité par la randonnée la plus facile.

C'est un algorithme glouton : à chaque étape on fait le choix localement le meilleur (l'étape la plus facile) sans jamais le remettre en cause, ni anticiper la suite (stratégie du « plus proche voisin »).

Q23. Déroulement (les voisins sont examinés dans l'ordre du dictionnaire) :

depuis a : voisins b ( $3$ ), c ( $2$ ), d ( $4$ ) : on va en c, difficulté cumulée $2$ ;
depuis c : a est visité, reste d ( $4$ ) : cumul $6$ ;
depuis d : a, c visités ; b ( $2$ ), e ( $1$ ), f ( $4$ ) : on va en e, cumul $7$ ;
depuis e : d visité ; b ( $5$ ), f ( $1$ ) : on va en f, cumul $8$ ; sTraite == "f", fin.

L'appel renvoie le tuple (['a', 'c', 'd', 'e', 'f'], 8) (vérifié en exécutant le code du sujet).

Q24. Non. Contre-exemple sur $G$ lui-même : le chemin a–d–e–f a une difficulté $4 + 1 + 1 = 6 < 8$ . Le premier choix glouton (c, la randonnée la plus facile au départ) mène dans un cul-de-sac coûteux (la seule sortie de c coûte $4$ ) : un minimum local à chaque étape ne donne pas un minimum global de la somme.

Pire, l'algorithme peut ne pas aboutir : si tous les voisins de sTraite sont déjà visités (impasse), d reste infini, sInter reste égal à sTraite et la boucle ne termine plus. Sur le graphe $G_{1}$ de la figure 4, mystere2(G1, "a1", "h1") va de a1 en b1 puis en e1, feuille dont l'unique voisin est visité : boucle infinie. Le jury : « un contre-exemple est le meilleur moyen de montrer le problème de l'algorithme glouton ».

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →