Un poids négatif, et Dijkstra se trompe

G = {"A": [("B", 2), ("C", 3)],
     "B": [("D", 5)],
     "C": [("B", -2)],
     "D": []}

print(dijkstra(G, "A"))     # {'A': 0, 'B': 1, 'C': 3, 'D': 7}

La vraie réponse. Le chemin $A\to C\to B\to D$ coûte $3-2+5=6$, alors que l'algorithme annonce $7$ pour $D$.

Le moment exact de l'erreur. Après le traitement de $A$, on a $\mathrm{dist}(B)=2$ et $\mathrm{dist}(C)=3$. L'étape suivante fixe le sommet de plus petite distance provisoire, donc $B$, et relâche aussitôt son arête sortante : $\mathrm{dist}(D)=2+5=7$. Vient ensuite $C$, qui propose $3-2=1$ pour $B$. Mais $B$ est déjà sorti de l'ensemble des sommets à traiter : son arête $B\to D$ ne sera plus jamais réexaminée, et $D$ garde les $7$ calculés sur une valeur périmée.

Le piège dans le piège. Le dictionnaire rendu affiche $B$ à $1$, la bonne valeur — c'est $D$, plus loin, qui est faux. Contrôler seulement le sommet qu'atteint l'arête négative ne montrerait rien.

Ce que l'hypothèse garantissait. Avec des poids positifs, tout chemin passant par un sommet non encore fixé coûte au moins la distance provisoire de ce sommet, donc au moins celle du minimum : le fixer est sûr, sa distance ne baissera plus, et ce qu'il a propagé reste valable. Un poids négatif fait disparaître exactement ce « au moins ».

Le point à retenir. La mention « poids positifs » n'est pas une précaution de rédaction : c'est l'hypothèse sur laquelle repose la correction de l'algorithme, et il échoue sans rien signaler.