Sauver la matrice creuse — le dictionnaire d'arcs

def listes_vers_arcs(R: dict) -> dict:
    return {(u, v): R[u][v] for u in R for v in R[u]}

• Comparatif : cette structure offre une complexité spatiale optimale en $O(m)$ et permet d'accéder au poids d'un arc ou de valider son existence en $O(1)$.
• Limite : sa principale faiblesse est l'impossibilité de lister efficacement les voisins d'un sommet. Pour trouver les successeurs de $u$, il faut parcourir l'ensemble des $m$ clés du dictionnaire d'arcs, soit un coût prohibitif en $O(m)$ (à comparer au coût direct en $O(d)$ des listes d'adjacence).