Quelle condition sur le graphe est nécessaire pour que l'algorithme de Dijkstra trouve des plus courts chemins corrects ?

Réponse : C. Tous les poids des arêtes sont supérieurs ou égaux à 0

L'algorithme de Dijkstra fixe le sommet non encore fixé dont la distance est la plus petite. Il repose sur l'hypothèse que passer par d'autres sommets ne peut qu'allonger une distance, jamais la raccourcir. Avec une arête négative, une distance peut devenir plus courte plus tard par un autre chemin ; par exemple, dans un graphe orienté avec S→A 2, S→B 3 et B→A −2, A est fixé à 2 avant que le chemin S→B→A de longueur 1 soit trouvé. En présence de poids négatifs, on utilise l'algorithme de Bellman-Ford ou une méthode similaire. L'algorithme de Dijkstra fonctionne avec des cycles et des arêtes orientées, pourvu que tous les poids soient supérieurs ou égaux à 0.