Outils pour utilisateurs

Outils du site


les_exposes:plus_court_chemin

Différences

Ci-dessous, les différences entre deux révisions de la page.

Lien vers cette vue comparative

Les deux révisions précédentes Révision précédente
les_exposes:plus_court_chemin [02/11/2016 12:15]
paquier
les_exposes:plus_court_chemin [02/11/2016 12:25]
paquier
Ligne 14: Ligne 14:
  
 Plus précisément,​L'​algorithme de Dijkstra calcule des plus courts chemins à partir d'une source dans un graphe orienté pondéré par des réels positifs. Plus précisément,​L'​algorithme de Dijkstra calcule des plus courts chemins à partir d'une source dans un graphe orienté pondéré par des réels positifs.
-On peut aussi l'​utiliser pour calculer un plus court chemin entre une source et un sommet d'​arrivée+On peut aussi l'​utiliser pour calculer un plus court chemin entre une source et un sommet ​ 
 +d'​arrivée 
 + 
 + 
 +__**Exemple**__ 
 + 
 +Le graphe ci-dessous représente le réseau routier d'une région qui prend en compte le sens de la circulation,​ chaque arc représente une route à sens unique dont le poids est la distance en kilomètre entre deux sommets. {{ :​les_exposes:​sans_titre.png |}}
  
 L'​algorithme dû à Dijkstra est basé sur le principe suivant : L'​algorithme dû à Dijkstra est basé sur le principe suivant :
Ligne 22: Ligne 28:
 On construit de proche en proche le chemin cherché en choisissant à chaque itération de l'​algorithme,​ un sommet si 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 à si soit la plus courte possible. On construit de proche en proche le chemin cherché en choisissant à chaque itération de l'​algorithme,​ un sommet si 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 à si soit la plus courte possible.
  
-**__ +**Initialisation ​de l'algorithme ​:**
-Exemple pour mieux comprendre:​ +
-__ +
-** +
- +
-L'​algorithme prend en entrée un graphe orienté pondéré par des réels positifs et un sommet source.  +
-{{:​les_exposes:​545px-dijkstrabis01.svg.png?​200|}} +
- +
-Il s'​agit ​de construire progressivement un sous-graphe dans lequel sont classés les différents sommets par ordre croissant de leur distance minimale au sommet de départ. La distance correspond à la somme des poids des arcs empruntées. +
- +
- +
-Au départ, on considère que les distances de chaque sommet au sommet de départ sont infinies sauf pour le sommet de départ pour lequel la distance est de 0. Le sous-graphe de départ est l'ensemble vide. +
- +
-Au cours de chaque itération, on choisit en dehors du sous-graphe un sommet de distance minimale et on l'​ajoute au sous-graphe. Ensuite, on met à jour les distances des sommets voisins de celui ajouté. La mise à jour s'​opère comme suit la nouvelle distance du sommet voisin est le minimum entre la distance existante et celle obtenue en ajoutant le poids de l'arc entre sommet voisin et sommet ajouté à la distance du sommet ajouté. +
- +
-On continue ainsi jusqu'​à épuisement des sommets (ou jusqu'​à sélection du sommet d'​arrivée). +
- +
-**__Exemple en image__** +
- +
-{{:​les_exposes:​545px-dijkstrabis01.svg.png?​200|}} +
- +
- +
-<-- on choisit la ville A. On met à jour les villes voisines de A qui sont B, C, et E. Leurs distances deviennent respectivement 85, 217, 173, tandis que les autres villes restent à une distance infinie. +
- +
-{{:​les_exposes:​545px-dijkstrabis02.svg.png?​200|}}  +
- +
- +
-<-- on choisit la ville B. En effet, c'est la ville hors du sous-graphe qui est à la distance minimale (85). On met à jour le seul voisin (F). Sa distance devient 85+80 = 165. +
- +
- +
-{{:​les_exposes:​545px-dijkstrabis03.svg.png?​200|}} +
-  +
- +
-<-- : on choisit F. On met à jour le voisin I (415). +
- +
-{{:​les_exposes:​545px-dijkstrabis04.svg.png?​200|}} +
-  +
- +
-<​-- ​ on choisit E. On met à jour le voisin J (675). +
- +
-{{:​les_exposes:​545px-dijkstrabis05.svg.png?​200|}}  +
- +
- +
-<-- la distance la plus courte en dehors du sous-graphe est maintenant celle de la ville C. On choisit donc C. On met à jour la ville G (403) et la ville H (320). +
- +
-{{:​les_exposes:​545px-dijkstrabis06.svg.png?​200|}} +
- +
- +
- <​-- la distance la plus courte en dehors du    sous-graphe est maintenant celle de la ville H (320). On choisit donc H. On met à jour la ville D (503) et la ville J (487< 675). +
- +
-{{:​les_exposes:​545px-dijkstrabis07.svg.png?​200|}}  +
- +
- +
-<-- la distance la plus courte suivante est celle de la ville G. On choisit G. La mise à jour ne change aucune autre distance.+
  
-{{:les_exposes:​545px-dijkstrabis08.svg.png?200|}}+Étape 1 On affecte le poids 0 au sommet origine (E) et on attribue provisoirement un poids ∞ aux autres sommets.
  
 +**Répéter les opérations suivantes tant que le sommet de sortie (S) n'est pas affecté d'un poids définitif**
  
-<​-- ​ la distance la plus courte suivante est celle de la ville I. La distance de la ville voisine J n'est pas modifiée car la distance existante est inférieure à celle que l'on obtiendrait en passant par I (415 + 84 > 487).+Étape 2 : Parmi les sommets dont le poids n'est pas définivement fixé choisir le sommet X de poids p minimal. Marquer définitivement ce sommet X affecté du poids p(X).
  
-{{:les_exposes:545px-dijkstrabis09.svg.png?​200|}} ​+Étape 3 Pour tous les sommets Y qui ne sont pas définitivement marqués, adjacents au dernier sommet fixé X :
  
 +°Calculer la somme s du poids de X et du poids de l'​arête reliant X à Y.
 +° Si la somme s est inférieure au poids provisoirement affecté au sommet Y, affecter ​         provisoirement à Y le nouveau poids et indiquer entre parenthèses le sommet X pour se souvenir de sa provenance. ​
  
-<-- la ville dont la distance ​est la plus courte est J (487). On choisit J et on l'​ajoute au sous-graphe. On s'​arrête puisque la ville d'​arrivée est maintenant dans le sous-graphe.+**Quand le sommet S est défintivement marqué**
  
-//On connaît ainsi le chemin le plus court menant ​de à J, il passe par C et H et mesure 487 km.// +Le plus court chemin ​de à S s'​obtient en écrivant de gauche à droite le parcours en partant de la fin S
-__** + {{ :​les_exposes:​1222.png |}}
-Sous forme de tableau**__+
  
-On peut aussi résumer l'​exécution ​de l'​algorithme de Dijkstra avec un tableau. Chaque étape correspond à une ligne. ​ +Pour faciliter la recherche du plus court chemin il est commode ​de présenter les résultats dans un tableau  
-Une ligne donne les distances courantes des sommets depuis le sommet de départ. +{{:​les_exposes:​tableau.png|}}
-Une colonne donne l'​évolution des distances d'un sommet donné depuis le sommet de départ au cours de l'​algorithme.  +
-La distance d'un sommet choisi (car minimale) est soulignée. Les distances mises à jour sont barrées si elles sont supérieures à des distances déjà calculées.+
  
-{{ :les_exposes:​tablo.png |}}+Pour déterminer le trajet le plus court on remonte les sommets en partant de S S vient de F qui vient de C qui vient de E.
  
-Le tableau donne non seulement la distance minimale de la ville A à la ville J (487) mais aussi le chemin à suivre à rebours (J - H - C - A) pour aller de A à J ainsi que toutes les distances minimales de la ville A aux autres villes rangées par ordre croissant. 
les_exposes/plus_court_chemin.txt · Dernière modification: 02/11/2016 12:25 par paquier