Corrigé Mines-Ponts 2026 Informatique II MPI — Partie 2 (2.3) (Q20 à Q23) : Parcours en largeur et Dijkstra initialisé par le parcours

Sujet officiel du concours Mines-Ponts, session 2026, épreuve Informatique II MPI. Corrigé rédigé par Ibrahim Alame.

Énoncé

Le monde, représenté en CSR (partie précédente), est supposé fortement connexe ; les coûts des passages sont strictement positifs. On dispose, sans avoir à les écrire, d'une file FIFO d'entiers (file_init(n) crée une file vide de capacité n) et d'un tas min de salles munies d'une priorité entière (tasMin_depile retire et renvoie une salle de priorité minimale) :


typedef struct _file file;
file* file_init(int taille);
bool  file_vide(file *f);
void  file_enfile(file *f, int x);
int   file_defile(file *f);
void  file_libere(file *f);

typedef struct _tasMin tasMin;
tasMin* tasMin_init(void);
bool    tasMin_vide(tasMin *tm);
void    tasMin_empile(tasMin *tm, int salle, int priorite);
int     tasMin_depile(tasMin *tm);
void    tasMin_libere(tasMin *tm);

Q20. Expliquer comment un parcours en largeur depuis s fournit, pour chaque salle t, un chemin de nombre minimal de passages ; donner un cas où ces chemins sont aussi de coût minimal.
Q21. Écrire int* bfs_cout(mondeCSR* mc, int s), qui renvoie un tableau dist (alloué dynamiquement, de taille mc->nb_salles) où dist[u] est la somme des coûts le long du chemin à nombre minimal de passages trouvé par le parcours en largeur de s à u.
Q22. Expliquer pourquoi dist[u] majore le coût minimal d'un chemin de s à u.
Rappel : Dijkstra part d'un tableau dist rempli de $+ \infty$ et explore le graphe depuis s à l'aide d'une file de priorité ; un sommet découvert u y est inséré avec la priorité dist[u], et les sommets sont explorés dans l'ordre de sortie de la file. Ici, dist est initialisé par bfs_cout(mc, s) au lieu de $+ \infty$ , et l'on traite tous les sommets (pas de sommet d'arrivée).
Q23. Écrire void dijkstra(mondeCSR* mc, int s, int* dist), qui transforme le tableau dist calculé par bfs_cout(mc, s) en le tableau des coûts minimaux depuis s (sans reconstruire les chemins).

Corrigé

Les deux fonctions ont été compilées (gcc -Wall -Wextra -std=c99, sans avertissement) et exécutées avec une file et un tas binaire écrits pour le test : sur le graphe de Q12 depuis chacune des cinq salles (depuis $0$ : dist $= [0, 2, 3, 5, 6]$ , déjà minimal) ; sur un graphe où le parcours en largeur ne donne pas le coût minimal (ci-dessous) ; sur un monde d'une seule salle ; enfin sur $3000$ graphes aléatoires fortement connexes de $1$ à $9$ salles, soit $14856$ sources, comparés à Floyd-Warshall : aucune erreur, et jamais plus de $n p + 1$ insertions dans le tas. Aucune fuite mémoire (leaks).

Q20. Le parcours en largeur range les salles à traiter dans une file. On attribue à s le niveau $k (s) = 0$ et on l'enfile ; tant que la file n'est pas vide, on défile une salle $u$ et chaque salle $v$ atteinte par un passage $u \to v$ et pas encore découverte reçoit le niveau $k (v) = k (u) + 1$ , le « père » $u$ , et est enfilée. Chaque salle est découverte au plus une fois, et toutes le sont puisque le monde est fortement connexe. En remontant les pères depuis $t$ , on obtient un chemin de $s$ à $t$ de $k (t)$ passages. Montrons que $k (t)$ est le nombre minimal $d (t)$ de passages d'un chemin de $s$ à $t$ .

Invariant de la file. Si elle contient $v_{1}, \dots, v_{r}$ (tête en premier), alors $k (v_{1}) ⩽ \dots ⩽ k (v_{r}) ⩽ k (v_{1}) + 1$ : c'est vrai au départ (une seule salle), et défiler $v_{1}$ puis enfiler des salles de niveau $k (v_{1}) + 1$ le préserve. Les salles sortent donc de la file par niveaux croissants : d'abord le niveau $0$ , puis toutes celles du niveau $1$ , etc.
$k (t) ⩾ d (t)$ , car le chemin des pères comporte $k (t)$ passages.
$k (t) ⩽ d (t)$ , par récurrence sur $ℓ = d (t)$ . Si $ℓ = 0$ , $t = s$ . Sinon, soit $u$ l'avant-dernière salle d'un chemin de $ℓ$ passages : $d (u) = ℓ - 1$ , donc $k (u) = ℓ - 1$ par hypothèse de récurrence. Quand $u$ est défilée, soit $t$ est découverte à cet instant et $k (t) = ℓ$ , soit elle l'a été plus tôt par une salle $w$ défilée avant $u$ , donc de niveau $k (w) ⩽ k (u)$ , et $k (t) = k (w) + 1 ⩽ ℓ$ .

Un cas de coût minimal : si tous les passages ont le même coût $c > 0$ , un chemin de $p$ passages coûte $c p$ , donc minimiser le coût revient à minimiser le nombre de passages. (Autre cas : un monde réduit à un circuit $0 \to 1 \to \dots \to n - 1 \to 0$ , où chaque salle n'est atteinte depuis s que par un seul chemin sans répétition de salle.)

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 →