L'assertion qui sauve — poids négatifs

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 14 — Plus courts chemins : Dijkstra et au-delà

Énoncé

Proposer un exemple de graphe comportant un poids négatif pour lequel Dijkstra renvoie un résultat erroné, et montrer l'utilité d'une assertion.

Corrigé

Soit le graphe ${s 2 a, s 3 b, b - 2 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 - 2 a$ est relâché. Cependant, $a$ étant déjà figé, sa distance n'est plus modifiée.
L'algorithme renvoie $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)

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.