L’algorithme que les élèves viennent de découvrir dans ce module est un algorithme de recherche du plus court chemin. Le nom technique de cet algorithme est Breadth-First Search algorithm ou simplement BFS algorithm. En français, on parle aussi d’algorithme de parcours en largeur. Inventé en 1945, il permet de parcourir un graphe en commençant par explorer un nœud source, puis ses successeurs, puis les successeurs non explorés des successeurs, etc. L’algorithme de parcours en largeur sert à calculer les distances de tous les nœuds depuis un nœud source dans un graphe. Le mode de fonctionnement du BFS utilise une file dans laquelle il prend le premier sommet et place en dernier ses voisins non encore explorés. Les nœuds déjà visités sont marqués afin d’éviter qu’un même nœud ne soit exploré plusieurs fois. Cet algorithme fonctionne seulement sur les graphes non pondérés, c.-à-d. les graphes dans lesquels les nœuds sont connectés par des arêtes, toutes égales non pondérées. C’est bel et bien le cas des graphes de ce module : deux nœuds (ici des configurations) sont reliés par une arête si l’on peut passer d’une configuration à l’autre par un seul mouvement de manivelle. Par contre, le BFS fonctionne pour les graphes orientés et non orientés. Un graphe orienté est un graphe dans lequel les arêtes entre deux nœuds sont orientées, c.-à-d. qu’elles vont d’un nœud vers un autre (Diestel, 2018), ou ont un sens de parcours. Comme le jeu Involution© est symétrique (si l’on peut passer d’une configuration A à une configuration B avec un seul mouvement, on peut passer de B à A avec le mouvement inverse, qui est en effet exactement le même mouvement), les graphes explorés dans ce module sont non orientés. Le département d’informatique de l’Université de Cornell a publié une introduction à l’algorithme BFS via des vidéos qui durent en tout 15 minutes (Gries, n.d.).

Parfois les graphes peuvent aussi être pondérés. Le graphe du réseau routier que nous avons vu dans ce module est un graphe pondéré : la distance entre deux carrefours varie d’une situation à une autre. Le graphe doit donc en tenir compte en attribuant un poids aux arêtes. Le plus court chemin n’est donc plus forcément le chemin qui parcourt le moins de nœuds possible et le BFS ne fonctionne donc pas sur les graphes pondérés. L’algorithme de Dijkstra est un algorithme connu qui donne le plus court chemin pour les graphes pondérés et non pondérés, qu’ils soient orientés ou non orientés. Il porte le nom de son inventeur, Edsger Dijkstra, et a été publié pour la première fois en 1959 (Dijkstra, 1959). Le mode de fonctionnement de l’algorithme de Dijkstra est le suivant : l’algorithme commence à un nœud de départ et calcule les distances entre ce nœud et tous les autres nœuds du graphe. Il choisit ensuite le nœud le plus proche du nœud de départ. Ce nœud est ajouté avec le nœud de départ dans une file, puis toutes les distances sont réévaluées : si la distance entre le nœud de départ et un autre nœud est plus courte en passant par le nouveau nœud, elle est remplacée par la distance la plus courte. L’algorithme continue ainsi jusqu’à ce qu’il ait parcouru tous les nœuds, ce qui permet d’établir les distances minimales entre le nœud de départ et tous les autres nœuds. Le département d’informatique de l’Université de Cornell a aussi publié une introduction à l’algorithme de Dijkstra (Gries, n.d.).

À plusieurs reprises, le mathématicien J. H. C. Whitehead a déclaré que « la combinatoire est le bidonville de la topologie » (Cameron, 2011). La combinatoire est une discipline mathématique dont fait partie la théorie des graphes. Au début du XX^e siècle, cette vision de la théorie des graphes est répandue parmi beaucoup d’autres mathématiciens, mais elle a fortement, voire complètement, changé aujourd’hui. La théorie des graphes est un outil important pour étudier les liens dans les systèmes complexes. Dès qu’un système peut être représenté schématiquement sous forme de nœuds et d’arêtes, la théorie des graphes s’applique. Ces systèmes peuvent être très divers : réseaux routiers, réseaux urbains des données informatiques… Les applications dans le monde numérique d’aujourd’hui sont énormes. Voici quelques exemples très importants (Flovik, 2020) :

• La propagation du virus COVID 19 dans les communautés
• Le classement des pages web dans les moteurs de recherche (comme Google)
• La sécurité du réseau
• Les navigateurs GPS
• etc

Revenons par exemple aux navigateurs GPS (comme Google maps, Waze, etc.), qui interviennent aussi dans ce module. Les systèmes de navigation GPS font partie des applications de la théorie des graphes qui ont un impact direct sur notre vie quotidienne : nous nous fions bien souvent à ces systèmes pour rejoindre un lieu en empruntant le chemin le plus court (ou le plus rapide). Un réseau routier peut être représenté par un graphe dont les nœuds sont les carrefours et les immeubles, et dont les arêtes sont les portions de route qui les relient. Comme certaines routes sont en sens unique, le graphe est orienté (contrairement au graphe d’Involution©, qui est non orienté). Le système de navigation calcule un chemin optimal entre deux points du réseau, en fonction de critères définis par l’utilisateur (il optimise soit la longueur du trajet, soit le temps de parcours ou favorise les autoroutes, etc.). Pour fixer les idées, imaginons que le système cherche à minimiser la longueur des trajets. Pour modéliser le problème, nous devons ajouter de l’information au graphe orienté qui modélise le réseau routier. On associe en effet à chaque portion de route un poids qui représente exactement la longueur de cette portion. Les navigateurs utilisent donc des graphes orientés et pondérés. L’algorithme de recherche du plus court chemin que les navigateurs utilisent est basé sur l’algorithme de Dijkstra (Teheux, 2019).

Il est intéressant de noter que les systèmes de navigation GPS implémentent l’algorithme de Dijkstra à l’envers. Plus précisément, si le but de l’utilisateur est de se rendre du nœud A au nœud B, le système de navigation applique l’algorithme de Dijkstra au graphe obtenu en retournant les arêtes du graphe du réseau routier avec le nœud B comme nœud source. Le résultat est alors le chemin le plus court de B vers A. Mais il suffit de retourner ce chemin pour obtenir le chemin souhaité. L’idée qui sous-tend cette inversion est une économie de calculs. Il n’est pas rare que nous, en tant que conducteurs, quittions l‘itinéraire recommandé par le navigateur (nous nous trompons, une route est fermée à la circulation, nous changeons de plan à la dernière minute, etc.). Si l’algorithme avait effectué la recherche du plus court chemin dans le bon sens, il devrait recommencer (car nous nous trouvons à un endroit qui n’était pas prévu dans les calculs de l’algorithme) et tous les calculs faits avant auraient été perdus. Par contre, en commençant par la fin, l’algorithme a déjà calculé le plus court chemin de n’importe quel point (dans un rayon raisonnable) au point final. En conséquence, même en changeant d’itinéraire, l’algorithme est capable de nous proposer rapidement une alternative (Teheux, 2019).

Bien que la théorie des graphes pure soit une discipline abstraite et mathématique, ceci montre qu’elle a beaucoup d’applications concrètes et intéressantes en informatique. De toute façon, comme le confirme l’informaticien mondialement reconnu Leslie Lamport : « Si vous voulez vraiment faire les choses correctement, vous devez écrire votre algorithme en termes mathématiques. » (Han, 2022).

Références

Cameron, Peter J. (2011). Aftermath. Preprint. https://arxiv.org/pdf/1111.4050.pdf
Diestel, Reinhard. (2018). Graph theory (5th Ed.). Graduate Texts in Mathematics, 173. Berlin : Springer.
Dijkstra, Edsger W. (1959). A note on two problems in connexion with graphs. Numer. Math., 1, 269 – 271. https://doi.org/10.1007/BF01386390 
Flovik, Vegard. (2020). What is Graph Theory, and why should you care. From graph theory to path optimization. Towards Data Science. https://towardsdatascience.com/what-is-graph-theory-and-why-should-you-care-28d6a715a5c2
Gries, David. (n.d.). Depth-first search and breadth-first search. https://www.cs.cornell.edu/courses/JavaAndDS/dfs/dfs01.html
Gries, David. (n.d.). The shortest-path algorithm. https://www.cs.cornell.edu/courses/JavaAndDS/shortestPath/shortestPath.html
Han, Sheon. (2022). How to Write Software With Mathematical Perfection. Quantamagazine. https://www.quantamagazine.org/computing-expert-says-programmers-need-more-math-20220517
Teheux, Bruno. (2019). À la recherche des chemins les plus courts. Losange, N 46, 45-54.