L'assertion qui sauve — poids négatifs

Soit le graphe $\{s\stackrel{2}{\to }a,s\stackrel{3}{\to }b,b\stackrel{-2}{\to }a\}$.

• Dijkstra commence par figer $a$ à la distance 2 (puisque $2<3$).
• La distance de $a$ est gelée. Ensuite, $b$ est figé à la distance 3, et l'arc $b\stackrel{-2}{\to }a$ est relâché. Cependant, $a$ étant déjà figé, sa distance n'est plus modifiée.
• L'algorithme renvoie $\text{dist}[a]=2$, alors que la distance réelle minimale est de $3-2=1$ (via $s\to b\to a$). Pour éviter cette erreur silencieuse, on place une assertion en entrée de fonction :

def dijkstra_secu(R: dict, source):
    assert all(R[u][v] >= 0 for u in R for v in R[u]), "Poids négatifs interdits !"
    return dijkstra(R, source)