Math
La route la moins chère
Un terrain où un pas coûte le prix de la case où l'on entre, et la vague de sommets fermés s'étend par PRIX et non par distance. Un curseur pose une arête négative sur la carte et possède trois régimes mesurés.
Ce qui se passe
Ici un pas coûte le prix de la case où l'on entre, donc la vague de sommets fermés ne s'étend pas en cercles : elle court loin dans un creux bon marché et bute sur une crête chère. Cette image est toute la différence entre un parcours en largeur et celui-ci. Tant que les poids sont positifs ou nuls, la réponse est prouvée minimale, et elle est vérifiée ici contre Bellman-Ford relaxé jusqu'au point fixe - jamais contre une seconde exécution du même algorithme - et sur les petites grilles contre l'énumération complète des chemins simples. Sur terrain plat le coût a une forme close, w(i + j), car toute route monotone coûte pareil. Les compteurs sont aussi des identités : chaque sommet est fermé exactement une fois et chaque arête relaxée exactement une fois, 4m(m−1) d'entre elles. Puis le curseur pose une unique arête dirigée négative, et elle a trois régimes, tous mesurés et non décrits. Jusqu'à −15 rien ne casse : une arête négative seule n'est pas un problème. De −16 à −50, Dijkstra répond 93 là où la vérité est 92, puis 78, puis 58 - toujours TROP GRAND, car un sommet fermé n'est jamais rouvert - et la vraie route apparaît à côté de la jaune, pour que l'erreur se voie au lieu d'être affirmée. À −51 un cycle négatif apparaît : il n'y a plus de plus court chemin du tout, Bellman-Ford le dit, et Dijkstra imprime les mêmes 93 sans broncher.
Équations du module
Équations terrain sur une grille m x m, chaque cellule ayant un prix 1..9, un pas coûte le prix de la cellule où l'on entre ; départ en haut à gauche, but en bas à droite avec des poids positifs ou nuls Dijkstra a raison - vérifié par rapport à Bellman-Ford relaxé jusqu'à un point fixe, et sur 3x3 et 4x4 par rapport à une énumération COMPLÈTE des chemins simples un terrain plat a une forme close : coût jusqu'à (i, j) = w(i + j), donc le but coûte w·2(m−1) - 120 pour w = 5, m = 13 sommets fixés = m² (chacun fermé exactement une fois) ; relaxations = arêtes = 4m(m−1) = 624 pour m = 13 ; insertions dans le tas 169 sur le terrain par défaut 13x13 par défaut, remise désactivée : chemin le moins cher jusqu'au but 93, les mêmes 93 pour Bellman-Ford, 25 cellules dans le chemin, 0 cellule où les deux divergent une arête orientée de remise de (0,7) à (5,0), et le curseur a TROIS régimes, tous mesurés : jusqu'à −15 : aucune erreur - une arête négative n'est pas à elle seule un problème de −16 à −50 : Dijkstra renvoie 93 alors que la vérité est 92, 78, 58 - toujours TROP GRAND, et les réponses divergent sur 65, 122, 159 des 169 cellules −51 et au-dessous : un cycle négatif - il n'y a pas de plus court chemin, Bellman-Ford le dit, et Dijkstra affiche toujours 93 les extrémités de l'arête de remise ont été choisies en énumérant toutes les paires : la fenêtre exige d(loin) − d(proche) < k < cost(proche à loin), et elle est vide lorsque le chemin bon marché vers la cellule éloignée passe par la proche
