Methode Daekstra finden Sie den kürzesten Weg. Diagramme Den kürzesten Abstand zwischen den beiden Scheitelpunkten mit dem Deiquistra-Algorithmus finden. Schema des sequentiellen Algorithmus

Der Algorithmus Daekstra ist ein Algorithmus in den Graphen, der den kürzesten Weg zwischen den beiden Scheitelpunkten in der Grafik mit nicht negativen Längen des Bogens findet. Es ist auch oft eine Aufgabe, den kürzesten Weg von diesem Scheitelpunkt an alle anderen zu berechnen. Der Algorithmus wird in der Programmierung weit verbreitet, beispielsweise wird es durch Routing-Protokolle verwendet.

Beschreibung

Der Algorithmuseingang erhält ein gewichtetes orientiertes Diagramm mit nicht negativen Gewichtsbögen. Die Ausgabe ist ein Satz kürzester Wege von diesem Scheitelpunkt an andere.

Zu Beginn wird der Abstand für den anfänglichen Scheitelpunkt als Null angenommen, und die Entfernungen zu allen anderen werden unendlich verstanden. Ein Array von Flags, die bezeichnet, ob die Oberseite übergeben wird, gefüllt mit Nullen. Dann wird in jedem Schritt des Zyklus eine Oberseite mit einem Mindestabstand zum Anfang und dem Flag gleich Null gesucht. Dafür ist das Flag installiert und alle benachbarten Scheitelpunkte werden geprüft. Wenn der vorherige Abstand von der Quellverpackung zuvor überprüft wird als die Menge des Abstands zum aktuellen Scheitelpunkt und der Länge der Rippe von ihm an den überprüften Scheitelpunkt, dann entspricht der Abstand zum getesteten Scheitelpunkt dem Abstand zur aktuellen + Kante von der aktuellen bis zum aktuell geprüften. Der Zyklus ist abgeschlossen, wenn die Flaggen aller Scheitelpunkte 1 entsprechen, oder wenn der Abstand zu allen Scheitelpunkten mit Flagge 0 unendlich ist. Der letzte Fall ist dann möglich und nur, wenn die Zählung intolerant ist.

Algorithmus Daekstra. in Pseudocode.

Eingang: VON : Array von Real-Count-ARC-Protokollmatrix; S ist ein Scheitelpunkt, von dem der kürzeste Weg und T ein Scheitelpunkt ist, zu dem es sucht.

Ausgabe: v\u003e Array von echt; und n: Array von 0..r. Wenn die Spitze v. Liegt auf dem kürzesten Weg von s. zu t, Das FERNSEHER]- Länge des kürzesten Weges von s. zu y; H [y] - Oben, direkt vorangestellt w. Auf dem kürzesten Weg.

H ist ein Array, in dem der Scheitelpunkt n dem Scheitelpunkt m entspricht, der vorherige auf dem Weg zu n von s.

T ist ein Array, in dem der Scheitelpunkt n der Entfernung von ihm zu s entspricht.

X ist ein Array, in dem der Scheitelpunkt n 1 entspricht, wenn der Pfad davon bekannt ist, und 0, wenn nicht.

initialisierung von Arrays:

zum v. von 1 bis. r. tun.

T [v.]: = ∞ (Der kürzeste Weg ist unbekannt)

X [v]: \u003d 0 (Alle Scheitelpunkte sind nicht markiert)

H [s]: \u003d 0 ( s. nichts ist vorangestellt)

T [s]: \u003d 0 (der kürzeste Weg hat eine Länge von 0 ...)

X [s]: \u003d 1 (... und er ist bekannt) v. : = s. (aktueller Scheitelpunkt)

M: (Aktualisierungsmarken)

zum und ∈. G (( und) tun

wenn X [und] = 0 & T [und]> FERNSEHER] + C. Dann.

T [und]: = FERNSEHER] + C. (ein kürzerer Pfad von s. im und durch v. }

H [u]:= v. (erinnere dich dran)

m.: = ∞

v. : = 0

(Suchen Sie nach dem Ende des kürzesten Weges)

zum und von 1 bis. p. tun.

wenn X [u] = 0 & T [u]< t. Dann.

v:= u.;

m:= T [u] (Oben v. beendet den kürzesten Weg von s.

wenn v. = 0 Dann.

stoppen Sie (kein Pfad von s. im t.) Ende, wenn

wenn v.= t. Dann.

stoppt (der kürzeste Weg von s. im t.) Ende, wenn

X [v]: \u003d 1 (der kürzeste Weg von s. im v. ) Gehe zu. M.

Rechtfertigung

Um die Richtigkeit des Daekstra-Algorithmus zu beweisen, reicht es aus, dass mit jeder Leistung des Körpers des Zyklus, der das Etikett M beginnt, als v.ein Scheitelpunkt wird verwendet, für den der kürzeste Weg von der Oberseite bekannt ist. s.Mit anderen Worten, wenn x [v] \u003d 1, dann t [v] \u003d d (s, v) , Und alle Scheitelpunkte auf dem von dem N-Vektor ermittelten Pfad (S, V) haben dieselbe Eigenschaft, die ist

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

Wirklich (nach Induktion), erstmals v. Der Scheitelpunkt S wird verwendet, für den der kürzeste Weg leer ist und eine Länge von 0 aufweist (nicht leere Pfade können nicht kürzer sein, da die Länge der Bögen nicht negativ ist). Lass t [u] \u003d d (s, u) für alle zuvor ausgeprägten Scheitelpunkte und. Betrachten Sie den neu markierten Scheitelpunkt v.das ausgewählt aus der Bedingung t [v] \u003d min t [und]. Beachten Sie, dass, wenn der Weg durch die markierten Scheitelpunkte bekannt ist, dann auch für den kürzesten Weg bekannt ist. Angenommen (sonst), dass t [v]\u003e d (s, v), das heißt, der Weg, der aus gefunden wurde s.im v,ist nicht die kürzeste. Dann sollten auf diesem Weg unermüdbare Scheitelpunkte geben. Betrachten Sie den ersten Scheitelpunkt w.auf diesem Weg, so dass t [w] = 0. iim: t [w] = d (s, w) ⩽d (s\u003e v)< Т[v],что противоречит выбору вершины u.

Vorübergehende Schwierigkeit

Die Komplexität des Daekstra-Algorithmus hängt von der Methode des Findens der Oberseite mit einem Mindestabstand zum anfänglichen Verfahren zum Aufbewahren einer Vielzahl von ungewissenen Scheitelpunkten und Verfahren zum Aktualisieren von Tags ab. Sei n die Anzahl der Scheitelpunkte und durch m - die Anzahl der Kanten in der Spalte. Wenn dann im einfachsten Fall alle Set-Scheitelpunkte angesehen werden, um die Scheitelpunkte mit einem Mindestabstand zum anfänglichen Scheitelpunkt zu durchsuchen, und ein Array wird verwendet, um die Entfernungen, die Zeit des Betriebs des Algorithmus - O (N 2) zu speichern. Der Hauptzyklus wird ungefähr n-mal ausgeführt, in jedem von ihnen wird das Minimum für n Operationen ausgegeben. Die Anzahl der Operationen wird auf den Zyklen entlang der Nachbarn jedes Besuchs des Scheitelpunkts, der Anzahl der ROBER M (da jede Kante zweimal in diesen Zyklen findet und eine konstante Anzahl von Operationen erforderlich ist). Somit ist die Gesamtbetriebszeit des O (N 2 + M) -Algorithmus, aber da m kleiner als n (n-1) ist, erscheint letztendlich etwa (n 2).

Für seltene Diagramme (das heißt, solche, für die m viel weniger als n² ist), können ungepflegte Scheitelpunkte in einem binären Haufen gespeichert werden, und als Schlüssel zur Verwendung von Entfernungen. Da der Zyklus etwa n-mal durchgeführt wird, und die Anzahl der Entspannung (Köderänderungen) ist nicht mehr als M, der Betriebszeit einer solchen Implementierung - O (nlogn + mlogn)

Beispiel

Berechnung der Entfernungen vom Scheitelpunkt 1 für passierbare Scheitelpunkte:

Vor jedem Stadtgebiet (wenn Sie nur auf den Straßen bewegen können).

Option 2. Es gibt einige Flüge zwischen den Städten der Welt, für jeden berühmten Preis. Die Kosten des Fluges von A bis B sind möglicherweise nicht gleich den Kosten des Fluges von B nach A. Finden Sie die Route der Mindestkosten (möglicherweise mit Transfers) von Kopenhagen nach Barnaul.

Formale Definition

Beispiel

Betrachten Sie die Ausführung des Algorithmus im Beispiel des in der Figuren gezeigten Grafik.

Lassen Sie es erforderlich sein, den kürzesten Abstand vom 1. Scheitelpunkt an alle anderen zu finden.

Implementierung in Programmiersprachen

Leistung in der Sprache C (SI)

#Define Größe 6 #define INF 1000000000 INT A [Größe] [Größe] \u003d ((Inf, 5, INF, INF, INF, INF, INF), (1, 2, 3, 4, 5, 6), // Matrixpfade (1, 2, 3, 4, 5, 6), (1, 2, 3, 4, 5, 6), // horizontale Indizes von dem Punkt { 1 , 2 , 3 , 4 , 5 , 6 },{ 1 , 2 , 3 , 4 , 5 , 6 }}; // senkrecht zu Punkt, Wert - Gewicht Int d [Größe]; // Array der kürzesten gefundenen Pfade, Indizes - Scheitelpunkte der Grafik void deikstra () (int v [größe]; // Anordnung von Etiketten int temp, i; int minindex, min; für (i \u003d 0; ich< SIZE ; i ++ ) { d [ i ] = INF ; // Array von Pfaden wird unendlich initialisiert v [i] \u003d 1; ) D [0] \u003d 0; tun ( // Durchführung des Algorithmus minindex \u003d inf; Min \u003d inf; für (i \u003d 0; ich< 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 + a [minindex] [i]; if (temp< d [ i ]) d [ i ] = temp ; } } v [ minindex ] = 0 ; } } while (minindex < INF ); }

kürzester Weg Heute ist es eine lebenswichtige Aufgabe und wird fast überall verwendet, reicht von der Suche nach der optimalen Route zwischen zwei Objekten auf dem Boden (z. B. dem kürzesten Weg von zu Hause an der Universität), in Autopilotsystemen, um den optimalen Weg während des Transports zu finden, Schaltinformationspaket in Netzwerken und T.P.

Der kürzeste Weg gilt als mit einem bestimmten mathematischen Objekt namens Diagramm. Suche kürzester Weg Es wird zwischen zwei angegebenen Scheitelpunkten in der Grafik durchgeführt. Das Ergebnis ist der Pfad, dh die Reihenfolge von Scheitelpunkten und Rippen, die an den beiden benachbarten Scheitelpunkten und seiner Länge vorfallen.

Betrachten Sie drei die meisten effektiver Algorithmus Verlegung kürzester Weg:

• algorithmus Daekstra.;
• Floyd-Algorithmus;
• Übergeborene Algorithmen.

Diese Algorithmen lassen sich leicht mit einer kleinen Anzahl von Scheitelpunkten in der Grafik durchführen. Mit einer Erhöhung ihrer Anzahl der Suchaufgabe kürzester Weg Komplett.

Algorithmus Daekstra.

Dieser Algorithmus ist ein Algorithmus in den Graphen, der 1959 von den Niederlandenwissenschaftler E. Dyakstroy erfunden wurde. Der Algorithmus findet den kürzesten Abstand von einem der Scheitelpunkte des Graphen an alle anderen und wirkt nur für Diagramme ohne Negativgewicht.

Jeder Scheitelpunkt wird dem Gewicht zugeschrieben - dies ist das Gewicht des Weges vom anfänglichen Scheitelpunkt hier. Außerdem kann jeder Scheitelpunkt hervorgehoben werden. Wenn der Scheitelpunkt hervorgehoben ist, ist der Pfad von ihm an den anfänglichen Scheitelpunkt der kürzesten, wenn nicht, dann vorübergehend. Wenn Sie mit der Grafik kommen, hält der Algorithmus die Route für jeden Scheitelpunkt, und wenn er sich als kürzester erweist, hebt die Oberseite hervor. Das Gewicht dieses Scheitelpunkts ist das Gewicht des Weges. Für alle Nachbarn dieses Scheitelpunkts berechnet der Algorithmus auch das Gewicht, ohne dass sie unter keinen Umständen verwendet werden. Der Algorithmus beendet seine Arbeit und erreicht den letzten Scheitelpunkt und das Wiegen kürzester Weg Das Gewicht des letzten Scheitelpunkts wird.

Algorithmus Daekstra.

Schritt 1. Für alle Tops, mit Ausnahme des ersten ist das Gewicht eine gleiche Unendlichkeit, und der erste Scheitelpunkt ist 0.

Schritt 2. Alle Scheitelpunkte sind nicht hervorgehoben.

Schritt 3. Der erste Scheitelpunkt wird als aktuell deklariert.

Schritt 4 aktueller Scheitelpunkt mit dem Underefidant.

Schritt 5. Unter den ungekümmelten Gipfeln ist ein Top mit minimalem Gewicht. Wenn dies nicht gefunden wird, ist das Gewicht aller Scheitelpunkte gleich unendlich, die Route existiert nicht. Folglich der Ausgang. Andernfalls ist der Strom das resultierende Oberteil. Es wird zugewiesen.

Schritt 6. Wenn sich der aktuelle Scheitelpunkt als das Finale herausstellt, ist der Weg gefunden, und sein Gewicht ist das Gewicht des letzten Scheitelpunkts.

Schritt 7. Gehen Sie zu Schritt 4.

In der Software-Implementierung. algorithmus Daekstra. Wir erstellen einen Satz von S-Scheitelpunkten, für die die kürzesten Wege des anfänglichen Scheitelpunkts bereits bekannt sind. Bei jedem Schritt zu den Satz S wird der gleiche Scheitelpunkt hinzugefügt, der Abstand vom anfänglichen Scheitelpunkt ist geringer als für andere verbleibende Scheitelpunkte. In diesem Fall verwenden wir das Array D, in dem die Längen aufgezeichnet werden kürzeste Wege Für jeden Scheitelpunkt. Wenn der Satz S alle Scheitelpunkte des Diagramms enthält, enthält das Array D Längen kürzeste Wege Von dem anfänglichen Scheitelpunkt zu jedem Scheitelpunkt.

Zusätzlich zu den angegebenen Arrays verwenden wir die C-Matrix von C, wo das Element C die Länge der Kanten (i, j) ist, wenn es keine Rippen gibt, dann wird seine Länge auf gleiche Unendlichkeit angewiesen, das heißt mehr als jede tatsächliche Rippenlänge. Eigentlich ist matrix c segelmatrix.in dem alle Nullelemente durch Infinity ersetzt werden.

Um das selbst zu bestimmen

5.4.3. Die Herausforderung des kürzesten Weges und des Daekster-Algorithmus seiner Entscheidung

Lass den orgraf einstellen G.(V., E.), wobei jeder Lichtbogen mit der Zahl in Einklang gebracht wird
namens bogen lange.

Definition. Lena Der Pfad wird als Summe der Bogenlängen bezeichnet, die diesen Weg bilden. Die Aufgabe des kürzesten Wegessetzt so.

Variante 1. Finden Sie die Längen der kürzesten Wege (Wege der minimalen Länge) und die Wege selbst von dem festen Scheitelpunkt s. an alle anderen Scheitelpunkte des Diagramms.

Option 2. Finden Sie die Längen der kürzesten Wege und den Pfaden selbst zwischen allen Paaren der Scheitelpunkte dieses Graphen.

Wenn in der Spalte negative Bögen in der Spalte vorhanden sind, hat die Aufgabe möglicherweise keine Lösungen (verliert die Bedeutung). Dies ist darauf zurückzuführen, dass die Kontur der negativen Länge in der Spalte vorhanden sein kann. Das Vorhandensein negativer Längenschaltungen bedeutet, dass die Pfadlänge gleich gemacht werden kann
. Und wenn keine negativen Längenschaltungen vorhanden sind, gibt es die kürzesten Wege und jeder kürzeste Weg ist eine einfache Kette.

Beachten Sie, dass, wenn der kürzeste Weg existiert, dann eines davon auch der kürzeste Weg zwischen den jeweiligen Scheitelpunkten ist.

Algorithmus Daekstra Lösung des Problems des kürzesten Weges.

Der Algorithmus arbeitet mit Bögen mit positiver Länge und definiert die kürzesten Wege des festen Scheitelpunkts s. an alle anderen Scheitelpunkte des Diagramms. Bezeichnen diese Scheitelpunkte v. 1 , v. 2 ,…, v. n. .

Definition. Lass uns die Spitze anrufen u. näher an der Spitze liegen s.als oben v.Wenn die Länge des kürzesten Weges von s. Vor u. weniger als die Länge des kürzesten Weges von s. Vor v.. Wir werden sagen, dass die Tops u. und v. unwichtig Von oben s.Wenn die Längen der kürzesten Wege von s. Vor u. und von s. Vor v. zusammenpassen.

Der Daekstra-Algorithmus strebte die Scheitelpunkte des Graphen konsequent im Sinne der Nähe nach oben s. und basierend auf den folgenden Grundprinzipien.

Wenn die Längen des ARC positive Zahlen sind, dann

nÄCHSTE K. s. top - sie selbst. Länge des kürzesten Weges von s. Vor s. gleich 0;

nÄCHSTE K. s. scheitel s.Lügen aus s. In der Entfernung eines Bogens  die kürzeste aller Bögen, die die Oberseite verlassen s.;

jede Zwischenseite des kürzesten Weges von s. Zu einigen Scheitelpunkten v. Liegt näher an K. s.als letzter Scheitelpunkt. v.;

der kürzeste Weg zum nächsten bestellten Scheitelpunkt kann nur durch bereits bestellte Peaks passieren.

Lassen Sie den Algorithmus bereits die Gipfel bestellt haben v. 1 , v. 2 … v. k. . Bezeichnen mit
,
Die Länge des kürzesten Wegs nach oben v. iCH. .

Berücksichtigen Sie alle Bögen der Quellgrafik, die in einem der Scheitelpunkte des Sets beginnen.
Und endet in anderen ungewöhnten Scheitelpunkten. Für jeden solchen Bogen zum Beispiel
Ich berechne die Summe
. Dieser Betrag ist gleich der Länge des Pfads von s. im y.in dem der Scheitelpunkt v. iCH. Es gibt eine vorletzte Oberseite und den Weg von s. im v. iCH. - der kürzeste aller miteinander verbundenen Pfaden s. und v. iCH. .

Dies sind die definierten Längen aller Wege von s. Noch nicht bestellte Peaks, in denen nur Scheitelpunkte zwischengeschrittenen Scheitelpunkten sind, sind k. NÄCHSTE K. s.. Lassen Sie den kürzesten dieser Wege darauf enden w.. Dann w. und ist
In der Nähe von K. s. Scheitel.

Technische Aktionen auf dem Daekstra-Algorithmus werden mit der Scheitdurchgeführt. Tag Verter v. bezeichnet, wie
. Etwas Etikett ist eine Zahl, die der Länge eines Pfads entspricht s. vor v.. Tags sind in temporärer und konstant eingeteilt. Bei jedem Schritt wird nur ein Etikett konstant. Dies bedeutet, dass sein Wert gleich der Länge des kürzesten Weges zum entsprechenden Scheitelpunkt ist und dieser Scheitelpunkt selbst angeordnet ist. Die Nummer des nächsten bestellten Scheitelpunkts wird vom Buchstaben bezeichnet r..

Beschreibung des Algorithmus.

Schritt 1. (Erstinstallation). Stellen
Und berücksichtigen Sie dieses Etikett konstant. Stellen
,
Und berücksichtigen Sie diese Markierungen vorübergehend. Stellen
.

Schritt 2. (Gemeinsamer Schritt). Er wiederholt n. sobald alle Scheitelpunkte des Diagramms bestellt sind.

Neu berechnen
Alle ungeordneten Scheitelpunkte. v. iCH. Dazu gehört ein Bogen, der die Oberseite verlässt r, Von der Regel.

Wählen Sie mit einem Mindestzeitaufkleber oben aus. Wenn es mehrere solche Scheitelpunkte gibt, wählen Sie eine aus.

Lassen w.- Top mit einem Mindestzeitaufkleber. Nehmen Sie ein Etikett an
konstant und gestellt
.

Die Schritte des Daekstra-Algorithmus werden zweckmäßigerweise in der Tabelle erstellt, von denen jede Säule dem Scheitelpunkt des Graphen entspricht. Die Reihen der Tabelle entsprechen der Wiederholung des Gesamtschritts.

Beispiel. Für den Graphen in FIG. 4. Finden Sie die kürzesten Wege von den Scheitelpunkten
an alle anderen Scheitelpunkte des Diagramms. Rippen bedeuten zwei Multi-Richtungs-Bögen derselben Länge.

Entscheidung. Auf der Registerkarte. 1 Verzeichneten Verpackungs-Tags bei jedem Schritt. Permanente Tags sind mit "+" gekennzeichnet. Lassen Sie uns detailliert beschreiben, wie die Tags berechnet werden.

Von den Scheitelpunkte 1 übersehen 1 Bögen die Scheitelpunkte 2, 5, 6. erinnern an den Etiketten dieser Scheitelpunkte und füllen die zweite Zeichenfolge des Tisches.

Die Oberseite des Scheitelpunkts 6 wird konstant,
.

Von den Scheitelpunkt 6 Bögen befinden sich noch ungeordnete Scheitelpunkte 2, 5, 8, 9. Neu kalkulieren ihre Zeittags

Fülle 3 Tischreihen. Das Minimum der Zeitkennzeichnungen beträgt 3 (Top-Tag 9),
.

Von den Scheitelpunkt 9 Bögen in den noch nicht ungeordneten Scheitelpunkten 5, 8, 11, 12. Dann

Füllen Sie die vierte Linie des Tisches. In dieser Linie haben zwei Scheitelpunkte  2 und 12 minimale Zeitmarkierungen gleich 4. Erste Ordnung, zum Beispiel der Scheitelpunkt 2. Dann wird der obere 12 zum nächsten Schritt bestellt.

Tabelle 1

So,
.

Von oben 2 gibt es Bögen in den noch stillstunten Scheitelpunkten 3, 4, 5. Erinnerung an temporäre Markierungen dieser Scheitelpunkte

Füllen Sie 5 Tischreihen aus. Die Minimum an Zeitetiketten beträgt 4 (Vertex-Tag 12),
.

Fülle 6 Tabellenreihen. Die Minimum an Zeitaufkleber beträgt 5 (Top-Tag 5),
.

Füllen Sie 7 Zeichenfolge des Tisches. Werden Sie ein konstanter Tag des Scheitelpunkts 8 (es ist gleich 5),
.

Top 11 ist bestellt.

Von den Scheitelpunkt 11 Bögen in ungeordneten Scheitelpunkten 7, 10. Erinnern an den Zeitmarken dieser Scheitelpunkte.

Top 4 erhält ein konstantes Tag.

Von den Scheitelpunkt 4 Bögen in ungeordneten Scheitelpunkten 3, 7. Neu berechnen Time-Tags

Organisieren Sie den Scheitelpunkt 3.

Füllen Sie 12 Tabellenreihen. In diesem Schritt bestellen wir den letzten ungeordneten Scheitelpunkt 10.

Einen Baum kürzester Wegen bauen.

Der Baum der kürzesten Wege ist ein fokussierter Baum mit einer Wurzel oben S. . Alle Wege in diesem Baum sind für diese Grafik kürzester.

Der kürzeste Pfadbaum basiert auf dem Tisch, der Oberteil ist über den Scheitelpunkt in der Reihenfolge eingeschaltet, in der sie konstante Tags erhielten. Der erste im Baum dreht sich an der Wurzel - der Scheitelpunkt S. .

Wir erstellen den kürzesten Weg für unser Beispiel.

Erstens schalten wir die Wurzel im Baum ein - der Scheitelpunkt 1. Dann wird der Bogen in einen Baum (1.6) umgewandelt. Der nächste wurde der Scheitelpunkt 9 bestellt, die Länge des kürzesten Weges, der gleich 3 ist. Die erste Zeitnummer 3 erschien in der dritten Linie, die mit gefüllt wurde
. Folglich ist der Scheitelpunkt 6 die vorletzte Oberseite des kürzesten Weges zum Scheitelpunkt 9. Wir drehen in den Holzbogen (6.9) Länge 1.

Die Oberseite 2 wurde mit der Länge des kürzesten Weges gleich 4 bestellt. Diese Nummer erschien erstmals in der dritten Zeile, mit der erfüllt war
. Folglich verläuft der kürzeste Weg in dem zweiten Scheitelpunkt entlang des Bogens (6.2). Wir schalten den Bogen (6.2) der Länge 2 ein.

Als nächstes wurde die Top 12 bestellt,
. Die erste Zeit Nummer 4 erscheint in der vierten Linie, mit der mit gefüllt wurde
. Der Baum umfasst einen Bogen (9.12) der Länge 1. Der Gesamtbaum der kürzesten Wege ist in Fig. 4 gezeigt. fünf.

Der deiquistische Algorithmus kann falsch sein, wenn in der Spalte negative Bögen in der Spalte vorhanden sind. Also, auf der Suche nach den kürzesten Wegen von oben s. \u003d 1 für den Graph in FIG. In Fig. 6 befahl der Algorithmus zunächst den Scheitelpunkt 3, dann den Scheitelpunkt 2 und beenden Sie die Arbeit. In diesem Fall ist dieser kürzeste Weg zu den Top 3 aus Sicht des Daekstra-Algorithmus  ein Bogen (1.3) Länge 3.

Tatsächlich besteht der kürzeste Weg zum Scheitelpunkt 3 aus Bögen (1.2) und (2.3), die Länge dieses Weges beträgt 5 + (3) \u003d 2.

Aufgrund der Anwesenheit eines Bogens (2.3) einer negativen Länge -3 wurden die folgenden Grundprinzipien gestört:

nÄCHSTE K. s. Der Peak liegt daraus in einem Abstand von zwei Bögen und nicht einem;

die mittlere Oberseite des kürzesten Weges 1-2-3 (Scheitelpunkt 2) liegt weiterhin vom Scheitelpunkt 1 (in einem Abstand von 5) als der endgültige Scheitelpunkt des Pfads 3.

Folglich kompliziert das Vorhandensein von negativem Längenbogen die Lösung des Problems des kürzesten Weges und erfordert den Einsatz komplexerer Algorithmen und nicht der Daekstra-Algorithmus.

Lösen Sie die Aufgabe, den kürzesten Weg des Daekstra-Algorithmus zu finden.
Finden Sie den kürzesten Weg von X0 bis X7. Die Zählung wird von den Elementen der Kostenmatrix eingestellt

Baue dieses Grafik


Beginnen wir mit dem Element X0 und wirweisen es einem Tag 0, betrachten alle seine Nachbarn, weil Es gibt noch keine Notiz, Sie weisen ihnen die entsprechenden Längen zu:


Alle Nachbarn X0 werden berücksichtigt, wir markieren es und gehen nach X1. Seine Nachbarn x0, x2, x4, aber x0 markiert, betrachten es nicht. Für x2: , Verlassen Sie das Etikett.

Für x4: Ersetzen des Etiketts. Alle Nachbarn des Scheitelpunkts X1 werden berücksichtigt, wir markieren es


Gehen Sie zur Spitze von X2. Seine Nachbarn X0, X1, X3, X4, X5, X6, aber X0, X1 sind markiert, betrachten sie nicht.
Für x3: , Verlassen Sie das Etikett.
Für x5: Ersetzen des Etiketts.
Für x4: , Verlassen Sie das Etikett.
Für x6: Ersetzen des Etiketts.
Alle Nachbarn der Spitze des X2 werden berücksichtigt, wir markieren es.


Gehen Sie nach oben X3. Seine Nachbarn x0, x2, x6, aber x0, x2 sind markiert, nicht in Betracht ziehen.
Für x6: , Verlassen Sie das Etikett.
Alle Nachbarn der Spitze des X3 werden berücksichtigt, wir markieren es.


Gehen Sie nach X4. Seine Nachbarn X1, X2, X5, X7, aber X1, X2 sind markiert, betrachten sie nicht.
Für x5: Ersetzen des Etiketts.
Für x7: Ersetzen des Etiketts.
Alle Nachbarn der Spitze des X4 werden berücksichtigt, wir markieren es.


Gehen Sie nach X5. Seine Nachbarn X2, X4, X6, X7, aber X2, X4 sind markiert, betrachten sie nicht.
Für x6: , Verlassen Sie das Etikett.
Für x7: , Verlassen Sie das Etikett.
Alle Nachbarn der Spitze des X5 werden berücksichtigt, wir markieren es.


Gehen Sie zum Anfang X6. Seine Nachbarn X2, X3, X5, X7, aber X2, X3, X5 sind markiert, betrachten sie nicht.
Für x7: , Verlassen Sie das Etikett.
Alle Tops der Spitze des X6 werden berücksichtigt, wir markieren es. Und wir haben den verbleibenden X7 gekennzeichnet, alle Scheitelpunkte werden berücksichtigt.


Schlussfolgerung: Der kürzeste Weg ihres X0 in X7 hat eine Länge von 101, diesen Pfad: x7-x4-x1-x0.