Différences

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

--- les_exposes:plus_court_chemin [30/10/2016 18:37]
paquier
+++ les_exposes:plus_court_chemin [02/11/2016 12:25] (Version actuelle)
paquier
@@ Ligne 2: / Ligne 2: @@
 **__
-L'algorithme de Dijkstra permet de déterminer le plus court chemin pour se rendre d'un endroit a un autre par exemple d'une ville a une autre sachant le reseau routier de la région.
+E. W. Dijkstra a proposé en 1959 un algorithme qui permet de déterminer le plus court chemin entre deux sommets d'un graphe connexe pondéré (orienté ou non) dont le poids lié aux arêtes est positif ou nul.
+L'algorithme de Dijkstra permet par exemple de déterminer le plus court chemin pour se rendre d'un endroit a un autre par exemple d'une ville a une autre sachant le reseau routier de la région.
 {{:les_exposes:dijkstra_animation.gif?200|}}  <-- execution de l'algorithme.
-L'algorithme porte le nom de son inventeur, l'informaticien néerlandais **Edsger Dijkstra**, et a été publié en 19591.
+L'algorithme porte le nom de son inventeur, l'informaticien néerlandais **Edsger Dijkstra**, et a été publié en 1959.
 {{ :les_exposes:edsger.jpg?200 |}}
@@ Ligne 12: / 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.
-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 :
+Si le plus court chemin reliant E à S passe par les sommets s1 , s2 , …, sk alors, les différentes étapes sont aussi les plus courts chemins reliant E aux différents sommets s1 , s2 , …, sk.
+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 :**
+É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**
+É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).
+É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.
-Exemple pour mieux comprendre:
+° 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.
-__
-**
-L'algorithme prend en entrée un graphe orienté pondéré par des réels positifs et un sommet source.
+**Quand le sommet S est défintivement marqué**
-{{: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.
+Le plus court chemin de E à S s'obtient en écrivant de gauche à droite le parcours en partant de la fin S.
+ {{ :les_exposes:1222.png |}}
-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.
+Pour faciliter la recherche du plus court chemin il est commode de présenter les résultats dans un tableau
+{{:les_exposes:tableau.png|}}
-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é.
+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.
-On continue ainsi jusqu'à épuisement des sommets (ou jusqu'à sélection du sommet d'arrivée).

Wiki ISN

Outils pour utilisateurs

Outils du site

Différences

Outils de la page