Recherchez sur tout Techno-Science.net
       
Techno-Science.net : Suivez l'actualité des sciences et des technologies, découvrez, commentez
Catégories
Techniques
Sciences
Encore plus...
Techno-Science.net
Partenaires
Organismes
 CEA
 ESA
Sites Web
Photo Mystérieuse

Que représente
cette image ?
 A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | +
Algorithme de Dijkstra

L'algorithme de Dijkstra sert à résoudre le problème du plus court chemin entre deux sommets d'un graphe connexe dont le poids lié aux arêtes est positif ou nul.

Pour illustrer l'intérêt de cet algorithme, on peut prendre pour exemple le réseau (Un réseau informatique est un ensemble d'équipements reliés entre eux pour échanger des informations. Par analogie avec un filet (un réseau est un « petit rets », c'est-à-dire un...) routier d'une région : chaque sommet est une ville (Une ville est une unité urbaine (un « établissement humain » pour l'ONU) étendue et fortement peuplée (dont les habitations doivent être à moins de 200 m chacune, par opposition aux...) et chaque arc est une route (Le mot « route » dérive du latin (via) rupta, littéralement « voie brisée », c'est-à-dire creusée dans la roche, pour ouvrir le chemin.) dont le poids (Le poids est la force de pesanteur, d'origine gravitationnelle et inertielle, exercée par la Terre sur un corps massique en raison uniquement du voisinage de la Terre. Elle est égale à l'opposé de la résultante des...) est le kilométrage. L'algorithme de Dijkstra (L'algorithme de Dijkstra sert à résoudre le problème du plus court chemin entre deux sommets d'un graphe connexe dont le poids lié aux arêtes est positif ou nul.) permet alors de trouver le plus court chemin d'une ville à une autre.

L'algorithme porte le nom de son inventeur, l'informaticien (On nommait dans les années 1960-1980 informaticien ou informaticienne une personne exerçant un métier dans l'informatique. La variété et le peu de...) néerlandais Edsger Dijkstra (Edsger Wybe Dijkstra (né à Rotterdam le 11 mai 1930, mort à Nuenen le 6 août 2002) est un mathématicien et informaticien néerlandais du XXe siècle.) et a été publié en 1959[1].

Notations

Le graphe (Le mot graphe possède plusieurs significations. Il est notamment employé :) est noté G = (S,A) où :

  • l'ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut être comprise comme un...) S est l'ensemble des sommets du graphe G ;
  • l'ensemble A est l'ensemble des arêtes de G tel que : si (s1,s2) est dans A, alors il existe une arête depuis le nœud s1 vers le nœud s2 ;
  • on définit la fonction Poids(s1,s2) définie sur A qui renvoie le poids positif de l'arête reliant s1 à s2 (et un poids infini (Le mot « infini » (-e, -s ; du latin finitus, « limité »), est un adjectif servant à qualifier quelque chose qui n'a pas de limite en nombre ou en taille.) pour les paires de sommets qui ne sont pas connectées par une arête).

Principes

Le poids du chemin entre deux sommets est la somme des poids des arêtes qui le composent. Pour une paire (On dit qu'un ensemble E est une paire lorsqu'il est formé de deux éléments distincts a et b, et il s'écrit alors :) donnée (Dans les technologies de l'information (TI), une donnée est une description élémentaire, souvent codée, d'une chose, d'une transaction d'affaire, d'un événement, etc.) de sommets sdeb (le sommet du départ) sfin (sommet d'arrivée) appartenant à S, l'algorithme trouve le chemin depuis sdeb vers sfin de moindre poids (autrement dit le chemin le plus léger ou encore le plus court).

L'algorithme fonctionne en construisant un sous-graphe P de manière à ce que la distance entre un sommet s de P depuis sdeb soit connue et soit un minimum dans G. Initialement P contient simplement le nœud sdeb isolé, et la distance de sdeb à lui-même vaut zéro (Le chiffre zéro (de l’italien zero, dérivé de l’arabe sifr, d’abord transcrit zefiro en italien) est un symbole marquant une...). Des arcs sont ajoutés à P à chaque étape :

1. en identifiant toutes les arêtes ai = (si1,si2) dans G \times P tel que si1 est dans P et si2 est dans G ;
2. en choisissant l'arête aj = (sj1,sj2) dans G \times P qui donne la distance minimum depuis sdeb à sj2 en passant tous les chemins créés menant à ce nœud.

L'algorithme se termine soit quand P devient un arbre (Un arbre est une plante terrestre capable de se développer par elle-même en hauteur, en général au delà de sept mètres. Les arbres acquièrent une structure rigide composée d'un...) couvrant de G, soit quand tous les nœuds d'intérêt[2] sont dans P.

Algorithme

Fonction annexes

L'algorithme utilise les fonctions annexes suivantes.

Initialisation de l'algorithme

 
 Initialisation(G,sdeb) 
 1 pour chaque point (Graphie) s de G 
 2    faire d[s]:= infini             /* on initialise les sommets autres que sdeb à 0 */[3] 
 3       prédecesseur[s]:= 0          /* car on ne connaît au départ aucun chemin entre s et sdeb */ 
 4 d[sdeb]:= 0                        /* sdeb étant le point le plus proche de sdeb */ 
 

Recherche (La recherche scientifique désigne en premier lieu l’ensemble des actions entreprises en vue de produire et de développer les connaissances...) du nœud le plus proche

  • On recherche le nœud le plus proche (relié par l'arête de poids le plus faible) de sdeb parmi les nœuds situés dans un ensemble Q, constitué des nœuds éloigné d'une arête des éléments de P. On utilise pour cela la fonction Trouve_min(). Le nœud trouvé est alors effacé de l'ensemble Q et est alors retourné à la fonction principale comme résultat de la fonction.

Mise à jour (Une mise à jour, souvent abrégé en MAJ ou MàJ, est l'action qui consiste à mettre « à jour », ou bien « à niveau », un outil informatique, un service ou une...) des distances

  • On met à jour (Le jour ou la journée est l'intervalle qui sépare le lever du coucher du Soleil ; c'est la période entre deux nuits, pendant laquelle les rayons du Soleil éclairent le ciel. Son début (par rapport à minuit heure...) des distances entre sdeb et s2 en se posant la question : vaut-il mieux passer (Le genre Passer a été créé par le zoologiste français Mathurin Jacques Brisson (1723-1806) en 1760.) par s1 ou pas ?
 
 maj_distances(s1,s2) 
 1 si d[s2] > d[s1] + Poids(s1,s2) 
 2    alors d[s2]:= d[s1] + Poids(s1,s2) 
 3         prédecesseur[s2]:= s1          /* on fait passer le chemin par s1 */ 
 

Fonction principale

Voici la fonction principale utilisant les précédentes fonctions annexes :

 
 Dijkstra(G,Poids,sdeb) 
 1 Initialisation(G,sdeb) 
 2 P:= ensemble vide (En mathématiques, l'ensemble vide est l'ensemble ne contenant aucun élément.) 
 3 Q:= ensemble de tous les nœuds 
 4 tant que Q n'est pas un ensemble vide (Le vide est ordinairement défini comme l'absence de matière dans une zone spatiale.) 
 5       faire s1:= Trouve_min(Q) 
 6          P:= P union {s1} 
 7          pour chaque nœud  s2 voisin de s1 
 8              faire maj_distances(s1,s2) 
 

Le plus court chemin de sdeb à sfin peut ensuite se calculer itérativement selon l'algorithme suivant, avec A la suite représentant le plus court chemin de sdeb à sfin:

 
 1 A = suite vide 
 2 s:= sfin 
 3 A = s + A                   /* insère s au début de A */ 
 4 tant que s != sdeb 
 5   s = prédecesseur[s]       /* on continue de suivre le chemin */ 
 6   A = s + A 
 

Améliorations de l'algorithme

Il est possible d'améliorer légèrement l'algorithme principal en arrêtant la recherche lorsque l'égalité s1 = sfin est vérifiée, à condition bien sûr de ne chercher que la distance minimale entre sdeb et sfin.

L'algorithme de Dijkstra pourra être mis en œuvre efficacement en stockant le graphe sous forme de listes d'adjacence et en utilisant un tas comme une file à priorités pour réaliser la fonction Trouve_min. Si le graphe possède m arcs et n nœuds, en supposant que les comparaisons des poids d'arcs soient à temps (Le temps est un concept développé par l'être humain pour appréhender le changement dans le monde.) constant, alors la complexité (La complexité est une notion utilisée en philosophie, épistémologie (par exemple par Anthony Wilden ou Edgar Morin), en physique, en biologie (par exemple par...) de l'algorithme est : \sigma [(m+n)\times ln(n)]. On notera que l'utilisation de tas de Fibonacci (Leonardo Fibonacci (Pise, v. 1170 - v. 1250) est un mathématicien italien. Fibonacci (de son nom moderne), connu à l'époque sous le nom de Leonardo Pisano (Léonard de Pise), mais aussi de Leonardo Bigollo (bigollo signifiant voyageur),...) donne un meilleur temps d'exécution amorti : \sigma [m+n\times ln(n)].

Exemple

L'exemple suivant montre les étapes successives dans la résolution du chemin le plus court dans un graphe. Les nœuds symbolisent des villes en Allemagne et les arêtes indiquent la distance entre les villes. On veut aller de Francfort (Frankfurt) à Munich (München).

Étape 1
Étape 1


Étape 2
Étape 2


Étape 3
Étape 3


Étape 4
Étape 4


Étape 5
Étape 5


Étape 6
Étape 6


Étape 7
Étape 7


Étape 8
Étape 8


Étape 9
Étape 9


Codes

Pseudo-code (En programmation, le pseudo-code est une façon de décrire un algorithme sans référence à un langage de programmation en particulier.)

 
 fonction Dijkstra (nœuds, fils, distance, debut, fin) 
 Pour n parcourant nœuds 
 n.parcouru = infini   // Peut être implémenté avec -1 
 n.precedent = 0 
 Fin pour 
 debut.parcouru = 0 
 DejaVu (DejaVu est une famille de police de caractères libre basée sur Bitstream Vera, dont le but est de couvrir le plus de caractères Unicode possible tout en maintenant le niveau de qualité et le...) = liste vide 
 PasEncoreVu = nœuds 
 Tant que PasEncoreVu != liste vide 
 n1 = minimum(PasEncoreVu)   // Le nœud dans PasEncoreVu avec parcouru le plus petit 
 DejaVu.ajouter(n1) 
 PasEncoreVu.enlever(n1) 
 Pour n2 parcourant fils(n1)   // Les nœuds reliés à n1 par un arc 
 Si n2.parcouru > n1.parcouru + distance(n1, n2)   // distance correspond au poids de l'arc reliant n1 et n2 
 n2.parcouru = n1.parcouru + distance(n1, n2) 
 n2.precedent = n1   // Dis que pour aller à n2, il faut passer par n1 
 Fin si 
 Fin pour 
 Fin tant que 
 chemin = liste vide 
 n = fin 
 Tant que n != debut 
 chemin.ajouterAvant(n) 
 n = n.precedent 
 Fin tant que 
 Retourner chemin 
 Fin fonction Dijkstra 
 

Implémentation (Le mot implantation peut avoir plusieurs significations :) Caml

Voici le code d'implémentation Caml :

 
 (* on suppose données des files de priorité *) 
 module H: sig 
 type 'a t 
 val empty: 'a t 
 val is_empty: 'a t -> bool 
 val add: int * 'a -> 'a t -> 'a t 
 val extract_min: 'a t -> (int * 'a) * 'a t 
 end 
 (* l'adjacence est donnée (Dans les technologies de l'information, une donnée est une description élémentaire, souvent codée, d'une chose, d'une transaction, d'un...) sous la forme d'une fonction: adj v est la liste des voisins de v, 
 avec leur distance ; la fonction suivante cherche le plus court chemin de v1 à v2 *) 
 let dijkstra (adj: 'a -> ('a * int) list) (v1:'a) (v2:'a) = 
 let visited = Hashtbl.create 97 in 
 let rec loop h = 
 if H.is_empty h then raise Not_found; 
 let (w,(v,p)),h = H.extract_min h in 
 if v = v2 then 
 List.rev p, w 
 else 
 let h = 
 if not (Hashtbl.mem visited v) then begin 
 Hashtbl.add visited v (); 
 List.fold_left (fun h (e,d) -> H.add (w+d, (e, e::p)) h) h (adj v) 
 end else 
 h 
 in 
 loop h 
 in 
 loop (H.add (0,(v1,(lien))) H.empty) 
 

Applications

Une application des plus courantes de l'algorithme de Dijkstra est le protocole open shortest path first qui permet un routage (En informatique, le terme routage désigne le mécanisme par lequel les données d'un équipement expéditeur sont acheminées jusqu'à leur destinataire en examinant les informations situées au niveau 3 du modèle OSI (IP...) internet (Internet est le réseau informatique mondial qui rend accessibles au public des services variés comme le courrier électronique, la messagerie instantanée et le World...) très efficace des informations en cherchant le parcours le plus efficace.

Les routeurs IS-IS utilisent également l'algorithme. Les sites d'itinéraires routiers l'utilise de la même manière et permettent de nombreuses adaptations en ajustant le poids des arcs comme par exemple : trajet le plus économique, le plus rapide...

Apparition dans la culture (La Culture est une civilisation pan-galactique inventée par Iain M. Banks au travers de ses romans et nouvelles de science-fiction. Décrite avec beaucoup de précision et de détail, La Culture peut...) populaire

L'algorithme de Dijkstra est utilisé par les enquêteurs de la série NUMB3RS, dans l'épiode 23 de la saison (La saison est une période de l'année qui observe une relative constance du climat et de la température. D'une durée d'environ trois mois (voir le tableau Solstice et Équinoxe ci-dessous), la saison joue un...) 3.

Source: Wikipédia publiée sous licence CC-BY-SA 3.0.

Vous pouvez soumettre une modification à cette définition sur cette page. La liste des auteurs de cet article est disponible ici.