Corrigé Banque PT 2025 Informatique et modélisation PT — Partie G (Q44 à Q48) : Plus court chemin : dictionnaire d'adjacence et algorithme de Dijkstra

Q44. Chaque arête non orientée apparaît dans les listes de ses deux extrémités, avec son poids :

g = {0: [(1, 5), (2, 6)],
     1: [(0, 5), (3, 8), (4, 3)],
     2: [(0, 6), (4, 1), (5, 9)],
     3: [(1, 8), (4, 2), (5, 4)],
     4: [(1, 3), (2, 1), (3, 2), (5, 7)],
     5: [(2, 9), (3, 4), (4, 7)]}

On contrôle la cohérence : $9$ arêtes, donc $18$ couples au total ($2+3+3+3+4+3=18$), et chaque couple $(v,w)$ de la liste de $u$ a son symétrique $(u,w)$ dans celle de $v$.

Pourquoi un dictionnaire d'adjacence ? Le graphe est peu dense : $9$ arêtes pour $\left(\genfrac{}{}{0ex}{}{6}{2}\right)=15$ paires possibles, chaque sommet ayant 2 à 4 voisins. Une matrice d'adjacence occuperait $n^2=36$ cases, la plupart vides (un réseau routier réel compte des millions de sommets de degré 3 ou 4 : la matrice serait gigantesque et presque vide). Le dictionnaire n'occupe qu'une place proportionnelle à $n+$ nombre d'arêtes, et il donne directement la liste des voisins d'un sommet, ce que fait Dijkstra à chaque visite (au lieu de parcourir une ligne entière de $n$ cases).

Le hachage. Un dictionnaire Python est une table de hachage. Une fonction de hachage transforme chaque clé en un entier, qui sert à calculer directement l'indice de la case d'un tableau où la valeur est rangée. L'accès à la valeur associée à une clé ne demande donc aucun parcours : il se fait en temps constant en moyenne, $O(1)$. Les collisions (deux clés envoyées dans la même case) sont rares si la table est assez grande et sont gérées par le langage ; c'est pourquoi les clés doivent être non mutables (entiers, chaînes, tuples). Ce que le correcteur attend : le mot « hachage », peu cité dans les copies.