Le plus court chemin de A à B est-il toujours la ligne droite ? En général oui, mais lorsqu'il faut suivre les voies délimitées par les routes et les carrefours d'une ville, un autre point de vue s'impose. L'algorithme de Dijkstra nous est alors d'un grand secours !


Du point de vue mathématique, une carte routière peut être vue comme un graphe orienté et pondéré, c’est-à-dire un ensemble de carrefours (les sommets) reliés par des routes (les arcsa priori à sens unique et de longueurs variables. La longueur de l’arc reliant le sommet u au sommet v est notée (uv ).

 

 

Un graphe orienté pondéré.

 

Pour aller d’un sommet u à un sommet v on suit un chemin, c’est-à-dire une succession d’arcs qui nous mènent de proche en proche vers notre but. La longueur totale du chemin est simplement la somme des longueurs de chacun des arcs traversés. Par exemple, le chemin cba (l’arête cb suivie ... Lire la suite


références

À la découverte des graphes et des algorithmes de graphes. Christian Laforest, EDP Sciences, 2017.
Les algorithmes. Bibliothèque Tangente 37, 2013.
Algorithmique. Thomas Cormen, Charles Leiserson, Ronald Rivest et Clifford Stein, Dunod, 2010.
« À la découverte des graphes ». Chaîne Youtube de Christian Laforest.