Méthode Daekstra Trouver le chemin le plus court. Graphiques. Trouver la distance la plus courte entre les deux sommets en utilisant l'algorithme de Deiquistra. Schéma de l'algorithme séquentiel

L'algorithme Daekstra est un algorithme sur les graphiques, ce qui trouve le chemin le plus court entre les deux sommets du graphique avec des longueurs non négatives de l'arc. C'est aussi souvent une tâche de calcul du chemin le plus court de ce sommet à tous les autres. L'algorithme est largement utilisé dans la programmation, par exemple, il est utilisé par les protocoles de routage.

La description

L'entrée d'algorithme est donnée un graphique orienté pondéré avec des arcs de poids non négatifs. La sortie est un ensemble de chemins les plus courts de ce sommet à d'autres.

Au début, la distance pour le sommet initial est supposée être nulle et les distances à tous les autres sont comprises infinies. Un tableau de drapeaux indiquant si le sommet est passé, rempli de zéros. Ensuite, à chaque étape du cycle, un sommet d'une distance minimale à l'initiale et à l'indicateur égal à zéro est recherché. Pour cela, le drapeau est installé et tous les sommets voisins sont vérifiés. Si la distance précédente du sommet source est auparavant vérifiée par rapport à la quantité de distance sur le sommet actuel et la longueur de la nervure à partir du sommet vérifié, la distance au sommet testé équivaut à la distance au courant + bord. du courant à la vérification actuelle. Le cycle est terminé lorsque les drapeaux de tous les sommets deviennent égaux à 1, ou lorsque la distance à tous les sommets avec drapeau 0 est infinie. Le dernier cas est possible alors et seulement si le nombre est intolérant.

Algorithme Daekstra en pseudocode

Entrée: DE : Matrice de journal arc réel; S est un sommet à partir duquel le chemin le plus court et T est un sommet à qui il cherche.

Sortie: V\u003e Tableau de réel; et n: tableau de 0..r. Si le sommet v. Se trouve dans le chemin le plus court de s. à t, cette LA TÉLÉ]- Longueur du chemin le plus court de s. à y; H [y] - Haut, directement précédent w. Dans le chemin le plus court.

H est un tableau dans lequel le sommet N correspond au sommet M, le précédent sur le chemin de n de s.

T est un tableau dans lequel le sommet N correspond à la distance de celui-ci à l'art.

X est un tableau dans lequel le sommet N correspond à 1 si le chemin est connu, et 0, sinon.

initialisation des tableaux:

pour v. de 1 à. r fais.

T [v.]: = ∞ (Le chemin le plus court est inconnu)

X [V]: \u003d 0 (tous les sommets ne sont pas marqués)

H [S]: \u003d 0 ( s. rien ne précède)

T [s]: \u003d 0 (le chemin le plus court a une longueur de 0 ...)

X [S]: \u003d 1 (... et il est connu) v. : = s. (sommet actuel)

M: (Marques de mise à jour)

pour et ∈ G ( et) fais

si X [et] = 0 & T [et]> LA TÉLÉ] + C. Puis.

T [et]: = LA TÉLÉ] + C. (un chemin plus court de s. dans et à travers v. }

H [u]:= v. (Souviens toi)

m.: = ∞

v. : = 0

(Recherchez la fin du chemin le plus court)

pour et de 1 à. p. fais.

si X [u] = 0 & T [u]< t. Puis.

v:= u.;

m:= T [u] (Haut v. termine le chemin le plus court de s.

si v. = 0 alors.

arrêter (pas de chemin de s. dans t.) Fin si

si v.= t. Puis.

arrêter (le chemin le plus court de s. dans t.) Fin si

X [v]: \u003d 1 (le chemin le plus court de s. dans v. ) Aller à. M.

Justification

Pour prouver l'exactitude de l'algorithme de Daekstra, il suffit de noter qu'avec chaque performance du corps du cycle, qui commence l'étiquette M, comme v.un sommet est utilisé pour lequel le chemin le plus court du haut est connu. s.En d'autres termes, si x [v] \u003d 1, alors t [v] \u003d d (s, v) , Et tous les sommets sur le chemin (S, V), déterminé par le vecteur N, ont la même propriété, c'est-à-dire

VU T [et] \u003d 1 \u003d\u003e T [et] \u003d D (S, U) & T] \u003d 1.

Vraiment (par induction), première fois comme v. Le sommet S est utilisé pour lequel le chemin le plus court est vide et a une longueur de 0 (des chemins non vides ne peuvent pas être plus courts, car la longueur des arcs ne sont pas négatives). Soit t [u] \u003d d (s, u) pour tous les sommets précédemment marqués et. Considérez le sommet nouvellement marqué v.qui est choisi parmi la condition T [V] \u003d min t [et]. Notez que si le chemin est connu à travers les sommets marqués, il est également connu pour le chemin le plus court. Supposons (sinon), que T [V]\u003e D (S, V), c'est-à-dire le chemin qui a été trouvé menant de s.dans v,n'est pas le plus court. Ensuite, il devrait y avoir des sommets non qualifiés sur ce chemin. Considérez le premier sommet w.sur ce chemin, tel que t [w] = 0. IIM: T [W] = d (S, W) ⩽D (S\u003e V)< Т[v],что противоречит выбору вершины u.

Difficulté temporaire

La complexité de l'algorithme Daekstra dépend du procédé de recherche non visitée par le haut avec une distance minimale à la méthode initiale et de stockage de pluralité de sommets et de procédés de mise à jour des étiquettes. Soit n le nombre de sommets et à travers m - le nombre d'arêtes dans la colonne. Ensuite, dans le cas le plus simple, lorsque tous les sommets définis sont visualisés pour rechercher les sommets avec une distance minimale au sommet initial et une matrice est utilisée pour stocker les distances, l'heure du fonctionnement de l'algorithme - O (n 2). Le cycle principal est effectué sur n Times, dans chacun d'eux, le minimum est dépensé sur les opérations n. Le nombre d'opérations est dépensé sur les cycles le long des voisins de chaque visite du sommet, le nombre de rober m (car chaque bord se trouve dans ces cycles doucement deux fois et nécessite un nombre constant d'opérations). Ainsi, le temps de fonctionnement global de l'algorithme O (N 2 + m), mais depuis M est inférieur à N (N-1), il s'avère finalement (N 2).

Pour les graphiques raréfiés (c'est-à-dire que, tel pour lequel M est beaucoup moins que N²) Les sommets inversés peuvent être stockés dans un tas binaire et une clé pour utiliser des distances. Étant donné que le cycle est effectué environ N fois et le nombre de relaxation (changements d'étiquettes) n'est pas supérieur à M, l'heure du fonctionnement d'une telle mise en œuvre - O (nlogn + mlogn)

Exemple

Calcul des distances du sommet 1 pour les sommets passables:

Avant chaque zone de la ville (si vous ne pouvez vous déplacer que sur les routes).

Option 2. Il y a des vols entre les villes du monde, pour chaque coût célèbre. Le coût du vol de A à B peut ne pas être égal au coût du vol de B à A. Trouvez la voie du coût minimum (éventuellement avec des transferts) de Copenhague à Barnaul.

Définition formelle

Exemple

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.

Mise en œuvre dans les langages de programmation

Performance dans la langue C (SI)

#Define taille 6 #define inf 1000000000 int A [Taille] [Taille] \u003d ((INF, 5, INF, INF, INF, INF), (1, 2, 3, 4, 5, 6), // Chemins matricielles (1, 2, 3, 4, 5, 6), (1, 2, 3, 4, 5, 6), // index horizontal du point { 1 , 2 , 3 , 4 , 5 , 6 },{ 1 , 2 , 3 , 4 , 5 , 6 }}; // Vertical à point, valeur - poids Int d [taille]; // matrice des chemins les plus courts trouvés, index - sommets du graphique vide Deikstra () (int V [Taille]; // Array d'étiquettes int Temp, i; int minindex, min; pour (i \u003d 0; i; i< SIZE ; i ++ ) { d [ i ] = INF ; // le tableau des chemins est initialisé Infinity v [i] \u003d 1; ) D [0] \u003d 0; fais ( // exécution de l'algorithme minindex \u003d inf; inf; Min \u003d inf; pour (i \u003d 0; je< SIZE ; i ++ ) { if ((v [ i ] == 1 ) && (d [ i ] < min )) { min = d [ i ]; minindex = i ; } } if (minindex != INF ) { for (i = 0 ; i < SIZE ; i ++ ) { if (a [ minindex ][ i ] > 0) (temp \u003d min + un [minindex] [i]; si (temp< d [ i ]) d [ i ] = temp ; } } v [ minindex ] = 0 ; } } while (minindex < INF ); }

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

5.4.3. Le défi du chemin le plus court et de l'algorithme de Daekster de sa décision

Laisser l'orgraf G.(V., E.), avec chaque arc de qui est mis en ligne avec le nombre
appelé arc long.

Définition. Lena Le chemin est appelé la somme des longueurs d'arc qui composent ce chemin. La tâche du chemin le plus courtmet comme ça.

Option 1. Trouvez les longueurs des chemins les plus courts (façons de longueur minimale) et les chemins eux-mêmes du sommet fixe s. à tous les autres sommets du graphique.

Option 2. Trouvez les longueurs des chemins les plus courts et des chemins eux-mêmes entre toutes les paires des sommets de ce graphique.

S'il y a des arcs négatifs dans la colonne, la tâche peut ne pas avoir de solutions (perdra la signification). Cela est dû au fait que le contour de la longueur négative peut être présent dans la colonne. La présence de circuits de longueur négative signifie que la longueur du chemin peut être faite égale
. Et s'il n'y a pas de circuits de longueur négative, les chemins les plus courts existent et tout chemin le plus court est une chaîne simple.

Notez que si le chemin le plus court existe, alors tout est, c'est aussi le chemin le plus court entre les sommets respectifs.

Algorithme Daekstra résolvant le problème du chemin le plus court.

L'algorithme fonctionne avec des arcs de longueur positive et définit les chemins les plus courts du sommet fixe s. à tous les autres sommets du graphique. Dénote ces sommets v. 1 , v. 2 ,…, v. n. .

Définition. Appelons le sommet u. se tenant plus proche du sommet s.que top v.Si la longueur du chemin le plus court de s. avant que u. moins que la longueur du chemin le plus court de s. avant que v.. Nous dirons que les sommets u. et v. Égal Du haut s.Si les longueurs des chemins les plus courtes de s. avant que u. et de s. avant que v. correspondre.

L'algorithme Daekstra simplifie toujours les sommets du graphique dans le sens de la proximité du sommet. s. et en fonction des principes de base suivants.

Si les longueurs de l'arc sont des nombres positifs, alors

k. à proximité s. top - elle-même. Longueur du chemin le plus court de s. avant que s. égal à 0;

k. à proximité s. sommet s., Mensonges de s. À la distance d'un arc  le plus court des arches quittant le sommet s.;

tout haut intermédiaire du chemin le plus court de s. À certains sommets v. Se rapproche de K. s.que le sommet final v.;

le chemin le plus court vers le prochain sommet commandé ne peut transmettre que des pics déjà commandés.

Laissez l'algorithme déjà commandé les sommets v. 1 , v. 2 … v. k. . Dénoter
,
La longueur du chemin le plus court vers le haut v. jE. .

Considérez tous les arcs du graphique source qui commencent dans l'un des sommets de l'ensemble.
Et se termine dans un autre sommet non ordonné. Pour chacun de ces arcs, par exemple
, Je calcule la somme
. Ce montant est égal à la longueur du chemin de s. dans y.dans lequel le sommet v. jE. Il y a un avant-sommete et le chemin de s. dans v. jE. - le plus court de tous les chemins de connexion s. et v. jE. .

C'est la longueur la plus définie de tous les chemins de s. pas encore commandé des pics dans lesquels seuls les sommets sont des sommets intermédiaires sont k. K. à proximité s.. Laissez le plus court de ces chemins se termine sur le dessus w.. Puis w. et est
Par proximité de k. s. sommet.

Les actions techniquement sur l'algorithme Daekstra sont effectuées à l'aide de l'appareil de marquage de sommet. Tag Verth v. dénote comment
. Toute étiquette est un nombre égal à la longueur de certains chemins de s. avant que v.. Les balises sont divisées en temporaire et constante. À chaque étape, une seule étiquette devient constante. Cela signifie que sa valeur est égale à la longueur du chemin le plus court vers le sommet correspondant et ce sommet lui-même est commandé. Le nombre de vertex ordonné est noté par la lettre r.

Description de l'algorithme.

Étape 1. (Installation initiale). Mettre
Et considérez cette constante d'étiquette. Mettre
,
Et considérez ces marques temporaires. Mettre
.

Étape 2. (Étape partagée). Il répète n. une fois que tous les sommets du graphique sont commandés.

Recalculer une marque temporaire
Tous les sommets désordonnés v. jE. qui comprend un arc qui quitte le haut r, Par règle

Sélectionnez le haut avec une étiquette de temps minimum. S'il y a plusieurs sommets, choisissez-le.

Laisser être w.- Haut avec une étiquette de temps minimum. Faire une étiquette
constant et mettre
.

Les étapes de l'algorithme Daekstra sont bien établies dans la table, dont chaque colonne correspond au sommet du graphique. Les rangées de la table correspondent à la répétition de l'étape globale.

Exemple. Pour graphique sur la Fig. 4. Trouvez les chemins les plus courts des sommets
à tous les autres sommets du graphique. Les côtes signifient deux arcs multidirectionaux de la même longueur.

Décision. Dans l'onglet. 1 Tags Vertex enregistrés à chaque étape. Les balises permanentes sont marquées de "+". Décrivons en détail comment les balises sont calculées.

Des arcs Vertex 1 donnent sur les sommets 2, 5, 6. Rappelant les étiquettes de ces sommets et remplissent la deuxième chaîne de la table.

Le haut du sommet 6 devient constant,
.

Du Vertex 6 Arcs sont toujours des sommets non ordonnés 2, 5, 8, 9. Recalculer leurs étiquettes de temps

Remplissez 3 rangées de table. Le minimum des étiquettes de temps est 3 (Top Tag 9),
.

Des arcs de sommet 9 dans des sommets encore non commandés 5, 8, 11, 12. ensuite

Remplissez la quatrième ligne de la table. Dans cette ligne, deux sommets  2 et 12 ont des étiquettes de temps minimes égales à 4. Premier ordre, par exemple, le sommet 2. Le top 12 sera ensuite commandé à l'étape suivante.

Tableau 1

Donc,
.

Du top 2, il y a des arcs dans des sommets toujours désordonnés 3, 4, 5. Rappelant des marques temporaires de ces sommets

Remplissez 5 rangées de table. Le minimum d'étiquettes de temps est de 4 (tag Vertex 12),
.

Remplissez 6 rangées de table. Le minimum d'étiquettes de temps est 5 (Top Tag 5),
.

Remplissez 7 chaîne de la table. Devenir une étiquette constante du sommet 8 (il est égal à 5),
.

Le top 11 est commandé.

Du Vertex 11 Arcs dans des sommets désordonnés 7, 10. Rappelant les traces de ces sommets de ces sommets.

Top 4 obtient une étiquette constante.

Du Vertex 4 Arcs dans des sommets non ordonnés 3, 7. Recalculer des étiquettes de temps

Organiser le sommet 3.

Remplissez 12 rangées de table. À cette étape, nous commandons le dernier sommet 8 désordonné.

Construire un arbre des chemins les plus courts.

L'arbre des chemins les plus courts est un arbre ciblé avec une racine en haut S. . Tous les chemins de cet arbre sont les plus courts pour ce graphique.

L'arborescence de chemin le plus court est basé sur la table, le haut est allumé sur le sommet dans l'ordre dans lequel ils ont reçu des balises constantes. Le premier dans l'arbre tourne sur la racine - le sommet S. .

Nous construisons l'arbre le plus court pour notre exemple.

Tout d'abord, nous allumons la racine de l'arbre - le sommet 1. Ensuite, l'arc est transformé en arbre (1,6). Le prochain a été commandé au sommet 9, la longueur du chemin le plus court qui est égale à 3. La première fois numéro 3 est apparu dans la troisième ligne, qui a été remplie de
. Par conséquent, le sommet 6 est l'avant-dernier haut du chemin le plus court du sommet 9. Nous tournons dans la longueur de l'arc bois (6.9) 1.

Le top 2 a été commandé avec la longueur du chemin le plus court égal à 4. Ce nombre est apparu pour la première fois dans la troisième ligne, qui était rempli de
. Par conséquent, le chemin le plus court du deuxième sommet passe le long de l'arc (6.2). Nous allumons l'arc (6.2) de la longueur 2.

Next a été commandé le top 12,
. La première fois numéro 4 apparaît dans la quatrième ligne, qui était remplie de
. L'arbre comprend un arc (9.12) de longueur 1. L'arborescence totale des chemins les plus courts est illustrée à la Fig. cinq.

L'algorithme de désiquiste peut avoir tort s'il y a des arcs négatifs dans la colonne. Donc, à la recherche des chemins les plus courts du haut s. \u003d 1 pour le graphique sur la Fig. 6, l'algorithme a d'abord commandé le sommet 3, puis le sommet 2 et terminer le travail. Dans ce cas, ce chemin le plus court vers le top 3, du point de vue de l'algorithme Daekstra, est une longueur d'arc (1,3) 3.

En fait, le chemin le plus court du sommet 3 comprend des arcs (1.2) et (2.3), la longueur de ce chemin est de 5 + (- 3) \u003d 2.

En raison de la présence d'un ARC (2.3) d'une longueur négative -3, les principes de base suivants ont été perturbés:

k. à proximité s. Le sommet se situe à une distance de deux arcs, et pas un;

le sommet intermédiaire du chemin le plus court 1-2-3 (sommet 2) se situe plus loin du sommet 1 (à une distance de 5) que le sommet final du chemin 3.

Par conséquent, la présence d'arc de longueur négative complique la solution du problème du chemin le plus court et nécessite l'utilisation d'algorithmes plus complexes, plutôt que l'algorithme Daekstra.

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.