Corrigé Centrale 2025 Option informatique MP — Partie IV (Q35 à Q42) : Dijkstra multicritère et optimums de Pareto

Sujet officiel du concours Centrale, session 2025, épreuve Option informatique MP. Corrigé rédigé par Ibrahim Alame.

Énoncé

Le réseau est un graphe orienté $G = (V, E)$ ; chaque arc $e$ porte un couple d'entiers positifs $(t (e), p (e))$ , durée et prix. Figure 6 ( $s = 0$ , $t = 5$ ) :

Le poids d'un chemin $C = (e_{1}, \dots, e_{T})$ est le triplet $w (C) = (\sum_{k} t (e_{k}), T - 1, \sum_{k} p (e_{k}))$ (durée, nombre de correspondances, prix) ; on note $\oplus$ la somme composante par composante des triplets (non prédéfinie en OCaml). Les optimums de Pareto (ordre produit $⪯$ de la partie II) parmi les poids des chemins de $s$ à $v$ sont les poids recherchés.


type poids = int * int * int        (* ordonnés lexicographiquement par OCaml *)
type arc = {dest : int; temps : int; prix : int}
type reseau_ferroviaire = arc list array   (* reseau.(i) : arcs partant de i *)

Algorithme 1 (un sommet peut figurer plusieurs fois dans la file) :


1  d[v] <- [] pour tout sommet v
2  Q <- file de priorité vide
3  ajouter s à Q avec la priorité (0, -1, 0)
4  tant que Q est non vide :
5      défiler v de priorité pi_v minimale (ordre lexicographique)
6      si aucun élément de d[v] n'est plus petit que pi_v :
7          supprimer de d[v] les éléments plus grands que pi_v
8          ajouter pi_v à d[v]
9          pour chaque arc e de v vers w :
10             enfiler w avec la priorité pi_v (+) (t(e), 1, p(e))

Sur la figure 6, avec $s = 0$ , après quatre itérations :

priorité	(3,0,88)	(4,0,84)	(4,2,110)	(5,1,40)	(5,1,50)	(6,0,60)	(6,1,120)
sommet	2	4	5	5	5	5	4

`d.(0)`	`d.(1)`	`d.(2)`	`d.(3)`	`d.(4)`	`d.(5)`
[(0,-1,0)]	[(1,0,44)]	[ ]	[(3,0,6); (2,1,76)]	[ ]	[ ]

Q35. Justifier qu'on peut utiliser les files de priorité de la partie I en y stockant des couples $(π_{v}, v)$ .
Q36. Détailler l'évolution de $Q$ et de d (de type poids list array) lors des trois itérations suivantes.
Q37. Écrire dijkstra_pareto : reseau_ferroviaire -> int -> poids list array, qui calcule pour chaque sommet la liste des poids optimums de Pareto des chemins depuis $s$ (fonctions des parties I.1 et II.4 utilisables, avec element égal à poids).
Q38. Montrer que le poids d'un chemin non élémentaire de $u$ à $v$ n'est pas un optimum de Pareto parmi les poids des chemins de $u$ à $v$ .
Q39. Si le poids d'un chemin $C_{s, t}$ est un optimum de Pareto parmi les chemins de $s$ à $t$ , montrer qu'il en est de même pour tout préfixe $C_{s, u}$ parmi les chemins de $s$ à $u$ .
Q40. Montrer que si $π_{v}$ satisfait le test de la ligne 6, c'est un optimum de Pareto parmi les poids des chemins de $s$ à $v$ ; en déduire une optimisation.
Q41. Montrer qu'à la fin, d[v] contient exactement les poids optimums de Pareto des chemins de $s$ à $v$ , et que l'algorithme termine.
Q42. Proposer une fonction donnant tous les chemins de $s$ à $t$ dont le poids est un optimum de Pareto (signature, structure utilisée).

Corrigé

Conventions. « Positif » signifie ici $\geq 0$ . Le test de la ligne 6 (« plus petit ») est lu pour l'ordre produit et au sens large : aucun $y$ de d[v] ne vérifie $y ⪯ π_{v}$ ; c'est ce que teste la fonction existe_plus_petit de Q19, que l'énoncé invite à réutiliser, et cette lecture redonne bien l'état fourni après quatre itérations. On note $⊑$ l'ordre lexicographique et $⊏$ sa version stricte. Le chemin vide de $s$ à $s$ a pour poids $(0, - 1, 0)$ , et pour un chemin $C^{'}$ prolongé par un arc $e$ , $w (C^{'} e) = w (C^{'}) \oplus (t (e), 1, p (e))$ ; plus généralement, si $C_{2}$ a $T_{2}$ arcs, $w (C_{1} C_{2}) = w (C_{1}) \oplus (\sum_{C_{2}} t, T_{2}, \sum_{C_{2}} p)$ .

Q35. Les fonctions de la partie I sont polymorphes : elles s'appliquent au type (poids * int) arbre. L'ordre utilisé est l'ordre implicite d'OCaml, lexicographique sur les couples : $(π, v) \leq (π^{'}, v^{'})$ ssi $π ⊏ π^{'}$ , ou $π = π^{'}$ et $v \leq v^{'}$ , et sur les triplets $π$ c'est encore l'ordre lexicographique. Le couple renvoyé par min_valeur a donc une priorité $π$ minimale pour $⊑$ (le numéro de sommet ne sert qu'à départager deux priorités égales, ce qui est sans importance), et le sommet associé est lu dans la seconde composante. Enfin un tas peut contenir des valeurs égales ou plusieurs couples de même sommet : un sommet peut figurer plusieurs fois dans la file, comme l'exige l'algorithme.

Q36. On écrit les éléments de $Q$ sous la forme $(π, v)$ , rangés par ordre croissant.

Itération 5. On défile $((3, 0, 88), 2)$ . d.(2) est vide : le test réussit, d.(2) devient $[(3, 0, 88)]$ . Les arcs issus de $2$ ajoutent $((4, 1, 94), 4)$ , $((4, 1, 120), 5)$ et $((6, 1, 93), 3)$ . Alors $Q$ contient $((4, 0, 84), 4)$ , $((4, 1, 94), 4)$ , $((4, 1, 120), 5)$ , $((4, 2, 110), 5)$ , $((5, 1, 40), 5)$ , $((5, 1, 50), 5)$ , $((6, 0, 60), 5)$ , $((6, 1, 93), 3)$ , $((6, 1, 120), 4)$ .

Itération 6. On défile $((4, 0, 84), 4)$ . d.(4) est vide : d.(4) devient $[(4, 0, 84)]$ , et l'arc $4 \to 5$ ajoute $((5, 1, 90), 5)$ . Alors $Q$ contient $((4, 1, 94), 4)$ , $((4, 1, 120), 5)$ , $((4, 2, 110), 5)$ , $((5, 1, 40), 5)$ , $((5, 1, 50), 5)$ , $((5, 1, 90), 5)$ , $((6, 0, 60), 5)$ , $((6, 1, 93), 3)$ , $((6, 1, 120), 4)$ .

Itération 7. On défile $((4, 1, 94), 4)$ . Or $(4, 0, 84) ⪯ (4, 1, 94)$ (car $4 \leq 4$ , $0 \leq 1$ , $84 \leq 94$ ) : le test échoue, d est inchangé et rien n'est enfilé. $Q$ contient $((4, 1, 120), 5)$ , $((4, 2, 110), 5)$ , $((5, 1, 40), 5)$ , $((5, 1, 50), 5)$ , $((5, 1, 90), 5)$ , $((6, 0, 60), 5)$ , $((6, 1, 93), 3)$ , $((6, 1, 120), 4)$ .

Après ces trois itérations, d vaut $[(0, - 1, 0)]$ , $[(1, 0, 44)]$ , $[(3, 0, 88)]$ , $[(3, 0, 6); (2, 1, 76)]$ , $[(4, 0, 84)]$ , $[]$ . (Trace obtenue aussi par exécution d'une version instrumentée de la fonction de Q37, qui redonne d'abord exactement l'état de l'énoncé après quatre itérations.)

Q37. On utilise insere, min_valeur, suppression_min (partie I) et existe_plus_petit, ajoute_plus_petit (Q19, Q20), avec l'ordre produit sur les triplets :


let inferieur ((a, b, c) : poids) ((a', b', c') : poids) : bool =
  a <= a' && b <= b' && c <= c'

let plus ((t1, c1, p1) : poids) ((t2, c2, p2) : poids) : poids =
  (t1 + t2, c1 + c2, p1 + p2)

let dijkstra_pareto (reseau : reseau_ferroviaire) (s : int) : poids list array =
  let n = Array.length reseau in
  let d = Array.make n [] in
  let q = ref (insere ((0, -1, 0), s) Vide) in
  while !q <> Vide do
    let (pi, v) = min_valeur !q in
    q := suppression_min !q;
    if not (existe_plus_petit pi d.(v)) then begin
      d.(v) <- ajoute_plus_petit pi d.(v);
      List.iter
        (fun e -> q := insere (plus pi (e.temps, 1, e.prix), e.dest) !q)
        reseau.(v)
    end
  done;
  d

La fonction auxiliaire plus (type poids -> poids -> poids) réalise $\oplus$ . Le corps de la boucle suit l'algorithme 1 ligne à ligne : ajoute_plus_petit réalise les lignes 7 et 8, List.iter la boucle des lignes 9 et 10. Sur la figure 6, avec $s = 0$ , on obtient d.(5) = [(6,0,60); (5,1,40); (4,2,110); (4,1,120)] : ce sont les trajets (a), (d), (c) et (g) de la figure 3. Tests : sur $3000$ graphes aléatoires d'au plus $6$ sommets, avec des durées et des prix nuls ou non et des boucles, le résultat coïncide, pour chaque sommet, avec les optimums de Pareto des poids de tous les chemins élémentaires énumérés par un parcours exhaustif (ce qui suffit d'après Q38).

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 →