Résolvez la tâche de trouver le chemin le plus court de l'algorithme Daekstra.
Trouvez le chemin le plus court de X0 à X7. Le nombre est défini par les éléments de la matrice de coût
Construire ce graphique 
Commençons par l'élément X0 et nous l'attribuons une balise 0, considérons tous ses voisins, car Il n'y a toujours pas de note, vous leur attribuez les longueurs correspondantes: 
Tous les voisins X0 sont considérés, nous le marquons et allons au sommet de X1. Ses voisins X0, X2, X4, mais X0 marqués, ne le considèrent pas. Pour x2: 
, Laissez l'étiquette.
Pour x4: 
Remplacer l'étiquette. Tous les voisins du sommet X1 sont considérés, nous le marquons 
Aller au sommet de x2. Ses voisins X0, X1, X3, X4, X5, X6, mais X0, X1 sont marqués, ne les considèrent pas.
Pour x3: 
, Laissez l'étiquette.
Pour x5: 
Remplacer l'étiquette.
Pour x4: 
, Laissez l'étiquette.
Pour x6: 
Remplacer l'étiquette.
Tous les voisins du sommet des X2 sont pris en compte, nous le marquons. 
Aller au sommet x3. Ses voisins X0, X2, X6, mais X0, X2 sont marqués, ne les considèrent pas.
Pour x6: 
, Laissez l'étiquette.
Tous les voisins du sommet des X3 sont considérés, nous le marquons. 
Aller au sommet de x4. Ses voisins X1, X2, X5, X7, mais X1, X2 sont marqués, ne les considèrent pas.
Pour x5: 
Remplacer l'étiquette.
Pour x7: 
Remplacer l'étiquette.
Tous les voisins du sommet du X4 sont considérés, nous le marquons. 
Aller au sommet de x5. Ses voisins X2, X4, X6, X7, mais X2, X4 sont marqués, ne les considèrent pas.
Pour x6: 
, Laissez l'étiquette.
Pour x7: 
, Laissez l'étiquette.
Tous les voisins du sommet du X5 sont considérés, nous le marquons. 
Aller au sommet de x6. Ses voisins X2, X3, X5, X7, mais X2, X3, X5 sont marqués, ne les considèrent pas.
Pour x7: 
, Laissez l'étiquette.
Tous les sommets du sommet des X6 sont pris en compte, nous le marquons. Et nous avons étiqueté le X7 restant, tous les sommets sont pris en compte. 
Conclusion: Le chemin le plus court de leur x0 en X7 a une longueur de 101, ce chemin: x7-x4-x1-x0.
L'algorithme Daekstra (algorithme anglais de Dijkstra) est un algorithme au graphique, inventé par le scientifique néerlandais Edsger Dikstroy en 1959. Trouve les chemins les plus courts de l'un des sommets du graphique à tous les autres. L'algorithme fonctionne seulement pour les graphiques sans poids négatif radim.
Considérez l'exécution de l'algorithme sur l'exemple du graphique indiqué sur la figure.
Devant qu'il soit nécessaire de trouver la distance la plus courte du 1er sommet à tous les autres.
Les cercles indiquent les sommets, les lignes - le chemin entre eux (Nombre RIBRI). Dans les cercles marqués, les nombres des sommets, sur les bords sont indiqués par leur "prix" - la longueur du chemin. À côté de chaque sommet du rouge marqué l'étiquette - la longueur du chemin le plus court vers ce sommet du sommet 1.
Premier pas. Considérez l'étape de l'algorithme de Deiquistra pour notre exemple. L'étiquette minimale a un sommet 1. Ses voisins sont des sommets 2, 3 et 6.
Le premier à son tour des sommets du sommet 1 - Top 2, car la longueur du chemin d'accès est minimale. La longueur du trajet dans le sommet à travers le sommet 1 est égale à la somme de la valeur de la balise du sommet 1 et de la longueur du bord provenant du 1er à 2, c'est-à-dire 0 + 7 \u003d 7. Il est Moins que la balise actuelle du sommet 2, l'infini, la nouvelle étiquette est donc 2e les sommets sont 7.
Une opération similaire se fait avec deux autres voisins du 1er sommet - le 3ème et 6ème.
Tous les sommets du sommet 1 sont vérifiés. La distance minimale actuelle du sommet 1 est considérée comme définitive et la révision n'est pas soumise à (ce qu'elle a vraiment prouvé E. Dyakstra pour la première fois). Je le traverse hors du graphique pour noter que ce haut est visité.
Deuxième étape. L'étape de l'algorithme est répétée. Nous trouvons à nouveau le "le plus proche" des sommets involontaires. Ceci est un sommet 2 étiqueté 7.
Réessayez à nouveau pour réduire les marques des voisins du sommet sélectionné, essayant de les passer à travers le 2e sommet. Les voisins des sommets 2 sont des sommets 1, 3 et 4.
Le premier (dans l'ordre) Un voisin du sommet 2 est le sommet 1. mais il est déjà visité, donc nous ne faisons rien avec le 1er sommet.
Le prochain voisin du sommet 2 est Vertex 3, car il a une étiquette minimale des sommets marqués comme non visités. Si vous y allez dans 2, la longueur d'un tel chemin sera égale à 17 (7 + 10 \u003d 17). Mais la marque actuelle du troisième sommet est de 9, et cela est inférieur à 17, de sorte que l'étiquette ne change pas.
Un autre voisin du sommet 2 est le sommet 4. Si vous y allez à travers le 2e, la longueur d'un tel chemin sera égale à la somme de la distance la plus courte du 2e sommet et la distance entre les sommets 2 et 4 , c'est-à-dire 22 (7 + 15 \u003d 22). Depuis 22.<, устанавливаем метку вершины 4 равной 22.
Tous les sommets du sommet 2 sont visualisés, gèlent la distance de la distance et nous le marquons comme visités.
Troisième étape. Nous répétons l'étape de l'algorithme en sélectionnant le sommet 3. Après son "traitement", nous obtenons les résultats:
Prochaines étapes. Nous répétons l'étape de l'algorithme pour les sommets restants. Ce seront des sommets 6, 4 et 5, respectivement, ordre.
Achèvement de l'exécution de l'algorithme. L'algorithme termine le travail lorsque vous ne pouvez traiter aucun sommet. Dans cet exemple, tous les sommets sont noyés, mais il sera confondu de croire que ce sera donc dans un exemple - certains sommets peuvent rester non couplés s'il est impossible de l'obtenir, c'est-à-dire si le compte n'est pas concluant. Le résultat de l'algorithme est visible dans la dernière figure: le chemin le plus court du sommet 1 au 2e est de 7, au 3ème - 9, jusqu'au 4ème - 20, au 5ème - 20, au 6ème - 11.
Mise en œuvre de l'algorithme dans divers langages de programmation:
C ++.
#Include "stdafx.h" #includePascal
Programme dijkstraalgorithme; Utilise CRT; const v \u003d 6; inf \u003d 100000; Type vektor \u003d tableau d'entier; Var départ: entier; Const gr: matrice d'entier \u003d ((0, 1, 4, 0, 2, 0), (0, 0, 0, 9, 0, 0), (4, 0, 0, 7, 0, 0), (0, 9, 7, 0, 0, 2), (0, 0, 0, 0, 0, 8), (0, 0, 0, 0, 0, 0)); (Algorithme de dikstra) Procédure Dijkstra (GR: Array d'entier; ST: Entier); Var cant, index, i, u, m, min: entier; Distance: Vektor; Visité: Array de Boolean; Commencer m: \u003d st; Car je: \u003d 1 à v commence la distance [i]: \u003d inf; Visité [i]: \u003d faux; finir; Distance: 0; Pour le compte: \u003d 1 à V-1 commence Min: \u003d Inf; Pour i: \u003d 1 à v faire si (pas visité [i]) et (distance [i]<=min) then begin min:=distance[i]; index:=i; end; u:=index; visited[u]:=true; for i:=1 to V do if (not visited[i]) and (GR<>0) et (distance [u]<>inf) et (distance [u] + grJava.
Importer java.io.bufferedreader; Import java.io.ioException; Import java.io.inputtreamreader; Import java.io.printwritre; import java.util.arraylist; Import java.util.arrays; Import java.util.stringtensizer; Solution de classe publique (Privé Static Inf \u003d Integer.Max_Value / 2; Nombre de sommets Int N; // Nombre de sommets dans l'intégrateur Orgraph Int M; // Nombre d'arcs dans l'arraylist privé orgraphiqueUne autre option:
Import java.io. *; Import java.util. *; Classe publique Dijkstra (graphique final statique privé \u003d (nouveau graphique.dge ("A", "B", 7), Nouveau graphique.dge ("A", "C", 9), nouveau graphique.dge ( "A", "F", 14), Nouveau graph.dge ("B", "C", 10), Nouveau graphge.dge ("B", "D", 15), Nouveau graphged ("C "," D ", 11), Nouveau graphique.dge (" C "," F ", 2), nouveau graphique.dge (" D "," E ", 6), nouveau graphique.dge (" E ", "F", 9),); String Finale statique privé Start \u003d "A"; String final statique privé End \u003d "E"; Public statique vide (String args) (graphique g \u003d nouveau graphique); g.dijkstra (départ ); G.printpath; //g.prinTallPaths ();)) Graphique de classe (carte finale privée
C.
#Inclure.Php.
$ bord, "coût" \u003d\u003e $ bord); $ voisins [$ Edge] \u003d tableau ("fin" \u003d\u003e $ bord, "coût" \u003d\u003e $ bord); ) $ sommets \u003d array_unique ($ sommets); foreach ($ sommets en tant que sommet $) ($ distex [$ sommet] \u003d inf; $ précédent [$ sommet] \u003d null;) $ dist [$ source] \u003d 0; $ Q \u003d $ sommets; tandis que (comptage ($ q)\u003e 0) (// todo - trouver un moyen plus rapide d'obtenir un minimum de $ min \u003d Inf; foreach ($ q comme $ sommet) (si ($ DISTEEX]< $min) { $min = $dist[$vertex]; $u = $vertex; } } $Q = array_diff($Q, array($u)); if ($dist[$u] == INF or $u == $target) { break; } if (isset($neighbours[$u])) { foreach ($neighbours[$u] as $arr) { $alt = $dist[$u] + $arr["cost"]; if ($alt < $dist[$arr["end"]]) { $dist[$arr["end"]] = $alt; $previous[$arr["end"]] = $u; } } } } $path = array(); $u = $target; while (isset($previous[$u])) { array_unshift($path, $u); $u = $previous[$u]; } array_unshift($path, $u); return $path; } $graph_array = array(array("a", "b", 7), array("a", "c", 9), array("a", "f", 14), array("b", "c", 10), array("b", "d", 15), array("c", "d", 11), array("c", "f", 2), array("d", "e", 6), array("e", "f", 9)); $path = dijkstra($graph_array, "a", "e"); echo "path is: ".implode(", ", $path)."\n";
Python
Des collections Importation NamedTuple, File d'attente de PPrint Importation PPRTT en tant que PP Inf \u003d Float ("Edge", "Démarrer, fin de classe, coût") Graph (): def __init __ (auto, bords): auto .dges \u003d Edges2 \u003d Soi. VERTIS \u003d SET (SUM (SUM (FOR EDÉS2),)) DEF DIJKSTRATA (SOFT, SOURCE, DESTS): Affirmez la source dans Self.vertices dist \u003d (sommet: Inf pour sommet dans self.vertices) Précédent \u003d (sommet: Aucun pour sommet dans self.vertices) dist \u003d 0 q \u003d self.vertices.copy () voisins \u003d (sommet: défini () pour vertex dans self.vertices) Pour commencer, fin, coût de soi. bords: voisins ((fin , Coût)) #pp (voisins) tandis que q: u \u003d min (q, clé \u003d lambda sommetex: dist) q.Retirer (u) si dist [u] \u003d\u003d Inf ou u \u003d \u003d Dest: pause pour v, coût dans voisins [u]: alt \u003d dist [u] + coût si alt< dist[v]: # Relax (u,v,a)
dist[v] = alt
previous[v] = u
#pp(previous)
s, u = deque(), dest
while previous[u]:
s.pushleft(u)
u = previous[u]
s.pushleft(u)
return s
graph = Graph([("a", "b", 7), ("a", "c", 9), ("a", "f", 14), ("b", "c", 10),
("b", "d", 15), ("c", "d", 11), ("c", "f", 2), ("d", "e", 6),
("e", "f", 9)])
pp(graph.dijkstra("a", "e"))
Output:
["a", "c", "d", "e"]
Parmi les nombreux algorithmes de la recherche des itinéraires les plus courtes sur la colonne, à Habré, je n'ai trouvé qu'une description de l'algorithme Floyd Warshlla. Cet algorithme trouve le chemin le plus court entre tous les sommets du graphique et de leur longueur. Dans cet article, je vais décrire le principe de fonctionnement de l'algorithme Daekstra, qui trouve des itinéraires optimaux et leur longueur entre un sommet particulier (source) et tous les autres sommets du graphique. L'inconvénient de cet algorithme est qu'il fonctionnera de manière incorrecte si le graphique a un arc de poids négatif.
Par exemple, prenez un tel nombre orienté g:
Nous pouvons imaginer ce graphique sous la forme d'une matrice avec:
Prenez un sommet 1. Cela signifie que nous rechercherons les itinéraires les plus courts du top 1 des sommets 2, 3, 4 et 5.
Cet algorithme étape par étape passe par tous les sommets du graphique et les attribue aux étiquettes, qui sont une distance minimale connue du haut de la source à un sommet particulier. Considérez cet algorithme sur l'exemple.
Nous attribuons le 1er haut de l'étiquette égale à 0, car ce sommet est une source. Le reste des sommets assignez des balises égales à l'infini.
Ensuite, choisissez un tel sommet W, qui comporte une étiquette minimale (il s'agit désormais d'un sommet 1) et de considérer tous les sommets dans lesquels le sommet W est un chemin qui ne contient pas de sommet. Chacun des sommets considérés que nous attribuons une étiquette égale à la somme de la valeur marquée et la longueur du trajet de W au sommet à l'étude, mais uniquement si la quantité résultante est inférieure à la valeur de la balise précédente. Si le montant n'est pas moins de moins, nous laissons l'étiquette précédente inchangée.
Après avoir examiné tous les sommets dans lesquels il y a un chemin droit de W, le sommet w Nous marquons à la fois visité et choisissez de ne pas encore visiter de telle valeur minimale, ce sera le sommet suivant W. Dans ce cas, Ceci est un sommet 2 ou 5. S'il y a plusieurs sommets avec les mêmes tags, peu importe laquelle que nous choisissons comme W.
Nous choisirons un sommet 2. mais il n'y a pas un seul chemin sortant, nous célébrons donc immédiatement ce sommet comme visité et aller au sommet suivant avec une étiquette minimale. Cette fois, seul le sommet 5 a une étiquette minimale. Considérons tous les sommets dans lesquels il y a des chemins directs sur 5, mais qui ne sont pas encore marqués comme visités. Encore une fois, nous trouvons la somme du sommet du sommet W et du poids des côtes de W au sommet actuel, et si cette quantité est inférieure à la balise précédente, nous remplaçons la valeur de l'étiquette au montant résultant.
Basé sur la photo, nous pouvons voir que les étiquettes des 3ème et 4e sommets étaient inférieures à celles, c'est-à-dire une route plus courte de ces sommets du haut de la source. Ensuite, nous notons le 5ème sommet comme visité et sélectionnez le sommet suivant, qui a une étiquette minimale. Nous répétons toutes les étapes ci-dessus jusqu'à ce qu'il y ait des pics inversés.
Après avoir effectué toutes les actions, nous obtenons ce résultat:
Il y a aussi un vecteur P sur la base de laquelle vous pouvez créer les itinéraires les plus courts. Par le nombre d'éléments, ce vecteur est égal au nombre de sommets de la colonne, chaque élément contient le dernier sommet intermédiaire sur le chemin le plus court entre la source supérieure et le sommet final. Au début de l'algorithme, tous les éléments du vecteur p sont égaux au sommet de la source (dans notre cas p \u003d (1, 1, 1, 1, 1)). Ensuite, au stade de la recalcul, la valeur de l'étiquette du sommet à l'étude, si la balise à l'étude est modifiée en une plus petite, dans le tableau de R, nous écrivons la valeur du sommet actuel W. Par exemple: le 3ème Vertex avait une étiquette avec la valeur "30", quand w \u003d 1. Ensuite, lorsque W \u003d 5, la balise 3-elle a changé en "20", nous écrirons donc la valeur dans le vecteur p - p \u003d 5. De plus, lorsque W \u003d 5, la valeur de l'étiquette a changé dans le 4ème sommet (c'était "50", il est devenu "40"), cela signifie que vous devez affecter un 4ème élément du vecteur p \u003d 5. En conséquence, nous obtenons le vecteur p \u003d (1, 1, 5, 5, 1).
Sachant que dans chaque élément du vecteur p enregistré le dernier sommet intermédiaire sur le chemin entre la source et le sommet ultime, nous pouvons obtenir l'itinéraire le plus court lui-même.
le plus court chemin Aujourd'hui, il s'agit d'une tâche vitale et est utilisée presque partout, allant de la recherche de la route optimale entre deux objets sur le sol (par exemple, le chemin le plus court de la maison à l'université), dans les systèmes de pilote automatique, pour trouver la route optimale pendant le transport, Passage d'informations de commutation dans les réseaux et T.P.Le chemin le plus court est considéré à l'aide d'un certain objet mathématique appelé graphique. Rechercher le plus court chemin Il est effectué entre deux sommets spécifiés dans le graphique. Le résultat est le chemin, c'est-à-dire la séquence de sommets et de nervures, incident aux deux sommets voisins et sa longueur.
Considérer trois les plus algorithme efficace Pose le plus court chemin:
- algorithme Daekstra;
- Algorithme Floyd;
- algorithmes sur-né.
Ces algorithmes sont facilement effectués avec un petit nombre de sommets dans le graphique. Avec une augmentation de leur nombre de tâches de recherche le plus court chemin Compléter.
Algorithme Daekstra
Cet algorithme est un algorithme sur les graphiques, qui a été inventé par le scientifique néerlandais E. Dyaktroy en 1959. L'algorithme trouve la distance la plus courte de l'un des sommets du graphique à tous les autres et ne fonctionne que pour les graphiques sans nervures de poids négatif.
Chaque sommet est attribué au poids - il s'agit du poids du chemin du sommet initial à celui-ci. En outre, chaque sommet peut être mis en surbrillance. Si le sommet est mis en surbrillance, le chemin du sommet au sommet initial le plus court, sinon, puis temporaire. Venir par le graphique, l'algorithme considère l'itinéraire de chaque sommet et, s'il s'avère être le plus court, met en évidence le sommet. Le poids de ce sommet est le poids du chemin. Pour tous les voisins de ce sommet, l'algorithme calcule également le poids, sans aucune circonstance qui ne les utilise en aucun cas. L'algorithme termine son travail, atteignant le sommet final et pesant le plus court chemin Le poids du sommet final devient.
Algorithme Daekstra
Étape 1. Pour tous les sommets, à l'exception du premier, le poids est attribué à une infinité égale et le premier sommet est 0.
Étape 2. Tous les sommets ne sont pas mis en évidence.
Étape 3. Le premier sommet est déclaré actuel.
Étape 4. Le poids de tous les sommets non asquidés est traduit par la formule: le poids du sommet non reciné est le nombre minimum de poids ancien de ce sommet, la quantité du poids du sommet actuel et le poids du bord reliant le sommet actuel avec l'indéfidant.
Étape 5. Parmi les pics non rectosés est un haut avec un poids minimal. Si cela ne se trouve pas, c'est-à-dire que le poids de tous les sommets est égal à l'infini, l'itinéraire n'existe pas. Par conséquent, la sortie. Sinon, le courant est le sommet résultant. Il est alloué.
Étape 6. Si le sommet actuel s'avère être la finale, le chemin est trouvé et son poids est le poids du sommet final.
Étape 7. Allez à l'étape 4.
Dans la mise en œuvre du logiciel algorithme Daekstra Nous construirons un ensemble de sommets S pour lesquels les chemins les plus courts du sommet initial sont déjà connus. À chaque étape de l'ensemble S, le même sommet est ajouté, la distance entre le sommet initial est inférieure à celle des autres sommets restants. Dans ce cas, nous utiliserons la matrice D, dans laquelle les longueurs sont enregistrées chemins les plus courts Pour chaque sommet. Lorsque l'ensemble S contient tous les sommets du graphique, la matrice D contiendra des longueurs chemins les plus courts Du sommet initial à chaque sommet.
En plus des matrices spécifiées, nous utiliserons la matrice C de C, où l'élément C est la longueur des bords (I, J), s'il n'y a pas de nervures, la longueur est comptabilisée sur une infinité égale, c'est-à-dire plus que toute longueur de la côte réelle. En fait matrice c est matrice de voiledans lequel tous les éléments zéro sont remplacés par l'infini.
Déterminer le lui-même
À la fin du tournoi de la réveillon du nouvel an, le sponsor a décidé d'envoyer des cadeaux de $ M $ par courrier. Connaissant le nombre de participants N $ N $ et le délai de livraison du courrier entre certains départements «Ukrpochta», trouvez, après quel est le moment minimum le dernier des gagnants recevra son prix.
Des données d'entrée
La première ligne contient des numéros de 3 $ $: le nombre de participants du tournoi N $ N $, le nombre de prix du sponsor $ M $ et le nombre de délais de livraison temporaires connus entre certains des bureaux $ K $. Dans la ligne suivante, les chiffres des participants sont devenus des prix sont indiqués.
Vient ensuite $ K $ 1 $ Numéros de dollars chacun avec des informations sur les délais de livraison connus entre certains des compartiments au format: $ A $ B $ B $ $ T $, où $ A $ et $ B $ de numéro de compartiment $, $ T $ $ (0 \\ Leqslant t \\ Leqslant 365) - Délai de livraison de courrier entre eux. Dans la dernière ligne, il y a un numéro unique - le numéro du bureau de poste, à partir duquel le sponsor enverra des prix. On sait que 1 \\ Leqslant N, M, A, B \\ Leqslant 365 $.
Production
Si tous les prix sont livrés aux participants - se retirer dans la première ligne "Le bon sponsor!", Et dans la prochaine fois, après quoi le dernier des gagnants recevra votre prix. Si au moins un des participants peut obtenir un prix - se retirer dans la seule ligne ", il n'est pas faute de sponsor ...". Phrases de sortie sans guillemets.
Tests
| № | Des données d'entrée | Production |
| 1. | 3 2 2 2 3 1 2 3 2 3 4 1 |
Le bon sponsor! 7 |
| 2. | 5 1 4 5 1 3 2 2 3 3 4 2 5 4 5 6 1 |
Le bon sponsor! 16 |
| 3. | 7 2 6 1 3 1 3 2 2 4 32 4 5 94 3 1 0 6 2 4 7 2 3 7 |
Ce n'est pas une faute du sponsor ... |
| 4. | 5 2 6 1 2 3 1 1 3 4 2 2 4 3 5 1 4 4 5 5 2 3 7 2 |
Le bon sponsor! 6 |
