Outils pour utilisateurs
Ceci est une ancienne révision du document !
Comment un GPS peut trouver le plus court chemin parmi plusieurs?
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.
←- execution de l'algorithme.
L'algorithme porte le nom de son inventeur, l'informaticien néerlandais Edsger Dijkstra, et a été publié en 19591.
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
Exemple pour mieux comprendre:
L'algorithme prend en entrée un graphe orienté pondéré par des réels positifs et un sommet source.
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).
Outils de la page
