Dijkstra's Algorithmus -Zeit -Komplexität

„Der Algorithmus von Dijkstra sucht nach dem kürzesten Weg zwischen zwei beliebigen Knoten in einem Diagramm. Der Knoten wird auch als Scheitelpunkt in Diagrammwerken bezeichnet. Ein Zweig in einer Grafik wird auch als Kante bezeichnet. Der Einfachheit halber wird das Programm in diesem Artikel nach dem kürzesten Weg zwischen einem Quellscheitelpunkt und einem Zielscheitelpunkt suchen.”

Betrachten Sie die folgenden Städte: A, B, C, D, E und F, die durch Straßen verbunden sind:

Diese Städte sind durch Straßen verbunden (von denen angenommen werden kann, dass sie gerade sind). Die Straßenlänge von der Stadt A in die Stadt B beträgt 4 Einheiten; Es wird nicht zur Skalierung gezeichnet. Die Straßenlänge von der Stadt A in die Stadt C beträgt 5 Einheiten; Es wird nicht zur Skalierung gezeichnet. Die Länge von der Stadt B bis zur Stadt E beträgt 11 Einheiten, die nicht im Maßstab gezogen werden. Die Straßen zwischen anderen Städten sind ähnlich angegeben.

Die Städte: A, B, C, D, E und F sind die Scheitelpunkte einer Grafik. Die Straßen sind die Ränder des Diagramms. Diese Grafik wird jedoch in einer mathematischen Datenstruktur dargestellt, unterschiedlich als das geografische Layout.

Der Algorithmus von Dijkstra kann verwendet werden, um den kürzesten Weg zwischen einem Quellscheitel (z. B. A) und jedem anderen Scheitelpunkt zu finden. Weitere Einfachheit halber wird dieser Artikel darauf abzielen, nach dem kürzesten Weg von a nach e zu suchen.

Es gibt verschiedene Wege von A nach E, mit unterschiedlichen Längen, wie folgt:

A-B-D-F: 4 + 9 + 2 = 15
A-B-E-F: 4 + 7 + 6 = 17
A-B-C-E-F: 4 + 11 + 3 + 6 = 24
A-B-C-E-D-F: 4 + 11 + 3 + 13 + 2 = 33
A-b-d-e-f: 4 + 9 + 13 + 6 = 32
A-b-e-d-f: 4 + 7 + 13 + 2 = 26
A-C-E-F: 5 + 3 + 6 = 14
A-C-B-D-F: 5 + 11 + 9 + 2 = 27
A-C-B-E-F: 5 + 11 + 7 + 6 = 29
A-C-B-E-F: 5 + 11 + 7 + 6 = 29
A-c-e-d-f: 5 + 3 + 13 + 2 = 14
A-c-b-e-d-f: 5 + 11 + 7 + 13 + 2 = 38

Aus dieser Auflistung ist der kürzeste Weg A-C-E-F mit einer Gesamtlänge von 14 Einheiten.

Das Hauptziel dieses Artikels ist es, den Algorithmus von Dijkstra zu finden, um den kürzesten Weg von a nach e zu erhalten. Die Zeit wird nicht in Sekunden oder Minuten verabreicht. Es ist die relative Gesamtausführungszeit, die als Zeitkomplexität bezeichnet wird, die gegeben wird. C ++ - Codierung wird ebenfalls bereitgestellt.

Graph zu verwenden

Die Zeitkomplexität (relative Laufzeit) hängt hauptsächlich von der Art der mathematischen Grafik ab, die zur Darstellung des geografischen Layouts verwendet wird. Es hängt auch vom Algorithmus (eine andere Art von Algorithmus) ab, mit der die benachbarten Scheitelpunkte jedes Scheitelpunkts im Gesamtalgorithmus (Dijkstra -Algorithmus) sortiert werden, um den Algorithmus zu sortieren. Die Sortierung benachbarter Scheitelpunkte wird in diesem Artikel nicht behandelt.

Die für diesen Artikel ausgewählte mathematische Grafik wird als Adjazenzmatrix bezeichnet. Es ist:

Die Reihenhöhen sind die Stadtnamen von A bis F. Die Säulenkopfzeile sind die gleichen Stadtnamen von A bis F. Jeder Eintrag ist die Länge einer Straße von einer Stadt zur nächsten. Die Länge einer Straße von einer Stadt zu sich ist Null. Die Länge einer Straße von einer Stadt zur anderen, nachdem er ein oder mehrere Städte übersprungen hat, ist ebenfalls Null. Es werden nur direkte Straßen berücksichtigt. Jeder Eintrag befindet sich zuerst nach Zeile und dann nach Spalte. Auch hier hat jeder Eintrag die Länge einer Straße, ohne eine Stadt zu überspringen und nicht in die Stadt selbst. Diese Matrix ist eine mathematische Darstellung des oben angegebenen geografischen Netzwerks.

Die Matrix besteht also aus Kanten, mit den Zeilen- und Säulenkopfzeilen derselben Scheitelpunkte. Die Matrix ist die Hauptstruktur, die im Programm benötigt wird. In diesem Grundprogramm werden zwei weitere Vektoren (Arrays) verwendet.

Dijkstra -Algorithmus

Der Algorithmus von Dijkstra sucht nach dem kürzesten Weg zwischen zwei beliebigen Scheitelpunkten in einem Diagramm (Netzwerk). Die obige Matrix ist das Diagramm, das dem obigen geografischen Netzwerk entspricht. Der Einfachheit halber wird das Programm in diesem Artikel nach dem kürzesten Weg zwischen einem Quellscheitelpunkt und einem Zielscheitelpunkt suchen. Genau das Programm sucht nach dem kürzesten Weg vom Quellscheitelx, a, zum Zielscheitelpunkt, F.

Der für diese Aufgabe als relevante Algorithmus lautet wie folgt:

- Alle Scheitelpunkte sind als nicht besucht markiert. Zu diesem Zeitpunkt werden eine Reihe aller nicht besuchten Eckpunkte erstellt.

- Weisen Sie allen Scheitelpunkten einen vorläufigen Pfadlängenwert zu: der Pfadlänge von der Quelle zur Quelle wird ein Wert von Null zugewiesen; Der Pfadlänge von der Quelle zu einem anderen Scheitelpunkt wird dem einen Wert der Unendlichkeit zugewiesen, i.e., Ein Wert, der höher als der höchstmögliche Weg ist, in der Grafik. Der Wert jedes Scheitelpunkts würde mindestens einmal von einem hohen Wert bis zu einem niedrigeren Wert geändert, da der Algorithmus fortgesetzt wird. Mögliche Scheitelpunkte für den vollständigen kürzesten Weg werden auf den Quellscheitel (a) ausgerichtet sein, beginnend mit dem Quellscheitel (a). Der Scheitelpunkt mit dem Fokus wird als aktueller Scheitelpunkt bezeichnet. Der aktuelle Scheitelpunkt hat Nachbarn, die sich besser aus dem tatsächlichen Netzwerk (geografisches Layout) visualisiert haben.

- Es gibt den aktuellen Scheitelpunkt und es gibt den besuchten Scheitelpunkt. Tatsächlich würde es mehr als einen besuchten Scheitelpunkt in einer Kette geben, während der Algorithmus fortgesetzt wird. Alle zuvor besuchten Scheitelpunkte sind auf dem kürzesten, vollsten Weg, der entwickelt wird, ab der Quelle ab. Die Pfadlänge des zuletzt besuchten Scheitelpunkts ist bekannt (sollte bekannt sein). Ein Scheitelpunkt wird besucht, wenn seine Pfadlänge bestätigt wird. Der besuchte Scheitelpunkt gibt bisher die geringste Pfadlänge aus der Quelle, da der Algorithmus im Gange ist. Die nicht besuchten Nachbarn des aktuellen Scheitelpunkts, mit Ausnahme seines unmittelbaren früheren besuchten Nachbarn, haben vorläufige Werte (Pfadlängen aus der Quelle), von denen einige noch unendlich sind (sehr hoher Wert). Für jeden nicht besuchten Nachbarn und der aktuelle Keil nicht besuchter Nachbar. Wenn dieses Ergebnis geringer ist als das, was da war, wie die vorläufige Pfadlänge von der Quelle zum nicht besuchten Nachbarn des aktuellen Scheitelpunkts, wird dieser berechnete Wert zum neuen vorläufigen Wert für den Nachbarn des aktuellen Scheitelpunkts. Das heißt, der neue vorläufige Pfadwert für einen nicht besuchten Schmerz.

- Es kann mehr als einen aktuellen Eckpunkt geben. Wenn auf alle Nachbarn jedes Stromscheitels zugegriffen wurde und neue geeignete vorläufige Pfadlängen angegeben ist, wird der Stromscheitel mit der geringsten Pfadlänge aus der Quelle (am wenigsten Wert) als besucht angesehen. Da es den geringsten Wert hatte, wird sein geringster Wert als die bisher kürzeste Teil-Pfad-Länge bestätigt. Der zuvor besuchte Scheitelpunkt wird aus dem nicht besuchten Scheitelpunkt -Set entfernt. Ein besuchter Scheitelpunkt wird nie wieder überprüft. Alle Besuche danach hätten eine größere Pfadlänge.

- Die beiden vorherigen Schritte werden in der Reihenfolge für jeden nächsten aktuellen Scheitelpunkt wiederholt, der zum besuchten Scheitelpunkt wird. Diese Wiederholung wird fortgesetzt, bis der Zielscheitelpunkt erreicht ist. Der Zielscheitelpunkt kann nach dem Quellscheitungsscheitel einen jeden Scheitelpunkt sein. Der Einfachheit halber wurde der letzte Scheitelpunkt f des obigen Netzwerks jedoch als Zielscheitelpunkt für diesen Artikel ausgewählt.

- Im Verlauf des Algorithmus sollte jeder übergeordnete (zuvor besuchte) Scheitelpunkt und jedes Kind (als nächstes besucht) Scheitelpunkt des kürzesten Pfades aufgezeichnet werden, falls der kürzeste Weg durch Scheitelpunkte sowie der kürzeste Weg nach Länge erforderlich ist (erforderlich, (der kürzeste Pfad nach Länge ist erforderlich ist (es ist gefragt). Wenn der Zielscheitelpunkt erreicht und besucht wird, kann der vollständige kürzeste Weg nach hinten verfolgt werden, wenn der Pfad durch Scheitelpunkte benötigt wird. Was die Pfadlänge betrifft, wurde es berechnet, als der Algorithmus fortschritt.

Illustration Dijkstra Algorithmus

Die oben genannte Straße

Das Netzwerk wird verwendet, um den Algorithmus von Dijkstra zu veranschaulichen. Es wird unten für eine einfache Referenz neu gespielt.

Es beginnt an der Quelle „A“ mit einer Pfadlänge von Null. "A" wird als besucht und aus der nicht besuchten Liste (SET) angesehen und entfernt). "A" wird an eine besuchte Liste gesendet, falls der Pfad nach Scheitelpunkten erforderlich ist.

Die Pfadlängen von A nach B sind:

A-B = 4
A-C-B = 5 + 11 = 16

Zwischen 4, 16 und Unendlichkeit (das war da) ist 4 das geringste. B wird also B des vorläufigen Wertes von 4 als Pfadlänge gegeben.

Die Pfadlängen von a bis c sind:

A-C = 5
A-b-c = 4 + 11 = 15

Zwischen 5, 15 und Unendlichkeit (das war da) ist 5 das geringste. C wird also den vorläufigen Wert von 5 als Pfadlänge gegeben.

B und C waren die nicht besuchten Nachbarn von a. Derzeit hat jeder eine vorläufige Pfadlänge. Zwischen B und C muss ein Scheitelpunkt ausgewählt werden. B und C haben auch Nachbarn.

Die nicht besuchten Nachbarn von B sind D, E und C mit vorläufigen unendlichen Längen. Die nicht besuchten Nachbarn von C sind B und E mit vorläufigen unendlichen Längen. Ein Nachbar hat einen direkten Vorteil des fraglichen Scheitelpunkts.

Die von A bis D berechnete Pfadlänge durch B ist:

A-B-D = 4 + 9 = 13

Die von A nach E berechnete Pfadlänge durch B ist:

A-b-e = 4 + 7 = 11

Die von A bis C berechnete Pfadlänge durch B ist:

A-b-c = 4 + 11 = 15

Das sind die Pfadlängen durch B zu Bs Nachbarn, von dem besuchten Scheitelpunkt "A". Die vorläufigen Pfadlängen durch C sollte ebenfalls bestimmt werden.

Die von A bis B durch C berechnete Pfadlänge lautet:

A-C-B = 5 + 11 = 16

Die von A bis E bis C berechnete Pfadlänge lautet:

A-c-e = 5 + 3 = 8

Das sind die Pfadlängen durch C zu Cs Nachbarn, von dem besuchten Scheitelpunkt „A“, "A".

Alle bisher vorläufigen berechneten Teilweglängen sind:

A-B-D = 4 + 9 = 13
A-b-e = 4 + 7 = 11
A-b-c = 4 + 11 = 15
A-C-B = 5 + 11 = 16
A-c-e = 5 + 3 = 8

Der kürzeste dieser Teil-Pfad-Längen ist:

A-c-e = 5 + 3 = 8

Also wird der Scheitelpunkt C für den Weg nach vorne ausgewählt. Dies ist der nächste besuchte Scheitelpunkt. Jeder mögliche Weg durch B wird aufgegeben. C wird dann als besucht angesehen. Der Scheitelpunkt C wird aus der nicht besuchten Liste entfernt. C wird an die besuchte Liste gesendet (um nach a zu sein).

C sollte nicht besuchte Nachbarn mit vorläufigen Pfadlängen haben. In diesem Fall ist es b und e. B hat Nachbarn mit unendlichen Pfadlängen, die d und e sind. E hat Nachbarn mit unendlichen Pfadlängen, die d und f sind. Um den nächsten besuchten Knoten auszuwählen, müssen die vorläufigen Teilwadenlängen von C bis B und E berechnet werden. Die Berechnungen sind:

A-C-B-D = 5 + 11 + 9
= 16 + 9 = 25
A-c-b-e = 5 + 11 + 7
= 16 + 7 = 23
A-c-e-d = 5 + 3 + 13
= 8 + 13 = 21
A-c-e-f = 5 + 3 + 6
= 8 + 6 = 14

Der kürzeste für diese Teilweiten ist:

A-c-e-f = 8 + 6 = 14

Zu diesem Zeitpunkt ist E der Weg nach vorne. Dies ist der nächste besuchte Scheitelpunkt. Jeder mögliche Weg durch D wird aufgegeben. E wird aus der nicht besuchten Liste entfernt und zur besuchten Liste hinzugefügt (nach c).

E hat Nachbarn mit vorläufigen Pfadlängen nicht besucht. In diesem Fall ist es d und f. Wenn F nicht besuchte Nachbarn hätte, hätte ihre vorläufigen Pfadlängen von „A“, der Quelle, unendlich sein sollen. Jetzt beträgt die Länge von F bis nichts 0. Um den nächsten besuchten Knoten (Scheitelpunkt) auszuwählen. Die Berechnungen sind:

A-c-e-d-f = 5 + 3 + 13 + 2
= 8 + 15 = 23
A-c-e-f- = 5 + 3 + 6 + 0
= 14 + 0 = 14

Der kürzeste dieser Teil-Pfad-Längen ist:

A-c-e-f- = 14

Zu diesem Zeitpunkt ist F der Weg nach vorne. Es wird als besucht angesehen. F wird aus der nicht besuchten Liste entfernt und zur besuchten Liste hinzugefügt (nach E).

F ist das Ziel. Und so ist die kürzeste Pfadlänge von der Quelle a, bis zum Ziel, F, 14. Die Scheitelpunkte und ihre Bestellung in der besuchten Liste sollten A-C-E-F sein. Dies ist der kürzeste vorwärtskürzeste Weg durch Scheitelpunkte. Um den umgekehrten kürzesten Pfad durch Scheitelpunkte zu erhalten, lesen Sie die Liste rückwärts.

C ++ - Codierung

Der Graph

Die Grafik für das Netzwerk ist ein zweidimensionales Array. Es ist:

int g [v] [v] = 0,4,5,0,0,0,
4,0,11,9,7,0,
5,11,0,0,3,0,
0,9,0,0,13,2,
0,7,3,13,0,6,
0,0,0,2,6,0;

Es sollte in der C ++ - Hauptfunktion codiert werden. Jeder Eintrag ist die Länge der Kante von einem Scheitelpunkt, Read-by-Rows, bis zum nächsten Scheitelpunkt, Read-by-Säulen. Ein solcher Wert ist nicht für mehr als ein Scheitelpunktpaar.

Eckpunkte als Zahlen

Aus Gründen der Bequemlichkeit werden die Scheitelpunkte durch Zahlen unter Verwendung der ASCII -Codierung wie folgt identifiziert:

A ist 65
B ist 66
C ist 67
D ist 68
E ist 69
F ist 70
A ist 0 + 65 = 65
B ist 1 + 65 = 65
C ist 2 + 65 = 65
D ist 3 + 65 = 65
E ist 4 + 65 = 65
F ist 5 + 65 = 65

Die Codierungswerte für A, B, C, D, E und F sind wie folgt:

A = 0
B = 1
C = 2
D = 3
E = 4
F = 5

65 wird zu jeder dieser Zahlen hinzugefügt, um die entsprechende ASCII -Nummer zu erhalten, aus der der entsprechende Buchstaben erhalten wird.

Beginn des Programms

Der Beginn des Programms ist:

#enthalten
#enthalten
Verwenden von Namespace STD;
int int_max = +2'147'483'647; //Unendlichkeit
#define v 6 // Vertex -Nummer in G
int kurzdünste = int_max;
vector nicht besucht = 0, 1, 2, 3, 4, 5;
vectoristed;

Der vom Programmierer gewählte Wert für unendlich gewählte Unendlichkeit beträgt 2147483647. Die Anzahl der Eckpunkte, V (in Großbuchstaben), wird als 6 definiert (zugewiesen). Die Elemente des nicht besuchten Vektors (Array) sind a, b, c, d, e und f (0, 1, 2, 3, 4, 5), entsprechend den ASCII -Code -Nummern 65, 66, 67, 68, 69, 70. Diese Reihenfolge ist in diesem Fall nicht unbedingt eine vorgegebene, sortierte Reihenfolge. Besuchte Scheitelpunkte werden in die vom Algorithmus entdeckte Reihenfolge in den besuchten Vektor geschoben, beginnend mit dem Quellscheitelpunkt.

Die GetNeighbors () -Funktion

Diese Funktion erhält alle Nachbarn vor einem Scheitelpunkt, beginnend von kurz nach dem zuvor besuchten verwandten Scheitelpunkt. Der Funktionscode ist:

VectorgetNeighbors (int Graph [v] [v], int vindx, intvisedIndx)
VectorRingighbors;
für (int j = prävisitedIndx+1; j;if (Graph [Vindx] [j] != 0)
Nachbarn.push_back (j);

Nachbarn zurückkehren;

Die dijkstra () -Funktion

Nachdem der Quellindex (Vertex) vom Programm berücksichtigt wurde, geht die Funktion dijkstra () rekursiv in Aktion, bis der Zielindex (Vertex) berücksichtigt wird. Der Funktionscode ist:

void dijkstra (int graph [v] [v], int VisitedIDX, int VisitLength)
int VisitedIndx = VisitedIDX;
int newvisitedIndx = v;
int minLength = int_max;
int besuchtelänge;
int TentLength1 = 0;
vectorvisedednbs = GetNeighBors (Diagramm, besuchtindx, VisitedIDX);
für (int i = 0; iTentLength1 = VisitLength + Graph [VisitedIDX] [VisitedNbs [i]];
vectorCurrentnbs = getNeighbors (Diagramm, besuchtesNbs [i], besuchtidx);
if (currentnbs.Größe() != 0)
für (int j = 0; j int TentLength2 = TentLength1 + Graph [besuchtnbs [i]] [currentNbs [j]];
if (TentLength2 besuchtLength = TentLength1; // bestätigt, wenn es am wenigsten ist
newvisededIndx = besuchtnbs [i];



anders
besuchtLength = TentLength1; //bestätigt
newvisededIndx = besuchtnbs [i];


VisitedIndx = newvisitedIndx;
nicht besucht [VisitedIndx] = -1;
hat besucht.push_back (besuchtesIndx);
Kurzeinstufe = besuchte Länge;
if (besuchtindx< V -1)
Dijkstra (Graph, VisitedIndx, VisitedLength);

Die StartDijkstra () -Funktion

Der Algorithmus des Dijkstra beginnt mit dieser Funktion, um die Quellcode -Situation zu verarbeiten. Der Funktionscode ist:

void startdijkstra (int graph [v] [v], int srcvidx)
int VisitedIndx = srcvidx;
nicht besucht [VisitedIndx] = -1;
hat besucht.push_back (besuchtesIndx);
int VisitedLength = 0;
Dijkstra (Graph, VisitedIndx, VisitedLength);

Die oben genannten Codesegmente können in der Reihenfolge zusammengestellt werden, um das Programm zu bilden.

Die C ++ - Hauptfunktion

Eine geeignete C ++ - Hauptfunktion ist:

int main (int argc, char ** argv)

int g [v] [v] = 0,4,5,0,0,0,
4,0,11,9,7,0,
5,11,0,0,3,0,
0,9,0,0,13,2,
0,7,3,13,0,6,
0,0,0,2,6,0;
int Sourcevertex = 0;
startDijkstra (g, Sourcevertex);
Cout<für (int i = 0; iCout<< (char)(visited[i] + 65) << ";
Cout<Rückkehr 0;

Abschluss

Zeitkomplexität ist die relative Laufzeit. Unter der Annahme, dass die Sortierung der Eckpunkte (Nachbarn) gut ist, soll das obige Programm die folgende Zeitkomplexität haben:

O ((| e | + | v |) log | v |)

wo | e | ist die Anzahl der Kanten, | v | ist die Anzahl der Eckpunkte, und ein Protokoll ist Protokoll₂. Die Big-O mit seinen Klammern () ist ein Weg, um anzuzeigen, dass der Ausdruck in der Klammung Zeitkomplexität ist (relative Laufzeit).

Die schlimmste Zeitkomplexität für den Algorithmus von Dijkstra ist: O (| V |²)
[/cc]