Skip to content

Recherche du chemin le plus court : l'algorithme de Dijkstra

Le contexte

Un des problèmes classique en informatique est de trouver le plus court chemin reliant deux éléments d'un même réseau, que ce soit deux villes dans un réseau routier ou deux routeurs d'un réseau informatique.

Représenter une carte routière, notion de graphe

On considère l'extrait de carte de la région Auvergne-Rhône-Alpes donné ci-dessous :

Carte_Auvergne.png

Un technicien d'une entreprise doit se déplacer et pouvoir intervenir sur les différents sites de cette entreprises, situés dans les villes suivantes : Aurillac (A), Bourg-en-Bresse (B), Clermont-Ferrand (C), Saint-Etienne (E), Grenoble(G), Lyon (L), Le Puy-en-Velay(P), Valence(V). Il connait les distances suivantes par autoroute, en km :

  • AC = 160
  • AP = 180
  • CP = 130
  • CE = 140
  • CL = 180
  • PE = 80
  • PV = 100
  • EL = 70
  • EV = 100
  • LV = 100
  • LB = 80
  • LG = 110
  • BG = 180
  • VG = 90

Exercice

Donner une représentation graphique simplifiée de la situation présentée ci-dessus.

Notion de graphe (non orienté)

  • Un tel type de représentation s'appelle un graphe non orienté (undirected graph) - car les segments peuvent être parcourus dans les deux sens.
  • Les points A, B, C, etc sont appelés sommets (nodes) du graphe.
  • Les segments reliant deux sommets sont appelés arêtes (edges).
  • Les valeurs sur les arêtes sont appelées poids (weights).
  • Deux sommets sont dits voisins si il existe une arête entre ces deux sommets.
  • Une chaîne (ou un chemin, path en anglais) est une suite finie d'arêtes consécutive, et le poids d'une chaîne est la somme des poids de ses arêtes.

La théorie des graphes est une branche particulière des mathématiques ayant une importance capitale dans le développement de l'informatique, et de nombreux algorithmes classiques liés à la théorie des graphes sont systématiquement étudiés par les élèves des différentes écoles et universités faisant de l'informatique. De nombreux problèmes sont résolubles grâce à une implantation sous la forme de graphe, dont certains problèmes historiques comme :

  • Le problème des ponts de Königsberg : est il possible de visiter à pied la ville de Königsberg en passant une et une seule fois par chacun des ponts ?

    Koenigsberg.png

  • Le problème de la coloration de graphe : On veut colorier une carte géographique tracée sur le plan (ou la sphère) de manière que deux régions voisines soient toujours de couleurs différentes. Combien de couleurs sont nécessaires au minimum ?

    france-region.jpg

L'algorithme de Dijkstra

Edsger Dijkstra

Edsger Wybe Dijkstra (mathématicien et informaticien néerlandais 1930 − 2002) a proposé en 1959 un algorithme qui permet de calculer le plus court chemin entre un sommet particulier et tous les autres. C'est l'un des plus efficaces pour traiter les problèmes de plus court chemin. Grâce à la puissance du traitement informatique, il est utilisé par les logiciels d'optimisation de trajets réels (Navigateurs GPS, Site RATP. . .) ou virtuels (routage internet). Cet algorithme ne fonctionne que si le graphe ne possède que des valeurs positives.

Dijkstra.jpg

Description de l'algorithme

Algorithme de Dijkstra

Si le plus court chemin reliant le sommet \(E\) (entrée) au sommet \(S\) (sortie) passe par les sommets \(s_1 , s_2 , . . . , s_k\) alors, les différentes étapes sont aussi les plus courts chemins reliant \(E\) aux sommets successifs \(s_1 , s_2 , . . . , s_k\) . Nous devons dons construire de proche en proche le chemin cherché en choisissant à chaque itération de l'algorithme, un sommet \(s_i\) du graphe parmi ceux qui n'ont pas encore été traités, tel que la longueur connue provisoirement du plus court chemin allant de \(E\) à \(s_i\) soit la plus courte possible. L'algogramme correspondant est donné ci-dessous :

AlgogrammeDijkstra.png

Exemple complet débranché

Table de Dijkstra

Pour faciliter la recherche du plus court chemin il est commode de présenter les résultats dans un tableau.

Exercice

  1. Ayant terminé sa semaine de travail à Bourg-en-Bresse, le technicien souhaite retourner chez lui à Aurillac en faisant le moins de kilomètres possibles. Déterminer, en utilisant l'algorithme de Dijkstra, le plus court chemin entre les villes de Bourg-en-Bresse et Aurillac en empruntant le réseau routier, en s'aidant du tableau ci-dessous :

    TableDijkstra.png

    Quelle est alors la route à emprunter ?

  2. La route entre Le Puy-en-Velay et Aurillac est fermée à la circulation. Quel chemin doit-il alors emprunter?

D'autres utilisations

Alexis part en voyage dans l’Est des Etats-Unis. Il souhaite visiter les villes suivantes : Atlanta (A), Boston (B), Chicago (C), Miami (M), New York (N)et Washington (W).Une compagnie aérienne propose les liaisons suivantes représentées par le graphe ci-dessous :

GrapheAeroports.png

  1. Alexis veut relier Boston à Miami.Déterminer le trajet le moins cher ainsi que le coût de ce trajet.
  2. Le site https://graphonline.ru/fr/ permet de tracer un graphe et de déterminer entre autre le chemin le plus court grâce à l'algorithme de Dijkstra. Vérifiez vos calculs précédents avec ce site.