Algorithme de Dijkstra
Période historique : 1956
L'algorithme glouton déterminant les plus courts chemins dans un graphe à pondérations positives.
Contenu & Formulation mathématique
Genèse & Portée historique
Conçu en vingt minutes par Edsger Dijkstra en 1956 pour faire la démonstration de la machine ARMAC, cet algorithme calcule les chemins minimaux reliant un sommet source à tous les autres. En maintenant une file de priorité des distances estimées, il visite chaque sommet de manière optimale avec une complexité en O(|E| + |V| log |V|) via un tas de Fibonacci.
Dijkstra racontait avoir conçu l'algorithme en prenant un café sur une terrasse d'Amsterdam avec sa fiancée, sans papier ni crayon, guidé par le refus absolu de toute complication superflue.
Filiations & Relations conceptuelles (2)
Objet de collection MathTCG
Algorithme de Dijkstra
Principe : L'algorithme glouton déterminant les plus courts chemins dans un graphe à pondérations positives.
Dans l'édition physique et numérique de MathTCG, cette carte appartient à l'extension Space, Chance & Computation.