Graphes : représentation et parcours

Un graphe non orienté est un couple $G = (S, A)$ où $S$ est un ensemble fini non vide, dont les éléments sont les sommets, et où $A$ est un ensemble de paires de sommets : $A \subset \big\{ \{u, v\} \ ; \ u \in S, \ v \in S, \ u \neq v \big\}$. Les éléments de $A$ sont les arêtes. Deux sommets $u$ et $v$ sont adjacents, ou voisins, lorsque $\{u, v\} \in A$. En français : un graphe, c'est une liste finie de points, et la liste des paires de points reliés. Dans toute la fiche on pose $n = \mathrm{card}(S)$ et $m = \mathrm{card}(A)$, et toute complexité s'exprime en fonction de ces deux entiers.

Un graphe orienté est un couple $G = (S, A)$ où $A \subset S \times S$ : les éléments de $A$ sont des couples $(u, v)$, appelés arcs, et non des paires. L'arc $(u, v)$ va de $u$ vers $v$ : on dit que $v$ est un successeur de $u$ et que $u$ est un prédécesseur de $v$. L'ordre compte : $(u, v) \in A$ n'entraîne pas $(v, u) \in A$. Tout graphe non orienté se lit comme un graphe orienté, en remplaçant chaque arête $\{u, v\}$ par les deux arcs $(u, v)$ et $(v, u)$ ; c'est ce que font tous les programmes de la fiche, qui ne manipulent jamais que des successeurs.

Un graphe pondéré est un triplet $G = (S, A, w)$ où $(S, A)$ est un graphe et où $w : A \to \mathbb{R}$ associe à chaque arc son poids. La longueur pondérée du chemin $(x_0, x_1, \dots, x_k)$ est $\sum_{i=0}^{k-1} w(x_i, x_{i+1})$. Un graphe non pondéré se traite comme un graphe pondéré dont tous les poids valent $1$ : la longueur pondérée est alors le nombre d'arcs empruntés. L'hypothèse $w \geq 0$, inutile jusqu'au parcours en largeur, devient indispensable pour l'algorithme de Dijkstra, et elle sera rappelée à chaque énoncé qui en dépend.

L'ordre d'un graphe est son nombre de sommets $n$, sa taille son nombre d'arêtes $m$. Le degré $\deg(v)$ d'un sommet d'un graphe non orienté est son nombre de voisins ; dans un graphe orienté on distingue le degré sortant $\deg^+(v)$, nombre d'arcs d'origine $v$, et le degré entrant $\deg^-(v)$, nombre d'arcs d'extrémité $v$. Une boucle est une arête d'un sommet à lui-même ; un graphe est simple s'il n'a ni boucle ni arête répétée, ce que l'on suppose partout ici sauf mention contraire. Un graphe est dense quand $m$ est de l'ordre de $n^2$, creux quand $m$ est de l'ordre de $n$ : ces deux mots commandent le choix de la représentation. Le graphe complet $K_n$ a toutes les arêtes possibles.

Un chemin de $u$ à $v$ dans le graphe $(S, A)$ est une suite finie de sommets $(x_0, x_1, \dots, x_k)$ telle que $x_0 = u$, $x_k = v$ et, pour tout $i \in \{0, \dots, k-1\}$, $(x_i, x_{i+1}) \in A$. L'entier $k$ est sa longueur : c'est le nombre d'arcs empruntés, et non le nombre de sommets écrits, qui vaut $k + 1$. Un chemin est élémentaire lorsque $x_0, \dots, x_k$ sont deux à deux distincts. Un cycle d'un graphe non orienté est un chemin de longueur $k \geq 3$ tel que $x_0 = x_k$ et dont $x_0, \dots, x_{k-1}$ sont deux à deux distincts ; dans un graphe orienté, le même objet s'appelle un circuit et sa longueur peut valoir $1$ (une boucle) ou $2$. Rien n'interdit à un chemin quelconque de repasser par un sommet : cette liberté est exactement ce que comptent les puissances de la matrice d'adjacence.

Soient $u$ et $v$ deux sommets. On note $L(u, v) \subset \mathbb{N}$ l'ensemble des longueurs des chemins de $u$ à $v$. La distance de $u$ à $v$ est $d(u, v) = \min L(u, v)$ si $L(u, v) \neq \varnothing$, et $d(u, v) = +\infty$ sinon. Le minimum existe dès que $L(u, v)$ est non vide, comme partie non vide de $\mathbb{N}$. On a toujours $d(u, u) = 0$, l'inégalité triangulaire $d(u, w) \leq d(u, v) + d(v, w)$, et la symétrie $d(u, v) = d(v, u)$ dans un graphe non orienté seulement. Un plus court chemin de $u$ à $v$ est un chemin de longueur $d(u, v)$ ; il est automatiquement élémentaire, car supprimer la portion comprise entre deux passages par un même sommet raccourcirait le chemin.

Propriété (lemme des poignées de main) : dans un graphe non orienté simple $(S, A)$, $\sum_{v \in S} \deg(v) = 2m$. Chaque arête $\{u, v\}$ est en effet comptée exactement deux fois dans la somme, une fois dans $\deg(u)$ et une fois dans $\deg(v)$, et elle n'intervient nulle part ailleurs. Dans un graphe orienté, $\sum_{v \in S} \deg^+(v) = \sum_{v \in S} \deg^-(v) = m$, chaque arc n'étant compté qu'une fois de chaque côté. Corollaire : le nombre de sommets de degré impair est pair. Conséquence algorithmique, utilisée dans toute la fiche : énumérer une fois la liste des voisins de chaque sommet coûte $\Theta(n + m)$ opérations, et non $\Theta(nm)$ ; c'est la raison pour laquelle tous les parcours sont linéaires en la taille des données.

Dans un graphe non orienté, la relation « il existe un chemin de $u$ à $v$ » est réflexive (le chemin $(u)$, de longueur nulle), symétrique (on retourne le chemin, ce qui n'est licite que faute d'orientation) et transitive (on met les deux chemins bout à bout) : c'est une relation d'équivalence (voir le thème Relations, bloc Fondements 1). Ses classes d'équivalence sont les composantes connexes du graphe, et elles forment une partition de $S$. Le graphe est connexe lorsqu'il n'a qu'une seule composante, c'est-à-dire lorsque deux sommets quelconques sont reliés par un chemin. Dans un graphe orienté la symétrie tombe, et la notion correspondante, la forte connexité, dépasse cette fiche.

Soit $G = (S, A)$ un graphe dont les sommets sont numérotés de $0$ à $n-1$. Sa matrice d'adjacence est la matrice $M \in \mathcal{M}_n(\mathbb{R})$ définie par : pour tout couple $(i, j) \in \{0, \dots, n-1\}^2$, $M_{i,j} = 1$ si $(i, j) \in A$, et $M_{i,j} = 0$ sinon. Elle dépend de la numérotation choisie : deux numérotations différentes donnent deux matrices conjuguées par une matrice de permutation. Pour un graphe pondéré, on range plutôt $w(i,j)$ à la place du $1$, en convenant d'une valeur pour l'absence d'arc. La lettre $M$ est réservée à cette matrice dans toute la fiche, $m$ continuant de désigner le nombre d'arêtes. En Python, $M$ se code par une liste de $n$ listes de $n$ entiers, et M[i][j] est le coefficient de la ligne $i$ et de la colonne $j$.

Soit $M$ la matrice d'adjacence d'un graphe à $n$ sommets. Propriété : $M$ est symétrique si et seulement si l'ensemble des arcs l'est, c'est-à-dire si et seulement si $(u, v) \in A$ entraîne $(v, u) \in A$ ; jointe à une diagonale nulle, cette symétrie caractérise les graphes orientés qui sont la lecture d'un graphe non orienté, et c'est à ce titre que l'on dit couramment d'une matrice symétrique qu'elle est celle d'un graphe non orienté. La diagonale de $M$ est nulle si et seulement si le graphe est sans boucle ; pour tout $i$, $\sum_{j=0}^{n-1} M_{i,j} = \deg^+(i)$ et $\sum_{i=0}^{n-1} M_{i,j} = \deg^-(j)$, ces deux sommes valant $\deg(i)$ et $\deg(j)$ dans le cas non orienté. Côté coûts : la place occupée est $\Theta(n^2)$, quel que soit le nombre d'arêtes ; tester l'existence d'un arc se fait en $O(1)$ ; en revanche, énumérer les voisins d'un sommet impose de lire toute sa ligne, soit $\Theta(n)$ opérations, même si ce sommet est isolé. C'est ce dernier point, et non la place, qui disqualifie la matrice pour les parcours d'un graphe creux.

La représentation par listes d'adjacence associe à chaque sommet la liste de ses voisins. En Python, on la code par un dictionnaire dont les clés sont les sommets et dont les valeurs sont des listes : voisins[u] est la liste des voisins de u, et for v in voisins[u] les énumère en $\Theta(\deg u)$. La place occupée est $\Theta(n + m)$. Deux avantages propres à Python : toute donnée non mutable peut servir de clé, donc un sommet peut être un entier, une chaîne ou un couple de coordonnées, sans renumérotation préalable ; et le test u in voisins coûte $O(1)$ en moyenne (voir le thème Python : listes, tuples, chaînes et dictionnaires). Pour un graphe pondéré, la valeur associée est une liste de couples (voisin, poids).

Coûts comparés, pour un graphe à $n$ sommets et $m$ arêtes. Mémoire : $\Theta(n^2)$ pour la matrice, $\Theta(n + m)$ pour les listes. Tester l'existence de l'arc $(u,v)$ : $O(1)$ contre $O(\deg u)$, ou $O(1)$ en moyenne si les voisins sont rangés dans un ensemble plutôt que dans une liste. Énumérer les voisins de $u$ : $\Theta(n)$ contre $\Theta(\deg u)$. Parcourir le graphe entier : $\Theta(n^2)$ contre $\Theta(n + m)$. Ajouter une arête : $O(1)$ dans les deux cas. Règle de décision : graphe dense, ou algorithme qui interroge des arêtes au hasard, ou calcul de puissances de $M$, on prend la matrice ; graphe creux et algorithme qui parcourt, on prend les listes. Tous les parcours de cette fiche sont écrits sur des listes d'adjacence, et deviendraient $\Theta(n^2)$ sur une matrice.

Quand l'utiliser : l'énoncé donne un graphe par une liste d'arêtes, un dessin, une matrice ou une situation concrète (réseau, labyrinthe, dépendances entre tâches), et demande de le programmer.
1) Décider ce qu'est un sommet, et le dire : un entier de $0$ à $n-1$, une chaîne, un couple de coordonnées pour une grille. C'est ce choix qui fixe la représentation possible : une matrice exige des indices entiers, un dictionnaire accepte tout objet non mutable.
2) Décider orienté ou non orienté, et l'écrire dans la spécification. Pour un graphe non orienté, chaque arête donne deux entrées.
3) Écrire la spécification avant le corps de la fonction (voir le thème Python : structures de contrôle et fonctions) : ce que la fonction reçoit, ce qu'elle renvoie, ses préconditions, sa complexité.
4) Construire les listes d'adjacence en initialisant le dictionnaire avec tous les sommets, y compris les isolés, puis en ajoutant chaque arête ; ou la matrice en créant $n$ lignes distinctes par une compréhension.
5) Annoncer la complexité obtenue : $\Theta(n + m)$ pour les listes, $\Theta(n^2 + m)$ pour la matrice, dont $\Theta(n^2)$ pour la seule initialisation.
6) Vérifier sur un graphe de quatre ou cinq sommets, en relisant la sortie : un graphe non orienté doit donner des listes symétriques et une matrice symétrique.

Le graphe non orienté $G$ a pour sommets $0, 1, \dots, 6$ et pour arêtes $\{0,1\}$, $\{0,2\}$, $\{1,3\}$, $\{2,3\}$, $\{3,4\}$ et $\{5,6\}$. Écrire deux fonctions qui construisent ses listes d'adjacence et sa matrice d'adjacence, et une fonction qui passe de la seconde aux premières. Donner les complexités.
On numérote les sommets de $0$ à $n-1$, ce qui autorise les deux représentations.

def listes_adjacence(n, aretes):
    """Renvoie le dictionnaire des listes d'adjacence du graphe non orienté
    dont les sommets sont les entiers de 0 à n-1 et dont les arêtes sont les
    couples de la liste aretes. Complexité : O(n + m)."""
    voisins = {sommet: [] for sommet in range(n)}
    for (u, v) in aretes:
        voisins[u].append(v)
        voisins[v].append(u)
    return voisins


def matrice_adjacence(n, aretes):
    """Renvoie la matrice d'adjacence du graphe non orienté dont les sommets
    sont les entiers de 0 à n-1 et dont les arêtes sont les couples de la
    liste aretes. Complexité : O(n^2 + m)."""
    matrice = [[0] * n for _ in range(n)]
    for (u, v) in aretes:
        matrice[u][v] = 1
        matrice[v][u] = 1
    return matrice


def matrice_vers_listes(matrice):
    """Renvoie les listes d'adjacence du graphe donné par sa matrice
    d'adjacence. Complexité : O(n^2)."""
    n = len(matrice)
    voisins = {sommet: [] for sommet in range(n)}
    for u in range(n):
        for v in range(n):
            if matrice[u][v] == 1:
                voisins[u].append(v)
    return voisins

Complexités. La construction des listes initialise $n$ listes vides puis traite chaque arête en temps constant : $\Theta(n + m)$. La construction de la matrice crée $n^2$ cases avant de lire les arêtes : $\Theta(n^2 + m)$, et le terme $n^2$ domine dès que le graphe est creux. La conversion lit les $n^2$ coefficients : $\Theta(n^2)$, indépassable puisqu'un seul coefficient non lu peut cacher une arête.
Essai.

aretes = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (5, 6)]
print(listes_adjacence(7, aretes))
print(matrice_adjacence(7, aretes)[0])
print(matrice_vers_listes(matrice_adjacence(7, aretes)))

Sortie obtenue :

{0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2, 4], 4: [3], 5: [6], 6: [5]}
[0, 1, 1, 0, 0, 0, 0]
{0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2, 4], 4: [3], 5: [6], 6: [5]}

La relecture confirme deux choses : les listes sont symétriques, puisque $1$ figure chez $0$ et $0$ chez $1$, et la somme des degrés vaut $2 + 2 + 2 + 3 + 1 + 1 + 1 = 12 = 2 \times 6$, conformément au lemme des poignées de main.
À retenir : on initialise le dictionnaire avec tous les sommets avant de lire les arêtes, sans quoi un sommet isolé manquerait, et l'on contrôle la sortie par la symétrie et par la somme des degrés.

Ligne fautive : matrice = [[0] * n] * n.
L'opérateur * appliqué à une liste ne copie pas son contenu, il répète la même référence : les $n$ lignes obtenues sont un seul et même objet, vu $n$ fois. Modifier une case en modifie donc $n$, une par ligne. Contre-exemple exécuté, avec $n = 3$ :

matrice = [[0] * 3] * 3
matrice[0][1] = 1
print(matrice)

Sortie :

[[0, 1, 0], [0, 1, 0], [0, 1, 0]]

Une seule arête a été déclarée, et la matrice en affiche trois : toute la suite du programme est fausse, sans message d'erreur.
Version correcte : matrice = [[0] * n for _ in range(n)], qui évalue [0] * n à chaque tour et crée donc $n$ listes distinctes. Avec elle, la même affectation donne [[0, 1, 0], [0, 0, 0], [0, 0, 0]]. La ligne intérieure [0] * n, elle, est licite : elle répète l'entier $0$, qui est non mutable, donc l'alias est sans conséquence. C'est le cas général de l'alias entre listes, traité dans le thème Python : listes, tuples, chaînes et dictionnaires.

Ligne fautive : for (u, v) in aretes: voisins[u].append(v), pour un graphe non orienté.
Une arête $\{u, v\}$ se traduit par deux entrées dans les listes d'adjacence, $v$ chez $u$ et $u$ chez $v$, car les programmes ne connaissent que des successeurs. Avec la ligne fautive, sur les arêtes $\{0,1\}$, $\{0,2\}$, $\{1,3\}$, $\{2,3\}$, $\{3,4\}$, on obtient voisins[4] = [] et un parcours lancé depuis $4$ ne visite que $4$, alors que le graphe est connexe. L'erreur est silencieuse : le programme ne plante pas, il répond faux.
Version correcte : ajouter les deux entrées, voisins[u].append(v) puis voisins[v].append(u). Contrôle de relecture : dans un graphe non orienté, la somme des longueurs des listes doit valoir $2m$, et la matrice d'adjacence doit être symétrique. Attention à ne pas dédoubler, en revanche, un graphe orienté : y ajouter l'arc inverse revient à changer le graphe, et un tri topologique ou une détection de circuit répondront alors n'importe quoi.

Ligne fautive : vus = [] puis if voisin not in vus: et vus.append(voisin).
Le test x in liste parcourt la liste : il coûte $O(\mathrm{card}(\mathrm{vus}))$, et non $O(1)$. Comme il est exécuté une fois par arc, le parcours entier passe de $\Theta(n + m)$ à $O(nm)$, ce qui est quadratique dès que le graphe est connexe. Le même test dans un ensemble ou parmi les clés d'un dictionnaire coûte $O(1)$ en moyenne (voir le thème Python : listes, tuples, chaînes et dictionnaires). Mesure exécutée sur une chaîne de $20\,000$ sommets, sur la machine de rédaction : $0{,}004$ seconde avec un ensemble, $1{,}155$ seconde avec une liste, soit un rapport de l'ordre de $300$.
Version correcte : vus = set(), if voisin not in vus:, vus.add(voisin). Quand on a besoin de l'ordre de découverte et du test d'appartenance, on garde les deux structures : la liste ordre pour le résultat, l'ensemble vus pour les tests. Le dictionnaire dist joue le même rôle dans les fonctions qui renvoient des distances : y être clé, c'est avoir été découvert.

Théorème : soit $G = (S, A)$ un graphe dont les sommets sont numérotés de $0$ à $n-1$, et soit $M$ sa matrice d'adjacence. Pour tout entier $k \in \mathbb{N}$ et tout couple $(i, j) \in \{0, \dots, n-1\}^2$, le coefficient $(M^k)_{i,j}$ est égal au nombre de chemins de longueur exactement $k$ allant de $i$ à $j$. Les chemins comptés sont quelconques : ils peuvent repasser autant de fois qu'ils veulent par un même sommet ou par une même arête. Le cas $k = 0$ donne $M^0 = I_n$, le seul chemin de longueur nulle issu de $i$ étant $(i)$ ; le cas $k = 1$ redonne la définition de $M$. L'énoncé vaut aussi bien pour un graphe orienté que pour un graphe non orienté. Rappel du prérequis hors ligne : le produit de deux matrices carrées de taille $n$ est défini par $(PQ)_{i,j} = \sum_{\ell=0}^{n-1} P_{i,\ell} Q_{\ell,j}$ (voir le thème Calcul matriciel, bloc Algèbre 2).

Quand l'utiliser : l'énoncé demande le nombre de trajets en exactement $k$ étapes, le nombre de mots de longueur $k$ acceptés par un automate, ou s'il existe un trajet en $k$ coups. Le mot déclencheur est exactement $k$, ou en $k$ étapes : dès que la question porte sur le plus court trajet, ce n'est plus cette méthode mais un parcours en largeur.
1) Numéroter les sommets de $0$ à $n-1$ et écrire la matrice d'adjacence $M$. Le seul choix à justifier est la numérotation.
2) Invoquer le théorème : le nombre cherché est $(M^k)_{i,j}$. L'écrire, sans le redémontrer, sauf si l'énoncé le demande.
3) Calculer $M^k$. À la main, on enchaîne les produits ; en machine, on programme le produit puis la puissance, ou l'on réduit le coût par exponentiation rapide (voir le thème Récursivité et diviser pour régner).
4) Lire le coefficient demandé, et seulement lui. Pour un nombre total de chemins de longueur $k$ partant de $i$, on somme la ligne $i$ ; pour un nombre total dans le graphe, on somme tous les coefficients.
5) Pour le nombre de chemins de longueur au plus $k$, sommer les puissances : le nombre cherché est le coefficient $(i,j)$ de $I_n + M + M^2 + \dots + M^k$.
6) Contrôler sur un petit cas : les coefficients de $M^2$ diagonaux valent $\deg(i)$ dans un graphe non orienté, puisqu'un chemin de longueur $2$ de $i$ à $i$ est un aller-retour vers un voisin.
Coût : $\Theta(k n^3)$ par produits successifs, $\Theta(n^3 \log k)$ par exponentiation rapide, contre $\Theta(n + m)$ pour un simple parcours ; on ne sort donc cette méthode que si la question porte bien sur un dénombrement.

Soit $M$ la matrice d'adjacence d'un graphe dont les sommets sont numérotés de $0$ à $n-1$. Démontrer que pour tout $k \in \mathbb{N}$ et tout couple $(i,j)$, le coefficient $(M^k)_{i,j}$ est le nombre de chemins de longueur $k$ de $i$ à $j$.
Pour deux sommets $i$ et $j$ et un entier $k$, notons $C_k(i,j)$ l'ensemble des chemins de longueur $k$ de $i$ à $j$ : c'est un ensemble fini, puisqu'un tel chemin est une suite de $k+1$ sommets pris dans un ensemble fini.
Pour $k \in \mathbb{N}$, considérons la propriété $P_k$ : « pour tout couple $(i,j)$, $(M^k)_{i,j} = \mathrm{card}\, C_k(i,j)$ ».
Initialisation. On a $M^0 = I_n$. Un chemin de longueur $0$ de $i$ à $j$ est une suite $(x_0)$ vérifiant $x_0 = i$ et $x_0 = j$ : il en existe exactement un si $i = j$, et aucun sinon. Ainsi $\mathrm{card}\, C_0(i,j)$ vaut $1$ si $i = j$ et $0$ sinon, c'est-à-dire $(I_n)_{i,j}$. Donc $P_0$ est vraie.
Hérédité. Soit $k \in \mathbb{N}$ tel que $P_k$ soit vraie. Fixons un couple $(i,j)$.
Soit $(x_0, \dots, x_k, x_{k+1}) \in C_{k+1}(i,j)$. Son avant-dernier sommet $x_k$ vérifie $(x_k, j) \in A$, et son préfixe $(x_0, \dots, x_k)$ appartient à $C_k(i, x_k)$.
Réciproquement, si $\ell$ est un sommet tel que $(\ell, j) \in A$ et si $(x_0, \dots, x_k) \in C_k(i, \ell)$, alors $(x_0, \dots, x_k, j)$ appartient à $C_{k+1}(i,j)$.
Ces deux constructions sont réciproques l'une de l'autre, et l'avant-dernier sommet d'un chemin est déterminé par ce chemin : l'ensemble $C_{k+1}(i,j)$ est donc en bijection avec la réunion, disjointe, des $C_k(i,\ell)$ pour $\ell$ décrivant l'ensemble des sommets tels que $(\ell, j) \in A$.
En passant aux cardinaux, et en observant que le facteur $M_{\ell, j}$ vaut $1$ précisément quand $(\ell, j) \in A$ et $0$ sinon, ce qui permet d'étendre la somme à tous les sommets :
$\mathrm{card}\, C_{k+1}(i,j) = \sum_{\ell=0}^{n-1} \mathrm{card}\, C_k(i,\ell) \times M_{\ell,j}$.
Or $P_k$ donne $\mathrm{card}\, C_k(i,\ell) = (M^k)_{i,\ell}$ pour tout $\ell$, donc
$\mathrm{card}\, C_{k+1}(i,j) = \sum_{\ell=0}^{n-1} (M^k)_{i,\ell} \, M_{\ell,j} = (M^k M)_{i,j} = (M^{k+1})_{i,j}$,
la deuxième égalité étant la définition du produit matriciel. Donc $P_{k+1}$ est vraie.
Conclusion. Par le principe de récurrence (voir le thème Récurrence simple, bloc Fondamental), $P_k$ est vraie pour tout $k \in \mathbb{N}$ : pour tous $i$, $j$ et $k$, le coefficient $(M^k)_{i,j}$ est le nombre de chemins de longueur $k$ de $i$ à $j$.
À retenir : la récurrence porte sur la longueur, l'hérédité découpe un chemin en son préfixe et sa dernière arête, et c'est la définition du produit matriciel, écrite en toutes lettres, qui referme le calcul.

Écrire une fonction qui, à partir de la matrice d'adjacence d'un graphe, de deux sommets et d'un entier $k$, renvoie le nombre de chemins de longueur $k$ entre ces deux sommets. L'appliquer au graphe $G$ de la fiche, pour $k = 2$ et $k = 3$.
On programme le produit matriciel, puis la puissance par produits successifs, puis la lecture du coefficient.

def produit(a, b):
    """Renvoie le produit des deux matrices carrées a et b de même taille.
    Complexité : O(n^3)."""
    n = len(a)
    c = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                c[i][j] += a[i][k] * b[k][j]
    return c


def puissance(a, k):
    """Renvoie la puissance k-ième de la matrice carrée a, pour k >= 0.
    Complexité : O(k n^3)."""
    n = len(a)
    resultat = [[1 if i == j else 0 for j in range(n)] for i in range(n)]
    for _ in range(k):
        resultat = produit(resultat, a)
    return resultat


def nombre_chemins(matrice, k, depart, arrivee):
    """Renvoie le nombre de chemins de longueur exactement k du sommet depart
    au sommet arrivee, dans le graphe de matrice d'adjacence matrice.
    Complexité : O(k n^3)."""
    return puissance(matrice, k)[depart][arrivee]

Essai sur le graphe $G$ de la fiche, d'arêtes $\{0,1\}$, $\{0,2\}$, $\{1,3\}$, $\{2,3\}$, $\{3,4\}$ et $\{5,6\}$, dont on récrit ici la matrice d'adjacence pour que le programme tourne seul :

aretes = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (5, 6)]
M = [[0] * 7 for _ in range(7)]
for (u, v) in aretes:
    M[u][v] = 1
    M[v][u] = 1

print(puissance(M, 2)[0])
print(puissance(M, 3)[0])
print(nombre_chemins(M, 3, 0, 4))

Sortie obtenue :

[2, 0, 0, 2, 0, 0, 0]
[0, 4, 4, 0, 2, 0, 0]
2

Lecture. Le coefficient $(M^2)_{0,3} = 2$ compte les deux chemins $(0,1,3)$ et $(0,2,3)$. Le coefficient $(M^2)_{0,0} = 2$ compte $(0,1,0)$ et $(0,2,0)$ : ce sont bien des chemins de longueur $2$, et c'est le degré de $0$, conformément au contrôle de la méthode. Le coefficient $(M^3)_{0,4} = 2$ compte $(0,1,3,4)$ et $(0,2,3,4)$. Enfin, les coefficients $(M^3)_{0,0}$ et $(M^3)_{0,3}$ sont nuls : dans ce graphe, tout chemin issu de $0$ et de longueur impaire aboutit à $1$, $2$ ou $4$, ce qui traduit le fait que le graphe est biparti.
À retenir : on lit la sortie ligne par ligne en retrouvant les chemins à la main sur le dessin, et un coefficient nul est une information autant qu'un coefficient non nul.

Phrase fautive : « le coefficient $(M^k)_{i,j}$ donne le nombre de chemins de $i$ à $j$ qui ne repassent pas deux fois par le même sommet ».
Le théorème compte tous les chemins de longueur $k$, y compris ceux qui font des allers-retours. Contre-exemple chiffré, sur le graphe $G$ de la fiche : $(M^2)_{0,0} = 2$, alors qu'il n'existe aucun chemin élémentaire de longueur $2$ de $0$ à $0$ ; les deux chemins comptés sont $(0,1,0)$ et $(0,2,0)$. De même $(M^3)_{0,1} = 4$ compte $(0,1,0,1)$ et $(0,2,0,1)$, qui repassent par $0$, à côté de $(0,1,3,1)$ et $(0,2,3,1)$.
Version correcte : dire « nombre de chemins de longueur $k$ », sans autre qualificatif, et réserver le mot élémentaire aux chemins à sommets deux à deux distincts, que les puissances de $M$ ne savent pas compter. Deuxième erreur de la même famille : croire que $(M^k)_{i,j} \neq 0$ signifie $d(i,j) = k$. Cela signifie seulement qu'il existe un chemin de longueur $k$ ; la distance est le plus petit tel $k$, et elle se calcule par un parcours en largeur, en $\Theta(n+m)$, non par des produits de matrices.

Parcourir un graphe depuis un sommet $s$, c'est énumérer une fois et une seule chacun des sommets atteignables depuis $s$. Tout parcours repose sur le même squelette : une structure d'attente qui contient les sommets découverts mais pas encore traités, et un marquage qui retient les sommets déjà découverts afin de ne jamais les redécouvrir. Traiter un sommet, c'est examiner tous ses voisins et y découvrir ceux qui ne le sont pas encore. Seule la structure d'attente distingue les parcours : une file (premier entré, premier sorti) donne le parcours en largeur, une pile (dernier entré, premier sorti) le parcours en profondeur. Le marquage, lui, n'est pas facultatif : sans lui, un graphe contenant un cycle ferait tourner la boucle indéfiniment.

Le parcours en largeur d'un graphe depuis un sommet $s$ est le parcours dont la structure d'attente est une file : le prochain sommet traité est le plus anciennement découvert. Les sommets sont ainsi visités par couches : d'abord $s$, puis tous les voisins de $s$, puis tous les sommets à distance $2$, et ainsi de suite. En anglais BFS, pour *breadth-first search*. En Python, la file se code par un objet deque du module collections : file.append(v) ajoute à la queue en $O(1)$ et file.popleft() retire en tête en $O(1)$ (voir le thème Python : listes, tuples, chaînes et dictionnaires). C'est ce parcours, et lui seul, qui donne les distances en nombre d'arêtes.

Quand l'utiliser : l'énoncé demande quels sommets sont atteignables, en combien d'étapes au minimum, le plus court chemin en nombre d'arêtes, le nombre minimal de coups d'un jeu, ou le plus petit nombre de correspondances d'un réseau. Signal décisif : le plus petit nombre d'étapes, avec des étapes toutes équivalentes.
1) Écrire la spécification : ce que la fonction reçoit (les listes d'adjacence et un sommet de départ), ce qu'elle renvoie, sa complexité. On ne code rien avant.
2) Initialiser les trois objets : l'ensemble vus des sommets déjà découverts, contenant le départ, la file deque([depart]), et le résultat, liste ou dictionnaire.
3) Boucler tant que la file n'est pas vide, en défilant en tête : sommet = file.popleft().
4) Pour chaque voisin non vu : le marquer au moment où on l'enfile, jamais à sa sortie, puis l'enfiler.
5) Renvoyer le résultat. Toujours renvoyer, jamais afficher : une fonction qui print ne sert à rien à l'appelant (voir le thème Python : structures de contrôle et fonctions).
6) Contrôler sur un graphe à cinq sommets dont un isolé et un cycle : l'ordre obtenu doit commencer par le départ, puis ses voisins, et le sommet isolé ne doit pas y figurer.
Sur la copie : « On parcourt le graphe en largeur depuis $s$, en marquant chaque sommet au moment où il est enfilé. La file étant vide en fin de boucle, tous les sommets atteignables ont été traités. »

Écrire une fonction qui renvoie la liste des sommets atteignables depuis un sommet donné, dans l'ordre du parcours en largeur, puis la dérouler sur le graphe $G$ de la fiche depuis le sommet $0$.

from collections import deque


def parcours_largeur(voisins, depart):
    """Renvoie la liste des sommets atteignables depuis depart dans le graphe
    donné par ses listes d'adjacence voisins, dans l'ordre de découverte du
    parcours en largeur. Complexité : O(n + m)."""
    vus = {depart}
    file = deque([depart])
    ordre = []
    while file:
        sommet = file.popleft()
        ordre.append(sommet)
        for voisin in voisins[sommet]:
            if voisin not in vus:
                vus.add(voisin)
                file.append(voisin)
    return ordre

Essai sur le graphe $G$ d'arêtes $\{0,1\}$, $\{0,2\}$, $\{1,3\}$, $\{2,3\}$, $\{3,4\}$ et $\{5,6\}$ :

G = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2, 4], 4: [3], 5: [6], 6: [5]}
print(parcours_largeur(G, 0))

Sortie obtenue :

[0, 1, 2, 3, 4]

Les sommets $5$ et $6$ n'y figurent pas : ils forment une autre composante connexe, et un parcours ne sort jamais de la composante de son départ.
Trace. Une variante instrumentée, qui tient en plus le dictionnaire des distances, affiche la file et les distances à chaque tour :

def largeur_trace(voisins, depart):
    """Déroule le parcours en largeur sur le graphe voisins en affichant, à
    chaque tour, l'état de la file et les distances déjà connues. Le
    dictionnaire dist tient lieu de marquage : y être clé, c'est avoir été
    découvert."""
    dist = {depart: 0}
    file = deque([depart])
    print("file =", list(file), "  dist =", dist)
    while file:
        sommet = file.popleft()
        for voisin in voisins[sommet]:
            if voisin not in dist:
                dist[voisin] = dist[sommet] + 1
                file.append(voisin)
        print("on défile", sommet, ": file =", list(file), "  dist =", dist)


largeur_trace(G, 0)

Sortie obtenue :

file = [0]   dist = {0: 0}
on défile 0 : file = [1, 2]   dist = {0: 0, 1: 1, 2: 1}
on défile 1 : file = [2, 3]   dist = {0: 0, 1: 1, 2: 1, 3: 2}
on défile 2 : file = [3]   dist = {0: 0, 1: 1, 2: 1, 3: 2}
on défile 3 : file = [4]   dist = {0: 0, 1: 1, 2: 1, 3: 2, 4: 3}
on défile 4 : file = []   dist = {0: 0, 1: 1, 2: 1, 3: 2, 4: 3}

Deux faits se lisent sur cette trace, et ils seront démontrés plus bas. D'abord, les valeurs présentes dans la file sont toujours croissantes de la tête vers la queue, et deux d'entre elles diffèrent d'au plus $1$ : ici $[1, 2]$ puis $[2, 3]$ portent les valeurs $1, 1$ puis $1, 2$. Ensuite, le tour où l'on défile $2$ ne découvre rien : le sommet $3$, voisin de $2$, a déjà été découvert depuis $1$, et il garde la valeur $2$ qu'il tenait de $1$.
À retenir : on marque le voisin au moment de l'enfiler, et l'on contrôle son parcours en relisant la file tour par tour, pas seulement le résultat final.

Propriété : sur un graphe fini à $n$ sommets et $m$ arêtes, représenté par ses listes d'adjacence, le parcours en largeur termine, et son coût est $O(n + m)$ en temps et $O(n)$ en mémoire. La terminaison tient à ceci : un sommet n'est enfilé que lorsqu'il n'est pas marqué, et il est marqué au même instant, or un sommet marqué ne se démarque jamais ; chaque sommet est donc enfilé au plus une fois, et le nombre total de tours de boucle est au plus $n$. Le coût du tour qui traite le sommet $u$ est $\Theta(1 + \deg u)$, d'où un total $O\big(n + \sum_{u} \deg u\big) = O(n + 2m) = O(n + m)$ par le lemme des poignées de main. Ce coût est $\Theta(n + m)$ lorsque le graphe est connexe. Sur une matrice d'adjacence, le même parcours coûte $\Theta(n^2)$, puisque chaque tour lit une ligne entière.

Lignes fautives : sommet = file.popleft() puis vus.add(sommet), le marquage étant reporté à la sortie de la file au lieu d'être fait à l'entrée.
Un sommet peut alors être enfilé plusieurs fois, une fois par voisin qui le découvre avant qu'il ne sorte. Deux conséquences. D'abord le résultat est faux : sur le graphe $G$ de la fiche, la version fautive renvoie [0, 1, 2, 3, 3, 4, 4], soit sept visites pour cinq sommets atteignables, le sommet $3$ étant traité deux fois. Ensuite le coût explose : sur le graphe complet à $8$ sommets, le marquage à l'entrée produit $8$ enfilements, le marquage à la sortie en produit $29$, et l'écart croît avec la taille du graphe.
Version correcte : marquer au moment de l'enfilement, vus.add(voisin) immédiatement suivi de file.append(voisin), ce qui garantit qu'un sommet entre au plus une fois dans la file. Variante acceptable, dite paresseuse, indispensable pour l'algorithme de Dijkstra où une valeur meilleure peut arriver plus tard : on autorise les doublons dans la structure d'attente, mais on ajoute en tête de boucle le garde-fou if sommet in vus: continue. Ce qui n'est jamais correct, c'est de reporter le marquage sans ajouter ce garde-fou.

Ligne fautive : file = [depart] puis sommet = file.pop(0).
Retirer le premier élément d'une liste Python oblige à décaler tous les autres d'un cran : pop(0) coûte $O(\mathrm{card}(\text{file}))$, et non $O(1)$. Sur un graphe où la file devient longue, le parcours passe de $\Theta(n + m)$ à un coût quadratique. Mesure exécutée sur une étoile de $30\,001$ sommets, où la file atteint $30\,000$ éléments, sur la machine de rédaction : $0{,}005$ seconde avec une deque, $0{,}591$ seconde avec une liste, soit un rapport supérieur à $100$.
Version correcte : from collections import deque, puis file = deque([depart]) et sommet = file.popleft(), qui coûte $O(1)$. Noter que file.append(v) est licite dans les deux cas : c'est l'ajout en queue, amorti en $O(1)$ sur une liste. Erreur symétrique : utiliser file.pop() au lieu de file.popleft(), ce qui retire en queue et transforme sans prévenir la file en pile, donc le parcours en largeur en parcours en profondeur, dont les distances ne sont plus les bonnes.

Quand l'utiliser : l'énoncé ne demande pas seulement le nombre minimal d'étapes, mais le trajet lui-même : « donner un plus court chemin », « afficher la suite des coups », « reconstituer l'itinéraire ».
1) Remplacer l'ensemble vus par un dictionnaire dist : être clé de dist, c'est être découvert, et il n'y a donc aucune structure supplémentaire à tenir.
2) Tenir en parallèle un dictionnaire pere, avec pere[depart] = None, et écrire pere[voisin] = sommet au même endroit que l'affectation de la distance. Ces deux lignes vont toujours ensemble.
3) Renvoyer le couple (dist, pere). Une fonction peut renvoyer plusieurs valeurs sous forme de tuple, ce qui évite toute variable globale.
4) Reconstruire le chemin dans une fonction séparée, en remontant depuis l'arrivée jusqu'à ce que le père soit None, puis en retournant la liste obtenue avec route.reverse(). Ne jamais reconstruire à l'endroit : les pères ne se remontent que de l'arrivée vers le départ.
5) Traiter le cas d'un sommet non atteignable : il n'est pas clé de dist, et le test if arrivee not in dist doit précéder tout appel à la reconstruction.
6) Contrôler le résultat : la longueur de la liste renvoyée doit valoir $\mathrm{dist}[\text{arrivee}] + 1$, elle doit commencer au départ, finir à l'arrivée, et deux sommets consécutifs doivent être voisins. Ces quatre vérifications se programment et font un excellent jeu de tests.

Écrire une fonction qui renvoie les distances au départ et les pères, puis une fonction qui reconstruit un plus court chemin jusqu'à un sommet donné. Les appliquer au graphe $G$ de la fiche, depuis $0$ et vers $4$.

from collections import deque


def distances_largeur(voisins, depart):
    """Renvoie le couple (dist, pere) : dist[v] est le nombre minimal d'arêtes
    d'un chemin de depart à v et pere[v] le sommet qui précède v sur un tel
    chemin, pour les sommets v atteignables depuis depart.
    Complexité : O(n + m)."""
    dist = {depart: 0}
    pere = {depart: None}
    file = deque([depart])
    while file:
        sommet = file.popleft()
        for voisin in voisins[sommet]:
            if voisin not in dist:
                dist[voisin] = dist[sommet] + 1
                pere[voisin] = sommet
                file.append(voisin)
    return dist, pere


def chemin(pere, arrivee):
    """Renvoie la liste des sommets d'un plus court chemin du départ à arrivee,
    le dictionnaire pere étant celui renvoyé par distances_largeur.
    Précondition : arrivee est une clé de pere."""
    route = []
    sommet = arrivee
    while sommet is not None:
        route.append(sommet)
        sommet = pere[sommet]
    route.reverse()
    return route

Essai sur le graphe $G$ de la fiche :

G = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2, 4], 4: [3], 5: [6], 6: [5]}
dist, pere = distances_largeur(G, 0)
print(dist)
print(pere)
print(chemin(pere, 4))

Sortie obtenue :

{0: 0, 1: 1, 2: 1, 3: 2, 4: 3}
{0: None, 1: 0, 2: 0, 3: 1, 4: 3}
[0, 1, 3, 4]

Contrôles. Le chemin renvoyé compte $4$ sommets pour une distance de $3$, ce qui est l'égalité attendue. Il part de $0$, arrive en $4$, et chacun de ses couples consécutifs, $(0,1)$, $(1,3)$ et $(3,4)$, est bien une arête du graphe. Les sommets $5$ et $6$ ne sont pas clés de $\mathrm{dist}$ : ils sont à distance infinie de $0$, et un appel à chemin(pere, 5) déclencherait une KeyError, d'où la précondition écrite dans la spécification.
On note aussi que le chemin renvoyé n'est pas le seul plus court chemin : $(0, 2, 3, 4)$ a la même longueur. Le parcours en fournit un, celui que dessine l'arbre des pères ; l'énoncé demande presque toujours un plus court chemin, et non le plus court chemin.
À retenir : les deux lignes dist[voisin] = ... et pere[voisin] = ... s'écrivent ensemble, la reconstruction remonte de l'arrivée vers le départ, et l'on contrôle le résultat par sa longueur et par ses arêtes.

Théorème : soit $G = (S, A)$ un graphe fini, orienté ou non, et soit $s \in S$. À la fin du parcours en largeur lancé depuis $s$ avec marquage à l'enfilement, les clés du dictionnaire $\mathrm{dist}$ sont exactement les sommets atteignables depuis $s$, et pour chacun d'eux $\mathrm{dist}[v] = d(s, v)$. De plus, en remontant les $\mathrm{pere}[v]$ à partir de $v$, on obtient un plus court chemin de $s$ à $v$. Aucune hypothèse n'est faite sur le graphe : ni connexité, ni absence de cycle, ni orientation. Mais l'énoncé porte bien sur le nombre d'arêtes : dès que les arêtes portent des poids qui ne sont pas tous égaux, il tombe, et c'est l'algorithme de Dijkstra qui prend le relais. La démonstration repose sur un lemme d'apparence modeste : les valeurs présentes dans la file sont croissantes de la tête à la queue, et l'écart entre la première et la dernière est au plus $1$.

Démontrer que le parcours en largeur termine et qu'à la fin, pour tout sommet $v$ atteignable depuis $s$, on a $\mathrm{dist}[v] = d(s, v)$.
On raisonne sur la fonction distances_largeur, qui initialise $\mathrm{dist}[s] = 0$ et $\mathrm{pere}[s] = \mathrm{None}$, puis, tant que la file n'est pas vide, défile un sommet $u$ et affecte à chaque voisin $v$ non encore clé la valeur $\mathrm{dist}[v] = \mathrm{dist}[u] + 1$ avant de l'enfiler. Une clé n'est jamais retirée du dictionnaire, ni sa valeur modifiée.
Terminaison. Posons $V = 2\big(n - \mathrm{card}(\mathrm{dist})\big) + \mathrm{card}(\mathrm{file})$, où $\mathrm{card}(\mathrm{dist})$ est le nombre de clés. Comme $\mathrm{dist}$ ne contient que des sommets, $V$ est un entier naturel. Lors d'un tour qui défile un sommet et découvre $q$ voisins, avec $q \geq 0$, le nombre de clés augmente de $q$ et la file perd un élément puis en gagne $q$ : la variation de $V$ vaut $-2q + (q - 1) = -q - 1 \leq -1$. Ainsi $V$ est un entier naturel qui décroît strictement à chaque tour : la boucle s'arrête après au plus $V_0 = 2n - 1$ tours.
Lemme (file croissante). À tout instant, si la file contient $v_1, \dots, v_p$ de la tête à la queue, alors $\mathrm{dist}[v_1] \leq \dots \leq \mathrm{dist}[v_p] \leq \mathrm{dist}[v_1] + 1$.
Démontrons-le par récurrence sur le nombre de tours effectués. Au départ la file est $(s)$ et la propriété est vraie. Supposons-la vraie au début d'un tour, la file étant $(v_1, \dots, v_p)$ avec $p \geq 1$. On défile $v_1$, puis on enfile $q$ sommets, tous de valeur $c = \mathrm{dist}[v_1] + 1$.
Si $p = 1$, la file devient $(w_1, \dots, w_q)$, suite de valeurs toutes égales à $c$ : elle est croissante et son dernier terme égale son premier, donc la propriété est vraie.
Si $p \geq 2$, la file devient $(v_2, \dots, v_p, w_1, \dots, w_q)$. La portion $(v_2, \dots, v_p)$ est croissante par hypothèse de récurrence, et les $q$ sommets enfilés portent tous la même valeur $c$. Deux cas se présentent, selon que le tour découvre ou non un voisin.
Si $q = 0$, la nouvelle file est $(v_2, \dots, v_p)$ : elle est croissante, et son dernier terme vérifie $\mathrm{dist}[v_p] \leq \mathrm{dist}[v_1] + 1 \leq \mathrm{dist}[v_2] + 1$, par hypothèse de récurrence appliquée deux fois.
Si $q \geq 1$, le raccord est croissant car $\mathrm{dist}[v_p] \leq \mathrm{dist}[v_1] + 1 = c$, toujours par hypothèse de récurrence, et le dernier terme vaut $c = \mathrm{dist}[v_1] + 1 \leq \mathrm{dist}[v_2] + 1$, puisque $\mathrm{dist}[v_1] \leq \mathrm{dist}[v_2]$.
Dans les deux cas, l'écart entre le dernier et le premier terme de la nouvelle file est au plus $1$. Le lemme est établi.
Conséquence. Les sommets sont défilés par valeurs croissantes au sens large : le sommet défilé au tour suivant est $v_2$, de valeur au moins $\mathrm{dist}[v_1]$, ou l'un des $w_i$, de valeur $\mathrm{dist}[v_1] + 1$.
Première inégalité. Pour toute clé $v$, il existe un chemin de $s$ à $v$ de longueur $\mathrm{dist}[v]$ ; en particulier $d(s, v) \leq \mathrm{dist}[v]$. On le démontre par récurrence sur l'ordre chronologique des affectations. La première est $\mathrm{dist}[s] = 0$, et $(s)$ est un chemin de longueur $0$. Pour une affectation ultérieure, $\mathrm{dist}[v] = \mathrm{dist}[u] + 1$ où $u$ est le sommet défilé, dont la valeur a été affectée plus tôt : par hypothèse de récurrence il existe un chemin de $s$ à $u$ de longueur $\mathrm{dist}[u]$, et $(u, v) \in A$ puisque $v$ est voisin de $u$ ; en lui ajoutant $v$, on obtient un chemin de $s$ à $v$ de longueur $\mathrm{dist}[u] + 1 = \mathrm{dist}[v]$.
Seconde inégalité. Montrons par récurrence forte sur $k \in \mathbb{N}$ la propriété $Q_k$ : « tout sommet $v$ tel que $d(s, v) = k$ est clé de $\mathrm{dist}$, avec $\mathrm{dist}[v] = k$ ».
Initialisation. Un sommet à distance $0$ de $s$ est $s$ lui-même, et $\mathrm{dist}[s] = 0$ dès l'initialisation : $Q_0$ est vraie.
Hérédité. Soit $k \in \mathbb{N}$ tel que $Q_0, \dots, Q_k$ soient vraies, et soit $v$ tel que $d(s, v) = k + 1$. Fixons un plus court chemin $(x_0, \dots, x_{k+1})$ de $s$ à $v$ et posons $u = x_k$. Le préfixe $(x_0, \dots, x_k)$ est un chemin de $s$ à $u$ de longueur $k$, donc $d(s, u) \leq k$ ; et si l'on avait $d(s, u) < k$, en ajoutant l'arc $(u, v)$ à un plus court chemin de $s$ à $u$ on obtiendrait un chemin de $s$ à $v$ de longueur strictement inférieure à $k + 1$, ce qui contredit $d(s, v) = k + 1$. Donc $d(s, u) = k$, et $Q_k$ donne que $u$ est clé avec $\mathrm{dist}[u] = k$.
Tout sommet qui devient clé est enfilé au même instant, et la boucle ne s'arrête que la file vide : puisque l'algorithme termine, $u$ est défilé à un certain tour. Lors de ce tour, son voisin $v$ est examiné. Ou bien $v$ n'est pas encore clé, et il le devient avec $\mathrm{dist}[v] = \mathrm{dist}[u] + 1 = k + 1$. Ou bien $v$ est déjà clé, et sa valeur lui a été affectée lors du traitement d'un sommet $w$ défilé avant $u$, ou égal à $u$ ; les défilements se faisant par valeurs croissantes, $\mathrm{dist}[w] \leq \mathrm{dist}[u] = k$, donc $\mathrm{dist}[v] = \mathrm{dist}[w] + 1 \leq k + 1$. Or la première inégalité donne $k + 1 = d(s, v) \leq \mathrm{dist}[v]$. Les deux encadrements donnent $\mathrm{dist}[v] = k + 1$. Dans les deux cas $Q_{k+1}$ est établie.
Conclusion. La première inégalité montre que toute clé est atteignable ; la récurrence montre que tout sommet atteignable est clé, avec $\mathrm{dist}[v] = d(s, v)$. Les clés sont donc exactement les sommets atteignables, et chacun porte sa distance au départ.
Chemin reconstruit. Pour toute clé $v$ distincte de $s$, $\mathrm{pere}[v]$ est un sommet $u$ tel que $(u, v) \in A$ et $\mathrm{dist}[u] = \mathrm{dist}[v] - 1$. En remontant les pères depuis $v$, on obtient une suite de sommets dont les valeurs de $\mathrm{dist}$ décroissent strictement d'une unité : elle est finie et se termine en $s$, seul sommet de valeur $0$ et seul à avoir $\mathrm{None}$ pour père. Retournée, elle forme un chemin de $s$ à $v$ de longueur $\mathrm{dist}[v] = d(s, v)$, donc un plus court chemin.
À retenir : un variant entier positif strictement décroissant pour la terminaison, un lemme sur l'état de la file pour l'ordre des traitements, puis deux inégalités qui se referment, chacune par une récurrence dont on dit sur quoi elle porte.