Corrigé CCINP 2025 Informatique PC-PSI — Partie III.3 (Q29 à Q34) : Dijkstra bidirectionnel : déroulement, critère d'arrêt et correction partielle

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

Énoncé

On mène deux recherches de Dijkstra (fonctions cherche_min et unpas de la partie III.2) : forward depuis le départ (variables aVisiterF, dejaVisitesF, distanceF) et backward depuis l'arrivée (aVisiterB, dejaVisitesB, distanceB) ; distanceF et distanceB associent à chaque sommet un couple (distance, prédécesseur), distance initialement infinie, sauf $0$ pour le départ (resp. l'arrivée). On note $d_{F} (i)$ , $d_{B} (i)$ les distances courantes et

$F_{m i n} = i \in aVisiterF min d_{F} (i), B_{m i n} = i \in aVisiterB min d_{B} (i), B F_{m i n} = i min (d_{F} (i) + d_{B} (i)),$

avec initialement $F_{m i n} = B_{m i n} = 0$ et $B F_{m i n} = + \infty$ . À chaque étape : si $B F_{m i n} ⩽ F_{m i n} + B_{m i n}$ , on s'arrête et l'on renvoie $B F_{m i n}$ ; sinon on fait une étape forward (cherche_min puis unpas avec les variables F) si $F_{m i n} < B_{m i n}$ , backward si $B_{m i n} < F_{m i n}$ , et en cas d'égalité du côté dont la liste à visiter est la plus courte (forward si elles ont même longueur) ; puis on recalcule $F_{m i n}$ , $B_{m i n}$ , $B F_{m i n}$ .

Figure 3 — Graphe $G$ (rappel).

Q29. Sur $G$ , de a vers f : compléter la dernière ligne du tableau du DR des étapes (sens F ou B, valeurs de $d_{F}$ et $d_{B}$ pour chaque sommet).
Q30. Renvoyer $B F_{m i n}$ dès qu'un sommet a été atteint par les deux recherches donne-t-il le chemin minimal ?
Q31. Compléter dijkstra_bidirectionnel(graph, Sd, Sf) : lignes 4 et 5 (initialisation backward), 13 (condition du while), 21, 22 (calculs de Fmin, Bmin, de la forme min([...[v][0] for v in aVisiterF if v in distanceF])) et 23 (L = [... for v in distanceB if v in distanceF], puis BFmin = min(L)).

On note $d (x, y)$ la distance minimale entre deux sommets. On admet la correction de Dijkstra : pour tout sommet visité, la distance calculée est exacte, et les sommets non visités sont plus loin que les sommets déjà visités. Par l'absurde, supposons que l'algorithme se termine et qu'un chemin $s = s_{0}, s_{1}, \dots, s_{n} = t$ du départ à l'arrivée ait une longueur $d < B F_{m i n}$ .

Q32. Montrer que chaque $s_{i}$ est dans dejaVisitesF ou dans dejaVisitesB.
Q33. En déduire un indice $i_{0}$ tel que $s_{i_{0}}$ ait été visité par la recherche forward et $s_{i_{0} + 1}$ par la recherche backward.
Q34. En déduire la correction partielle de l'algorithme.

Corrigé

Q29. Déroulement (les valeurs $F_{m i n}$ , $B_{m i n}$ , $B F_{m i n}$ sont celles recalculées en fin d'étape) :

étape 1 : $F_{m i n} = B_{m i n} = 0$ et les deux listes à visiter ont un élément : forward, on visite a ; $d_{F}$ devient $3$ , $2$ , $4$ pour b, c, d. Alors $F_{m i n} = 2$ , $B_{m i n} = 0$ , $B F_{m i n} = + \infty$ (aucun sommet n'a deux distances finies) ;
étape 2 : $B_{m i n} < F_{m i n}$ : backward, on visite f ; $d_{B} (d) = 4$ , $d_{B} (e) = 1$ . Alors $F_{m i n} = 2$ , $B_{m i n} = 1$ et $B F_{m i n} = d_{F} (d) + d_{B} (d) = 8$ ; $8 > 3$ , on continue ;
étape 3 : $B_{m i n} < F_{m i n}$ : backward, on visite e ( $d_{B} = 1$ ) ; $d_{B} (b) = 1 + 5 = 6$ , $d_{B} (d) = 1 + 1 = 2 < 4$ . Alors $F_{m i n} = 2$ , $B_{m i n} = 2$ , $B F_{m i n} = min (3 + 6, 4 + 2) = 6$ ; $6 > 4$ , on continue ;
étape 4 : $F_{m i n} = B_{m i n} = 2$ , mais aVisiterF = [b, c, d] a trois éléments et aVisiterB = [d, b] deux : backward, on visite d ( $d_{B} = 2$ ) ; $d_{B} (a) = 2 + 4 = 6$ , $d_{B} (b) = 2 + 2 = 4 < 6$ , $d_{B} (c) = 2 + 4 = 6$ . Alors $F_{m i n} = 2$ , $B_{m i n} = min (6, 4, 6) = 4$ et $B F_{m i n} = 6$ .

Au test suivant, $B F_{m i n} = 6 ⩽ F_{m i n} + B_{m i n} = 2 + 4$ : l'algorithme s'arrête et renvoie $6$ , la bonne distance (Q25). Tableau des étapes, chaque case donnant $d_{F} / d_{B}$ ; la dernière ligne (étape 4) est celle à compléter sur le DR :

Étape	Sens, sommet	a	b	c	d	e	f
0	initialisation	$0 / \infty$	$\infty / \infty$	$\infty / \infty$	$\infty / \infty$	$\infty / \infty$	$\infty / 0$
1	F, a	$0 / \infty$	$3 / \infty$	$2 / \infty$	$4 / \infty$	$\infty / \infty$	$\infty / 0$
2	B, f	$0 / \infty$	$3 / \infty$	$2 / \infty$	$4 / 4$	$\infty / 1$	$\infty / 0$
3	B, e	$0 / \infty$	$3 / 6$	$2 / \infty$	$4 / 2$	$\infty / 1$	$\infty / 0$
4	B, d	$0 / 6$	$3 / 4$	$2 / 6$	$4 / 2$	$\infty / 1$	$\infty / 0$

Prédécesseurs à la dernière ligne : forward, a pour b, c, d ; backward, d pour a, b, c, e pour d, f pour e. La valeur $6$ est réalisée en d : a–d (forward) puis d–e–f (backward). Ce tableau a été obtenu en exécutant la fonction complétée de Q31 avec un print à chaque étape.

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 →