Mission : corriger le moteur d'itinéraire qui donne parfois un résultat faux

Contexte

Un moteur de calcul d'itinéraire utilise Dijkstra pour trouver le trajet le moins cher entre deux entrepôts, où le "poids" d'une arête représente un coût de transport. Une nouvelle fonctionnalité de remise promotionnelle a introduit des coûts négatifs sur certaines routes (des bonus de trajet), et le moteur s'est mis à retourner, dans de rares cas, un chemin plus cher que le vrai optimum, sans jamais planter.