Différences

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

--- les_exposes:plus_court_chemin [30/10/2016 19:04]
paquier
+++ les_exposes:plus_court_chemin [02/11/2016 12:15]
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 13: / Ligne 15: @@
 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
+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.
 **__

Wiki ISN

Outils pour utilisateurs

Outils du site

Différences

Outils de la page