Notes

• [1]
  La paternité des algorithmes de plus courts chemins est parfois difficile à établir, du fait que plusieurs chercheurs purent avoir indépendamment des idées identiques ou proches pratiquement en même temps. Le lecteur pourra donc trouver dans la littérature d’autres attributions que les nôtres pour les algorithmes décrits plus loin.
• [2]
  E.W. Dijkstra, A note on two problems in connexion with graphs, Numerische Mathematik 1, 1959, 269-271 ; Dijkstra avait en fait conçu son algorithme dès 1956.
• [3]
  L’utilisation de structures de données plus sophistiquées permet de réduire dans certains cas la complexité de l’algorithme de Dijkstra. Par exemple, la structure de tas (voir l’annexe D, page 481, en utilisant ici un tas croissant) permet d’obtenir une complexité en O((m+n) log n), ce qui se simplifie en O(m log n) si m est au moins de l’ordre de n (ce qui est le cas si le graphe possède une racine). On peut en fait obtenir O(m + n log n) avec des structures de données appropriées (qui sortent de notre cadre ; voir par exemple T. Cormen, C. Leiserson, R. Rivest, C. Stein, Algorithmique, Dunod, 2010).
• [4]
  Voir aussi l’exercice 9 pour déterminer une numérotation topologique à l’aide de DFS.
• [5]
  Si le graphe est codé par sa matrice d’adjacence, on constate facilement que la complexité est en O(n²).
• [6]
  R. Bellman, On a routing problem, Quarterly of Applied Mathematics 16, 1958, 87-90. En fait, dans son article, Bellman introduit les relations permettant de calculer les quantités que nous appelons ici val, mais sans se limiter à des graphes sans circuit.
• [7]
  Si le graphe est codé par la matrice des valuations, on vérifie facilement que l’algorithme de Bellman est en O(n²).
• [8]
  Plus précisément, la recherche d’un plus court chemin élémentaire dans le cas général est un « problème -difficile » (voir chapitre 13 pour le sens de cette expression et le problème 8, page 460, pour la démonstration), alors que le cas des valuations positives correspond à un problème polynomial. Les deux problèmes apparaissent ainsi comme étant qualitativement différents.
• [9]
  Appelons V la plus grande valeur absolue des valuations υ(a) des arcs a de . La somme des valuations val(s) initiales est majorée par n²V et la somme des valuations optimales est minorée par −n²V. Le nombre d’itérations est donc majoré par 2n²V.
• [10]
  G.B. Dantzig, AH shortest routes in a graph, in Théorie des graphes, P. Rosenstiehl (dir.), Dunod, 1966, 91-92.