Remerciez-le!

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

Distance entre la ville A et la ville J L'exemple suivant montre les étapes suc

Distance entre la ville A et la ville J L'exemple suivant montre les étapes successives dans la résolution du chemin le plus court dans un graphe. Les nœuds symbolisent des villes identifiées par une lettre et les arêtes indiquent la distance entre ces villes. On cherche à déterminer le plus court trajet pour aller de la ville A à la ville J. Étape 1 : à partir de la ville A, 3 villes sont accessibles, B, C, et E qui se sont alors affectées des poids respectifs de 85, 217, 173, tandis que les autres villes sont affectées d'une distance infinie. Étape 2 : la distance la plus courte est celle menant à la ville B. Le passage par la ville B ouvre la voie à la ville F (85+80 = 165). Étape 3 : La distance la plus courte suivante est celle menant à la ville F. Le passage par la ville F ouvre une voie vers la ville I (415). Étape 4 : La distance la plus courte suivante est alors celle menant à la ville E. Le passage par la ville E ouvre une voie vers la ville J (675). Étape 5 : la distance la plus courte suivante mène alors à la ville C. Le passage par la ville C ouvre une voie vers la ville G (403) et la ville H (320). Étape 6: la distance la plus courte suivante mène à 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). Étape 7 : la distance la plus courte suivante mène à la ville G et ne change aucune autre distance. Étape 8 : la distance la plus courte suivante mène à la ville I. Le passage par la ville I ouvre un chemin vers la ville J qui n'est pas intéressant (415 + 84 > 487). Étape 9 : la distance la plus courte suivante mène à la ville J (487). On connaît ainsi le chemin le plus court menant de A à J, il passe par Cet H et mesure 487 km. Présentation sous forme de tableau L'illustration par une série de graphes peut se révéler un peu longue. Il est d'autre part un peu plus difficile de repérer le chemin le plus court à l'issue du dessin. Ainsi l'algorithme de Dijkstra est souvent réalisé à l'aide d'un tableau dans lequel chaque étape correspond à une ligne.À partir de la matrice des arcs orientés reliant les diverses villes : Matrice des arcs orientés à A à B à C à D à E à F à G à H à I à J De A 0 85 217 ∞ 173 ∞ ∞ ∞ ∞ ∞ De B 85 0 ∞ ∞ ∞ 80 ∞ ∞ ∞ ∞ De C 217 ∞ 0 ∞ ∞ ∞ 186 103 ∞ ∞ De D ∞ ∞ ∞ 0 ∞ ∞ ∞ 183 ∞ ∞ De E 173 ∞ ∞ ∞ 0 ∞ ∞ ∞ ∞ 502 De F ∞ 80 ∞ ∞ ∞ 0 ∞ ∞ 250 ∞ De G ∞ ∞ 186 ∞ ∞ ∞ 0 ∞ ∞ ∞ De H ∞ ∞ 103 183 ∞ ∞ ∞ 0 ∞ 167 De I ∞ ∞ ∞ ∞ ∞ 250 ∞ ∞ 0 84 De J ∞ ∞ ∞ ∞ 502 ∞ ∞ 167 84 0 On construit un tableau dans lequel les distances d'un sommet au sommet de départ sont regroupées dans une même colonne. Les sommets sélectionnés sont soulignés. Les distances des voies ouvertes par la sélection d'un nouveau sommet sont barrées si elles sont supérieures à des distances déjà calculées. Quand un sommet est sélectionné, c'est que l'on a découvert sa distance minimale au sommet de départ, il est alors inutile de chercher d'autres distances de ce sommet au point de départ. à B à C à D à E à F à G à H à I à J A 85 217 ∞ 173 ∞ ∞ ∞ ∞ ∞ B(85A) - 217 ∞ 173 165 ∞ ∞ ∞ ∞ F(165B) - 217 ∞ 173 - ∞ ∞ 415 ∞ E(173A) - 217 ∞ - - ∞ ∞ 415 675 C(217A) - - ∞ - - 403 320 415 675 H(320C) - - 503 - - 403 - 415 487 G(403C) - - 503 - - - - 415 487 I(415F) - - 503 - - - - - 499487 J(487H) - - 503 - - - - - - D(503H) - - - - - - - - - La construction de ce tableau donne non seulement la distance minimale de la ville A à la ville J mais aussi le chemin à suivre (J - H - C - A) ainsi que toutes les distances minimales de la ville A aux autres villes rangées par ordre croissant. Notations Le graphe est noté où :  l'ensemble est l'ensemble des sommets du graphe ;  l'ensemble est l'ensemble des arêtes de tel que : si est dans , alors il existe une arête depuis le nœud vers le nœud ;  on définit la fonction définie sur qui renvoie le poids positif de l'arête reliant à (et un poids infini pour les paires de sommets qui ne sont pas connectées par une arête). Principe L'algorithme se termine soit quand devient un arbre couvrant de , soit quand tous les nœuds d'intérêt2 sont dans . On peut donc écrire l'algorithme de la façon suivante : Entrées : un graphe avec une valuation positive des arêtes, un sommet de Initialiser tous les sommets comme étant « non marqué ». Affecter la valeur à tous les labels Tant Qu'il existe un sommet non marqué Choisir le sommet non marqué de plus petit label Marquer Pour chaque sommet non marqué voisin de Fin Pour Fin Tant Que Le poids du chemin entre deux sommets est la somme des poids des arêtes qui le composent. Pour une paire donnée de sommets (le sommet du départ) (sommet d'arrivée) appartenant à , l'algorithme trouve le chemin depuis vers de moindre poids (autrement dit le chemin le plus léger ou encore le plus court). L'algorithme fonctionne en construisant un sous-graphe de manière à ce que la distance entre un sommet de depuis soit connue et soit un minimum dans . Initialement contient simplement le nœud isolé, et la distance de à lui-même vaut zéro. Des arcs sont ajoutés à à chaque étape : 1. en identifiant toutes les arêtes dans tel que est dans et est dans ; 2. en choisissant l'arête dans qui donne la distance minimum depuis à en passant tous les chemins créés menant à ce nœud. uploads/Geographie/ plus-court-chemin-algorithme-de-dijkstra 1 .pdf