Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Le probl` eme du plus court chemin : algorithme de Dijkstra Cours d’ASD Science

Le probl` eme du plus court chemin : algorithme de Dijkstra Cours d’ASD Sciences de l’Ing´ enieur H´ el` ene Renard (Marc Gaetano) 12/16 mai 2011 Dijkstra Question existentielle ! Exemples : ; Livreur de pizzas ; ; Mr Dupont -> gare de Strasbourg, direction Biarritz ; ; Synchronisation entre l’Intermarch´ e et le cimeti` ere d’Antony ; ; Internet -> donn´ ees dans le monde entier ? Quelle route au fait ? H´ el` ene Renard Algorithme de Dijkstra 2 Le probl` eme des plus courts chemins Qui dit trajet dit probl` eme des plus courts chemins. Qui dit probl` eme dit n´ ecessit´ e de trouver une solution. Probl` eme ´ Etant donn´ e un ensemble de points et un ensemble de liaisons entre ces points caract´ eris´ ees par un certain poids, comment trouver le chemin le plus court, le moins cher, le plus agr´ eable entre deux points ? L’´ etude suivante pr´ esente l’algorithme de Dijkstra permettant de r´ esoudre la question en θ((|n| + |a|)lg|n|) o` u n est le nombre de points et a le nombre de liaisons, dans le meilleur des cas. H´ el` ene Renard Algorithme de Dijkstra 3 Exemples concrets : distance entre la ville A et la ville J Les nœuds symbolisent des villes identiﬁ´ ees par une lettre et les arˆ etes indiquent la distance entre ces villes. Le plus court trajet pour aller de la ville A ` a la ville J. Figure: ´ Etape 1 →` A partir de la ville A, 3 villes sont accessibles, B, C, et E qui se voient donc aﬀect´ ees des poids respectifs de 85, 217, 173, tandis que les autres villes sont aﬀect´ ees d’une distance inﬁnie. H´ el` ene Renard Algorithme de Dijkstra 4 Exemples concrets : distance entre la ville A et la ville J Les nœuds symbolisent des villes identiﬁ´ ees par une lettre et les arˆ etes indiquent la distance entre ces villes. Le plus court trajet pour aller de la ville A ` a la ville J. Figure: ´ Etape 2 →La distance la plus courte est celle menant ` a la ville B. Le passage par la ville B ouvre la voie ` a la ville F (85+80 = 165). H´ el` ene Renard Algorithme de Dijkstra 4 Exemples concrets : distance entre la ville A et la ville J Les nœuds symbolisent des villes identiﬁ´ ees par une lettre et les arˆ etes indiquent la distance entre ces villes. Le plus court trajet pour aller de la ville A ` a la ville J. Figure: ´ Etape 3 →La distance la plus courte suivante est celle menant ` a la ville F. Le passage par la ville F ouvre une voie vers la ville I (415). H´ el` ene Renard Algorithme de Dijkstra 4 Exemples concrets : distance entre la ville A et la ville J Les nœuds symbolisent des villes identiﬁ´ ees par une lettre et les arˆ etes indiquent la distance entre ces villes. Le plus court trajet pour aller de la ville A ` a la ville J. Figure: ´ Etape 4 →La distance la plus courte suivante est alors celle menant ` a la ville E. Le passage par la ville E ouvre une voie vers la ville J (675). H´ el` ene Renard Algorithme de Dijkstra 4 Exemples concrets : distance entre la ville A et la ville J Les nœuds symbolisent des villes identiﬁ´ ees par une lettre et les arˆ etes indiquent la distance entre ces villes. Le plus court trajet pour aller de la ville A ` a la ville J. Figure: ´ Etape 5 →La distance la plus courte suivante m` ene alors ` a la ville C. Le passage par la ville C ouvre une voie vers la ville G (403) et la ville H (320). H´ el` ene Renard Algorithme de Dijkstra 4 Exemples concrets : distance entre la ville A et la ville J Les nœuds symbolisent des villes identiﬁ´ ees par une lettre et les arˆ etes indiquent la distance entre ces villes. Le plus court trajet pour aller de la ville A ` a la ville J. Figure: ´ Etape 6 →La distance la plus courte suivante m` ene ` a ville H(320). Le passage par la ville H ouvre une voie vers la ville D et un raccourci vers la ville J (487 < 675). H´ el` ene Renard Algorithme de Dijkstra 4 Exemples concrets : distance entre la ville A et la ville J Les nœuds symbolisent des villes identiﬁ´ ees par une lettre et les arˆ etes indiquent la distance entre ces villes. Le plus court trajet pour aller de la ville A ` a la ville J. Figure: ´ Etape 7 →La distance la plus courte suivante m` ene ` a la ville G et ne change aucune autre distance. H´ el` ene Renard Algorithme de Dijkstra 4 Exemples concrets : distance entre la ville A et la ville J Les nœuds symbolisent des villes identiﬁ´ ees par une lettre et les arˆ etes indiquent la distance entre ces villes. Le plus court trajet pour aller de la ville A ` a la ville J. Figure: ´ Etape 8 →La distance la plus courte suivante m` ene ` a la ville I. Le passage par la ville I ouvre un chemin vers la ville J qui n’est pas int´ eressant (415 + 84 > 487). H´ el` ene Renard Algorithme de Dijkstra 4 Exemples concrets : distance entre la ville A et la ville J Les nœuds symbolisent des villes identiﬁ´ ees par une lettre et les arˆ etes indiquent la distance entre ces villes. Le plus court trajet pour aller de la ville A ` a la ville J. Figure: ´ Etape 9 →La distance la plus courte suivante m` ene ` a la ville J (487). On connait ainsi le chemin le plus court menant de A ` a J, il passe par C et H et mesure 487 km. H´ el` ene Renard Algorithme de Dijkstra 4 Exemples concrets : pr´ esentation sous forme de tableau Figure: La construction de ce tableau donne non seulement la distance mi- nimale de la ville A ` a la ville J mais aussi le chemin ` a suivre (J - H - C - A) ainsi que toutes les distances minimales de la ville A aux autres villes rang´ ees par ordre croissant. H´ el` ene Renard Algorithme de Dijkstra 5 Exemples concrets : le livreur de pizzas ! Exemple 2 : Cherchons les plus courts chemins d’origne E et de destina- tion S dans ce graphe avec le tableau correspondant : On se place au sommet de plus petit poids, ici le sommet E H´ el` ene Renard Algorithme de Dijkstra 6 Exemples concrets : le livreur de pizzas ! Exemple 2 : Cherchons les plus courts chemins d’origne E et de destina- tion S dans ce graphe avec le tableau correspondant : On ´ etudie chacune des arˆ etes partant du sommet choisi. Dans les colonnes, on met la distance ` a E, et le sommet d’o` u l’on vient. On se place de nouveau au sommet de plus petit poids, ici B. H´ el` ene Renard Algorithme de Dijkstra 6 Exemples concrets : le livreur de pizzas ! Exemple 2 : Cherchons les plus courts chemins d’origne E et de destina- tion S dans ce graphe avec le tableau correspondant : Et ainsi de suite. H´ el` ene Renard Algorithme de Dijkstra 6 Exemples concrets : le livreur de pizzas ! Exemple 2 : Cherchons les plus courts chemins d’origne E et de destina- tion S dans ce graphe avec le tableau correspondant : Et ainsi de suite. H´ el` ene Renard Algorithme de Dijkstra 6 Exemples concrets : le livreur de pizzas ! Exemple 2 : Cherchons les plus courts chemins d’origne E et de destina- tion S dans ce graphe avec le tableau correspondant : Et ainsi de suite. H´ el` ene Renard Algorithme de Dijkstra 6 Exemples concrets : le livreur de pizzas ! Exemple 2 : Cherchons les plus courts chemins d’origne E et de destina- tion S dans ce graphe avec le tableau correspondant : Et ainsi de suite. H´ el` ene Renard Algorithme de Dijkstra 6 Exemples concrets : le livreur de pizzas ! Exemple 2 : Cherchons les plus courts chemins d’origne E et de destina- tion S dans ce graphe avec le tableau correspondant : Et ainsi de suite. H´ el` ene Renard Algorithme de Dijkstra 6 Plan de la pr´ esentation 1. Principes de l’algorithme de Dijkstra Description de l’algorithme Impl´ ementation de l’algorithme de Dijkstra 2. Complexit´ e 3. Conclusion 4. Exercices H´ el` ene Renard Algorithme de Dijkstra 7 Principes de l’algorithme de Dijkstra Plan de la pr´ esentation 1. Principes de l’algorithme de Dijkstra Description de l’algorithme Impl´ ementation de l’algorithme de Dijkstra 2. Complexit´ e 3. Conclusion 4. uploads/Geographie/ slides-dijkstra.pdf