L'algorithme de Dijkstra opère sur un graphe connexe pondéré, pas En ligne 15, on vérifie si une amélioration de l'estimation du chemin optimal est possible
si dans la file f, c'est-à-dire ligne 10 de l'algorithme 2 L'algorithme de Dijkstra permet de calculer les plus courts chemins dans le cas où tous les coûts sont
ces petits dessins des graphes, les points des sommets et les lignes des arcs ou L'algorithme de Dijkstra ne marche pas toujours quand le graphe contient
de l'algorithme de Dijkstra On enregistre un graphe orienté pondéré sous forme d'un fichier ASCII dont — la premi`ere ligne contient le nombre de sommets
Le but de l'algorithme de Dijkstra est de trouver un chemin le plus court entre algorithme sous forme de tableau, avec une colonne par sommet et une ligne
point A à un point B ? – Ben, la ligne droite – Mais non, c'est le L'algorithme de DIJKSTRA est sans doute le plus utilisé car il est aisé à mettre en œuvre
En sortie, la matrice B, de ligne courante S, contient le tableau de progression de l'algorithme La longueur minimale est dans la variable T et la chaine
La description des lignes de métro sera faite dans des fichiers ”texte” en Appeler l'algorithme de Dijkstra sur ce graphe pour en déduire des itinéraires et
Pour appliquer l'algorithme de DIJKSTRA à un graphe connexe pondéré, orienté Il est possible que l'algorithme n'utilise pas toutes les lignes du tableau dans
[PDF] algorithme de dijkstra java
[PDF] algorithme de dijkstra javascript
[PDF] algorithme dichotomie python
[PDF] algorithme factorielle boucle pour
[PDF] algorithme factorielle en c
[PDF] algorithme factorielle n
[PDF] algorithme factorielle pascal
[PDF] algorithme factorielle python
[PDF] algorithme fonction procedure exercice corrigé pdf
[PDF] algoritmo de dijkstra aplicaciones
[PDF] algoritmo de dijkstra c++
[PDF] algoritmo de dijkstra em c
[PDF] algoritmo de dijkstra grafos
[PDF] algoritmo de dijkstra online
[PDF] algoritmo de dijkstra python
RECHERCHE OPERATIONNELLE PLUS COURTS CHEMINS DANS DES GRAPHES VALUES I INTRODUCTION (1) Notations, Problèmes (2) Quelques résultats fondamentaux (3) Structures de données II PLUS COURTS CHEMINS D'UN SOMMET A TOUS LES AUTRES (1) Algorithme de DIJKSTRA (2) Algorithme de BELLMAN-FORD III PLUS COURTS CHEMINS ENTRE TOUS LES COUPLES DE SOMMETS (1) Algorithme de DANTZIG (2) Algorithme de FLOYD
1 I - INTRODUCTION Tout le monde connaît la boutade : " Quel est le plus court chemin pour aller d'un point A à un point B ? - Ben, la ligne droite ... - Mais non, c'est le raccourci ! » Ce que confirment les êtres infiniment plats, en fait chacun réduit à un point, vivant sur S2, la surface de la sphère usuelle, qui savent tous dès leur plus jeune age (mais est-ce aussi le cas des chauffeurs de taxi ?) que pour aller de A à B il faut utiliser un arc de grand cercle, en bref suivre la géodésique locale Et oui, si Ulysse l'avait su Pénélope eût été ravie Ou alors, comme dit le Chat : " Le plus court chemin d'un point à un autre c'est de ne pas y aller » ... Certes, mais allons y tout de même De fait de nombreux problèmes de RO reviennent à déterminer l'existence de chemins, ou les meilleurs chemins, en un sens à préciser, entre certains ou tous les sommets d'un graphe. On les rencontre dès qu'il s'agit d'acheminer par exemple des marchandises entre deux points d'un réseau ou d'un entrepôt à des centres de vente, de façon à minimiser un coût, une durée, e tc. Ils appara issent aussi en sous problème s de nombreux problèmes combinatoires comme les flots et les ordonnancements (1) Notations, Problèmes Nous nous plaçons dans le cadre général suivant Soit G = ( X, U, v) un graphe simple orienté val ué : tout arc xy est muni d'une valuation v(x, y) (coût, temps, distance, capacité, ...) réelle quelconque On utilise aussi les mots pondéré et pondération à la place de valué et valuation Si C = (x1, x2, ... , xk) est un chemin de G de x1 à xk sa longueur est : v(C) = v(x1, x2, ... , xk) = v(x
i i=1 k-1 x i+1
= d(x1, xk) Si x1 es t un sommet fixé à l'avanc e on pourra noter plus simplem ent d(xk) la " distance » de x1 à tout sommet xk, bien sûr d(x1) = 0 Les problèmes étudiés ici sont : (P1) Recherche des plus courts chemins reliant un sommet à tous les autres (P2) Recherche de tous les plus courts chemins entre tous les couples de sommets Notons qu'il n'y a pas de solution spécifique au problème consistant à chercher un plus court chemin entre deux sommets x et y particuliers d'un graphe, il se résout en résolvant (P1) : partant de x on s'arrête arrivé en y
2 Les algorithmes étudiés ici sont ceux de DIJKSTRA et de BELLMAN - FORD qui résolvent (P1) respectivement lorsque v ≥ 0 puis lorsque v est quelconque, et les algorithmes de DANTZIG et de FLOYD qui résolvent (P2) L'algorithme de DIJKSTRA est sans doute le plus utilisé car il est aisé à mettre en oeuvre, efficace en temps d'exécution et bien adapté aux situations courantes, c'est pourquoi nous en donnerons une écriture détaillée Nous détaillerons aussi l'algorithme de DANTZIG car il est matriciel, donc facile à mettre en oeuvre, et plus efficace que l'algorithme de BELLMAN - FORD appliqué à tous les sommets lorsque v est quelconque. Puis nous présentons succinctement l'algorithme de FLOYD dont les détails sont laissés en exercice Pour simplifier nous écrirons " PC2 » pour " Plus Court(s) Chemin(s) » Conventionnellement : | X | = n, X = {1, 2, ..., n}, les sommets sont numérotés de 1 à n, et | U | = m (et | E | = m, si le graphe est non orienté) Considérons par exemple le graphe orienté valué suivant ayant 6 sommets (1, 2, ..., 6) et 11 arcs où tous les couples de chemins existent et dont les valuations sont indiquées sur les arcs : 1 5 2 6 3 3 3 2 1 1 4 2 2 1 6 Les deux arcs 34 et 43 existent et v(3, 4) = 1 et v(4, 3) = 3 Nous utiliserons cet exemple pour illustrer chacun des algorithmes étudiés (2) Quelques résultats fondamentaux Un circuit absorbant de G est un circuit de longueur négative Les trois Théorèmes suivants donnent les conditions d'existence des PC2 ainsi que leurs structures Théorème 1 (P1) a une solution à partir de s ∈ X si et seulement si s est racine (ie il y a un chemin de s à tous les autres sommets) et G est sans circuit absorbant Donc si G = (X, E, v) est un graphe simple non orienté connexe valué où v ≥ 0 alors (P1), donc (P2), a toujours une solution à partir de tout sommet de G, mais cette solution n'est pas nécessairement unique
4 II - PLUS COURTS CHEMINS D'UN SOMMET A TOUS LES AUTRES (1) Algorithme de DIJKSTRA L'algorithme de DIJKSTRA (1959) résout (P1) lorsque v ≥ 0 Principe et squelette de l'algorithme A chaque étape l'ensemble des sommets est divisé en trois parties disjointes : V = {sommets visités} est l'ensemble des sommets x pour lesquels d(x) est connue, 1 ∈ V et d(1) = 0 A = {sommets atteints} est l'ensemble des successeurs immédiats et non visités des sommets visités, pour ces sommets on a une estimation de la distance X - (V ∪ A) pour lesquels d(y) = ∞ L'algorithme consiste tout simplement alors à prendre dans A le sommet ayant la plus petite distance estimée Initialement : V = {1}, d(1) = 0 et p(1) = 1 A = {successeurs immédiats de 1} et d(x) = M(1, x), p(x) = 1 si x ∈ A d (y) = ∞ pour tout y dans X - (V ∪ A) Etape courante (jusqu'à visiter tous les sommets) : choix de x dans A tel d(x) soit minimal V = V ∪ {x} A = A - {x} ∪ {y | y successeur de x ni visité ni atteint} pour chaque successeur non visité y de x on calcule d(y) = min {d(y), d(x) + M(x, y)}, on aura alors p(y) = x si le minimum change Si nous appliquons l'algorithme sur notre exemple, il y a 6 étapes qui sont : Etape initiale : V = {1}, d(1) = 0, p(1) = 1, A = {3, 4} (ce sont les successeurs de 1) avec d(3) = 6, d(4) = 2 et p(3) = 1, d(4) = 1, tous les autres sommets ont une distance infinie et leurs prédécesseurs sont à 0 Première étape : 4 est choisi donc V = {1, 4} et sa distance (définitive) est d(4) = 2, on a maintenant A = {2, 3}, d(2) = 4, d(3) = 5, p(2) = 4, p(3) = 4, les autres sommets ont une distance infinie et sont sans prédécesseur, dans la suite nous ne m entionnerons plus ces sommets, seuls seront mentionnés les sommets de V et A Deuxième étape : 2 est choisi donc V = {1, 2, 4} et sa distance est d(2) = 4, d'où A = {3}, d(3) = 5 et p(3) = 4 Troisième étape : 3 est choisi donc V = {1, 2, 3, 4} et sa distance est d(3) = 5, d'où A = {5, 6}, d(5) = 8, d(6) = 6 et p(5) = 3, p(6) = 3 Quatrième étape : 6 est choisi donc V = {1, 2, 3, 4, 6} et sa distance est d(6) = 6 et p(6) = 3, d'où A = {5}, d(5) = 7 et p(5) = 6
5 Cinquième et dernière étape (car à l'issue de cette étape tous les sommets sont visités) : 5 est choisi donc V = {1, 2, 3, 4, 5, 6}, sa distance est d(5) = 7 et p(5) = 6 On peut illustrer avantageusement la suite des calculs par la tableau suivant : 2 3 4 5 6 V = {1} ∞ 6, 1 2, 1 ∞ ∞ V = {1, 4} 4, 4 5, 4 - ∞ ∞ V = {1, 2, 4} - 5, 4 - ∞ ∞ V = {1, 2, 3, 4} - - - 8, 3 6, 3 V = {1, 2, 3, 4, 6} - - - 7, 6 - V = {1, 2, ..., 6} 4, 4 5, 4 2, 1 7, 6 6, 3 Chaque ligne contient V, les distances estimées ou définitives (en gras) de 1 à chaque sommet ainsi que le prédécesseur courant. Par exemple en ligne 2 : V = {1, 4}, 4 a été choisi, sa distance est 2, elle est définitive, son prédécesseur est 1 (inutile donc de mentionner à nouveau ces renseignements dans les lignes suivantes) et les distances estimées sont celles des sommets 2 et 3, notées avec les prédécesseurs courants respectifs La dernière ligne correspondant à la dernière étape contient les résultats définitifs Le graphe partiel des plus courts chemins trouvés correspond à l'arborescence suivante : 1 5 3 2 1 1 3 2 4 6 2 Ce graphe partiel est bien entendu construit à partir du tableau p des prédécesseurs
6 A ti tre d'exemple, nous donnons ci dessous une écriture détaillée possible de l'algorithme Précisons tout d'abord les structures de données choisies, rappelons que les sommets sont numérotés 1, 2, ... , n : - Matrice d'adjacence du graphe : M (M(i, j) = v(i, j)) - Tableau des distances : d - Tableau des prédécesseurs : p - Tableaux binaires (en vrai/faux ou 0/1) de marque des visités et des atteints : visité et atteint - Tableau stockant (entre les indices 1 et k) les sommets atteints : A - Divers entiers de gestion de boucles, de comptage, de désignation de sommets, ... Sachant que les trois parties entre guillemets demandent bien sûr à être précisées, les lecteurs curieux les traduiront aisément dans leur langage préf éré, l'algorithme peut alors s'écrire : /* initialisations */ d(1) = 0 ; p(1) = 1 visité(1) = vrai s = 1 pour i = 2 à n faire visité(i) = faux atteint(i) = faux d(i) = + ∞ k = 0 pour " chaque successeur i de 1 » faire k = k + 1 A(k) = i atteint(i) = vrai d(i) = M(1, i) ; p(i) = 1 /* corps de l'algorithme */ tant que s < n faire x = " élément de A, entre 1 et k, tel que d(x) soit minimal, soit i son indice » " échanger A(i) et A(k) » k = k - 1 visité(x) = vrai s = s + 1 pour " chaque successeur y de x » faire si visité(y) = faux alors si atteint(y) = faux alors atteint(y) = vrai ; k = k + 1 ; A(k) = y D = d(x) + M(x, y) si D < d(y) alors d(y) = D ; p(y) = x
8 Exercice Un réseau aérien relie 8 villes A, B, C, D, E, F, G et H. Les durées (en heures) des trajets existant entre ces villes sont données par la matrice M suivante : A B C D E F G H A 0 6 ∞ 2 ∞ ∞ 8 ∞ B 6 0 4 1 2 ∞ 2 ∞ C ∞ 4 0 ∞ 8 1 3 ∞ D 2 1 ∞ 0 1 ∞ ∞ ∞ E ∞ 2 8 1 0 9 ∞ ∞ F ∞ ∞ 1 ∞ 9 0 ∞ 2 G 8 2 3 ∞ ∞ ∞ 0 7 H ∞ ∞ ∞ ∞ ∞ 2 7 0 M(i,j) = ∞ lorsque i ≠ j signifie bien sûr qu'il n'existe pas de liaison entre i et j (1) Dessiner le graphe non orienté correspondant. Une représentation planaire, c'est-à-dire sans intersection d'arêtes, est possible (2) Une entreprise de livraison située dans la ville A souhaitant satisfaire au mieux ses clients désire déterminer les meilleurs itinéraires c'est-à-dire les chemins de livraison les plus rapides de la ville A aux autres villes. Déterminer ces itinéraires en utilisant l'algorithme de DIJKSTRA, puis déterminer et représenter le graphe partiel de ces itinéraires (3) La compagnie aérienne gérant le réseau veut déterminer les meilleurs itinéraires entre toutes les villes. Calculer ces itinéraires (4) On fait l'hypothèse que le coût de gestion d'u ne liaison est proportionnel à sa longueur (donc à la durée du trajet). Déterminer un sous-réseau (graphe partiel) permettant de relier toute ville à toute autre ville (via éventuellement des villes intermédiaires) et qui soit le plus économique possible Éléments de réponses : (1) Placer les sommets A, D, E, F, H et G, dans cet ordre, comme sommets d'un hexagone régulier (2) d(A) = 0, d(B) = 3, d(C) = 7, d(D) = 2, d(E) = 3, d(F) = 8, d(G) = 5 et d(G) = 10. Les arêtes du graphe partiel de ces itinéraires sont : AD, BC, BD, BG, CF, DE, et FH (3) Appliquer l'algorithme de DIJKSTRA à partir de chacun des sommets du graphe (4) La solution du problème est un arbre recouvrant minimal, il suf fit d'appliquer l'Algorithme de KRUSKAL ou de PRIM (voir poly sur ce problème). L'arbre obtenu a un coût égal à 12, il est unique
12 - pour k = 3 : il faut calculer D(1, 4), D(2, 4) et D(3, 4), par exemple D(1, 4) = min ( D(1, 1) + M(1, 4), D(1, 2) + M(2, 4), D(1, 3) + M(3, 4)) = min (0 + 2, ∞ + ∞, 6 + 1) = 2, donc P(1, 4) = 1 ; il faut ensuite calculer D(4, 1), D(4, 2) et D(4, 3) puis finalement D(1, 2), D(1, 3), D(2, 1), D(2, 3), D(3, 1) et D(3, 2). Nous obtenons : D(2, 4) = 5 (P(2, 4) = 1), D(3, 4) = 1 (P(3, 4) = 3) ; D(4, 1) = 5 (P(4, 1) = 2), D(4, 2) = 2 (P(4, 2) = 2), D(4, 3) = 3 (P(4, 3) = 4) ; D(1, 2) = 4 (P(1, 2) = 4), D(1, 3) = 5 (P(1, 3) = 4), D(2, 3) = 8 (P(2, 3) = 4), D(3, 1) = 6 (P(3, 1) = 2) et D(3, 2) = 3 (P(3, 2) = 4) - pour k = 4 : nous obtenons D(1, 5) = 8 (P(1, 5) = 3), D(2, 5) = 11 (P(2, 5) = 3), D(3, 5) = 3 (P(3, 5) = 3), D(4, 5) = 6 (P(4, 5) = 3) ; D(5, 1) = 2 (P(5, 1) = 5), D(5, 2) = 6 (P(5, 2) = 4), D(5, 3) = 7 (P(5, 3) = 4), D(5, 4) = 4 (P(5, 4) = 1) ; enfin, seul changement : D(3, 1) = 5 (P(3, 1) = 5) - pour k = 5 : nous obtenons D(1, 6) = 6 (P(1, 6) = 3, D(2, 6) = 9 (P(2, 6) = 3), D(3, 6) = 1 (P(3, 6) = 3), D(4, 6) = 4 (P(4, 6) = 3), D(5, 6) = 8 (P(5, 6) = 3) ; D(6, 1) = 3 (P(6, 1) = 5), D(6, 2) = 2 (P(6, 2) = 4), D(6, 3) = 4 (P(6, 3) = 4), D(6, 4) = 1 (P(6, 4) = 6), D(6, 5) = 1 (P(6, 5) = 6) ; enfin, les derniers changements sont : D(1, 5) =7 (P(1, 5) = 6), D(2, 5) = 10 (P(2, 5) =6), D(3, 1) = 4 (P(3, 1) = 5), D(3, 5) = 2 (P(3, 5) = 6), D(4, 5) = 5 (P(4, 5) = 6) Il est facile d'établir Théorème Si G est sans circuit absorbant l'algorithme de DANTZIG calcule au plus un PC2 entre tous les couples de sommets du graphe en O(n3) en temps et en O(n2) en espace Comme pour l'algorithme de DIJKSTRA, nous donnons ci dessous quelques éléments précisant chacune des étapes de l'algorithme de DANTZIG et permettant d'en faire plus facilement l'estimation des coûts Les structures de données nécessaires sont : - La matrice d'adjacence du graphe M (M(i, j) = v(i, j)) - La matrice des distances D - La matrice des prédécesseurs P - Divers entiers de gestion de boucles, de comptage, de désignation de sommets, ... /* initialisations */ pour i = 1 à n faire pour j = 1 à n faire si i ≠ j alors P(i, j) = 0 D(i, j) = ∞ sinon P(i, j) = i D(i, j) = 0
13 /* corps de l'algorithme */ pour k = 1 à n - 1 faire pour i = 1 à k faire pour j = 1 à k faire d = D(i, j) + M(j, k+1) si d < D(i, k+1) alors D(i, k+1) = d; P(i,k+1) = j d = M(k+1, j) + D(j, i) si d < D(k+1, i) alors D(k+1, i) = d si i = j alors P(k+1, i) = k + 1 sinon P(k+1, i) = P(j, i) pour i = 1 à k faire pour j = 1 à k faire d = D(i, k+1) + D(k+1, j) si d < D(i, j) alors D(i, j) = d ; P(i, j) = P(k+1, j) Estimation des coûts (complexités) En espac e ce t algorithme est en O(n2) (m atrices d'adjacence du graphe, des plus courtes distances et des prédécesseurs) En temps il est en O(n3) (car pour k variant de 1 à n - 1, i et j varient de 1 à k) Remarquons que la stratégie sous jacente à l'algorithme de DANTZIG est du type Programmation Dynamique, voir suite du cours, car il résout le problème global à partir de solutions de sous problèmes de tailles croissantes Quelques questions supplémentaires • L'algorithme de DANTZIG résout (P2) pour t oute valuation, comment peut-on l e modifier pour tester s'il existe un circuit absorbant ? • Ecrire un algorithme permettant de construire effectivement, quand il existe et à partir de la matrice P, un PC2 entre deux sommets fixés i et j, puis un algorithme construisant le graphe des PC2 • Quelles simplifications peut-on apport er à l'algorithme lorsque le graphe est non orienté ? Comment est alors D ?
14 (2) Algorithme de FLOYD Nous présentons maintenant rapidement l'algorithme de FLOYD dont certains détails sont laissés en exercice Formellement, l'algorithme considère une suite de matrices n.n : F0, F1, ..., Fn, définies pour tous les couples de sommets (x, y) de X par : F0 (x, y) = M(x, y) si xy ∈ U, ∞ sinon, et F0 (x, x) = 0 Fk (x, y) = longueur d'un PC 2 rel iant x à y dans G dont le s s ommets intermédiaires sont dans {1, 2, ..., k} ou ∞ si un tel chemin n'existe pas Remarquons que Fk (x, x) sera la longueur minimale d'un circuit passant par x et n'utilisant que des sommets de {1, 2, ..., k} ∪ {x}, si un tel circuit existe Nous avons alors : Propriété Fk (x, y) = min { Fk-1 (x, y), Fk-1 (x, k) + Fk-1 (k, y) } Principe de l'algorithme Partant de F = F 0, qui correspond en fait à M, la matrice du graphe, on calcule successivement F = F1, F = F2, ... jusqu'à F = Fn qui est la matrice des distances cherchées À chaque étape, par le test " Fk (x, x) < 0 ? », on peut détecter l'existence d'un circuit absorbant et arrêter l'algorithme La preuve de cet algorithme est immédiate par définition des matrices Fk et d'après la propriété mentionnée Exercice • Prouver la propriét é précédente et préciser comment évolue P, la matrice des prédécesseurs suivant les cas • Appliquer l'algorithme à l'exemple choisi • Donner une écriture détaillée de l'algorithme • Estimer ses complexités en espace et en temps
quotesdbs_dbs20.pdfusesText_26
[PDF] Plus court chemin dans un graphe - mediaeduscoleducationfr