Das folgende Tutorial zeigt uns den Kürzeste-Weg-Algorithmus von Dijkstra. Wir werden die Funktionsweise des Dijkstra-Algorithmus anhand einer schrittweisen grafischen Erklärung verstehen.

Wir werden Folgendes abdecken:

• Ein kurzer Überblick über die grundlegenden Konzepte des Graphen
• Verstehen Sie die Verwendung des Dijkstra-Algorithmus
• Verstehen Sie die Funktionsweise des Algorithmus anhand eines Schritt-für-Schritt-Beispiels

Also lasst uns anfangen.

Eine kurze Einführung in Diagramme

Grafiken sind nichtlineare Datenstrukturen, die die „Verbindungen“ zwischen den Elementen darstellen. Diese Elemente werden als bekannt Eckpunkte , und die Linien oder Bögen, die zwei beliebige Eckpunkte im Diagramm verbinden, werden als bezeichnet Kanten . Formeller ausgedrückt umfasst ein Graph eine Reihe von Eckpunkten (V) Und eine Reihe von Kanten (E) . Der Graph wird mit bezeichnet G(V, E) .

Komponenten eines Diagramms

Eckpunkte:Eckpunkte sind die Grundeinheiten des Diagramms, die zur Darstellung realer Objekte, Personen oder Entitäten verwendet werden. Manchmal werden Scheitelpunkte auch als Knoten bezeichnet.Kanten:Kanten werden gezeichnet oder verwendet, um zwei Eckpunkte des Diagramms zu verbinden. Manchmal werden Kanten auch als Bögen bezeichnet.

Die folgende Abbildung zeigt eine grafische Darstellung eines Diagramms:

Abbildung 1: Grafische Darstellung eines Diagramms

In der obigen Abbildung sind die Eckpunkte/Knoten durch farbige Kreise und die Kanten durch die Linien gekennzeichnet, die die Knoten verbinden.

vergleichbare Schnittstelle in Java

Anwendungen der Graphen

Diagramme werden zur Lösung vieler realer Probleme verwendet. Zur Darstellung der Netzwerke werden Diagramme verwendet. Zu diesen Netzen können Telefon- oder Leitungsnetze oder -wege in einer Stadt gehören.

Beispielsweise könnten wir Graphs verwenden, um ein Transportnetzwerkmodell zu entwerfen, bei dem die Eckpunkte die Einrichtungen anzeigen, die die Produkte senden oder empfangen, und die Kanten Straßen oder Wege darstellen, die sie verbinden. Das Folgende ist eine bildliche Darstellung davon:

Figur 2: Bildliche Darstellung des Verkehrsnetzes

Diagramme werden auch auf verschiedenen Social-Media-Plattformen wie LinkedIn, Facebook, Twitter und anderen verwendet. Beispielsweise verwenden Plattformen wie Facebook Diagramme, um die Daten ihrer Benutzer zu speichern, wobei jede Person mit einem Scheitelpunkt gekennzeichnet ist und jede von ihnen eine Struktur darstellt, die Informationen wie Personen-ID, Name, Geschlecht, Adresse usw. enthält.

Arten von Diagrammen

Die Diagramme können in zwei Typen eingeteilt werden:

1. Ungerichteter Graph
2. Gerichteter Graph

Ungerichteter Graph: Ein Graph mit Kanten, die keine Richtung haben, wird als ungerichteter Graph bezeichnet. Die Kanten dieses Diagramms implizieren eine bidirektionale Beziehung, bei der jede Kante in beide Richtungen durchlaufen werden kann. Die folgende Abbildung zeigt einen einfachen ungerichteten Graphen mit vier Knoten und fünf Kanten.

Figur 3: Ein einfacher ungerichteter Graph

Gerichteter Graph: Ein Graph mit Kanten mit Richtung wird als gerichteter Graph bezeichnet. Die Kanten dieses Diagramms implizieren eine Einwegbeziehung, bei der jede Kante nur in einer einzigen Richtung durchlaufen werden kann. Die folgende Abbildung zeigt einen einfachen gerichteten Graphen mit vier Knoten und fünf Kanten.

Figur 4: Ein einfacher gerichteter Graph

Die absolute Länge, Position oder Ausrichtung der Kanten in einer Diagrammdarstellung hat typischerweise keine Bedeutung. Mit anderen Worten: Wir können denselben Graphen auf unterschiedliche Weise visualisieren, indem wir die Eckpunkte neu anordnen oder die Kanten verzerren, wenn sich die zugrunde liegende Struktur des Graphen nicht ändert.

Was sind gewichtete Diagramme?

Ein Diagramm wird als gewichtet bezeichnet, wenn jeder Kante ein „Gewicht“ zugewiesen wird. Das Gewicht einer Kante kann Distanz, Zeit oder irgendetwas bezeichnen, das die „Verbindung“ zwischen dem Paar von Scheitelpunkten modelliert, das sie verbindet.

In der folgenden Abbildung des gewichteten Diagramms können wir beispielsweise eine blaue Zahl neben jeder Kante beobachten. Diese Zahl wird verwendet, um das Gewicht der entsprechenden Kante anzugeben.

Abbildung 5: Ein Beispiel für ein gewichtetes Diagramm

Eine Einführung in den Dijkstra-Algorithmus

Nachdem wir nun einige grundlegende Diagrammkonzepte kennen, wollen wir uns mit dem Verständnis des Konzepts des Dijkstra-Algorithmus befassen.

Haben Sie sich jemals gefragt, wie Google Maps die kürzeste und schnellste Route zwischen zwei Orten findet?

Nun, die Antwort ist Dijkstras Algorithmus . Dijkstras Algorithmus ist ein Graph-Algorithmus das den kürzesten Weg findet von einem Quellscheitelpunkt zu allen anderen Scheitelpunkten im Diagramm (kürzester Pfad mit einer einzigen Quelle). Es handelt sich um eine Art Greedy-Algorithmus, der nur bei gewichteten Diagrammen mit positiven Gewichten funktioniert. Die zeitliche Komplexität des Dijkstra-Algorithmus beträgt O(V²) mit Hilfe der Adjazenzmatrixdarstellung des Graphen. Diese Zeitkomplexität kann auf reduziert werden O((V + E) log V) mit Hilfe einer Adjazenzlistendarstellung des Graphen, wo IN ist die Anzahl der Eckpunkte und UND ist die Anzahl der Kanten im Diagramm.

Geschichte des Dijkstra-Algorithmus

Dijkstras Algorithmus wurde entworfen und veröffentlicht von DR. Edsger W. Dijkstra , ein niederländischer Informatiker, Software-Ingenieur, Programmierer, Wissenschaftsessayist und Systemwissenschaftler.

Während eines Interviews mit Philip L. Frana für die Kommunikation der Zeitschrift ACM im Jahr 2001 enthüllte Dr. Edsger W. Dijkstra:

„Was ist im Allgemeinen der kürzeste Weg, um von Rotterdam nach Groningen zu reisen: von einer bestimmten Stadt zur anderen? Es ist der Algorithmus für den kürzesten Weg, den ich in etwa zwanzig Minuten entworfen habe. Eines Morgens war ich mit meiner jungen Verlobten in Amsterdam einkaufen und müde setzten wir uns auf die Caféterrasse, um eine Tasse Kaffee zu trinken, und ich überlegte gerade, ob ich das schaffe, und ich habe dann den Algorithmus für den kürzesten Weg entworfen . Wie gesagt, es war eine zwanzigminütige Erfindung. Tatsächlich wurde es 1959, also drei Jahre später, veröffentlicht. Die Publikation ist immer noch lesbar, sie ist sogar ganz nett. Einer der Gründe, warum es so schön ist, liegt darin, dass ich es ohne Bleistift und Papier entworfen habe. Später erfuhr ich, dass einer der Vorteile des Entwerfens ohne Bleistift und Papier darin besteht, dass man fast gezwungen ist, alle vermeidbaren Komplexitäten zu vermeiden. Zu meinem großen Erstaunen wurde dieser Algorithmus schließlich zu einem der Grundpfeiler meines Ruhms.“

Dijkstra dachte über das Problem des kürzesten Weges nach, als er 1956 als Programmierer am Mathematischen Zentrum in Amsterdam arbeitete, um die Fähigkeiten eines neuen Computers namens ARMAC zu veranschaulichen. Sein Ziel war es, sowohl ein Problem als auch eine Lösung (vom Computer erzeugt) auszuwählen, die Menschen ohne Computerkenntnisse verstehen konnten. Er entwickelte den Algorithmus für den kürzesten Weg und führte ihn später für ARMAC für eine leicht verkürzte Verkehrskarte von 64 Städten in den Niederlanden aus (64 Städte, also würden 6 Bits ausreichen, um die Stadtnummer zu kodieren). Ein Jahr später stieß er auf ein weiteres Problem von Hardware-Ingenieuren, die den nächsten Computer des Instituts bedienten: Minimieren Sie die Menge an Kabeln, die zum Verbinden der Pins auf der Rückseite der Maschine erforderlich sind. Als Lösung entdeckte er den Algorithmus namens Prims minimaler Spannbaumalgorithmus wieder und veröffentlichte ihn im Jahr 1959.

Grundlagen des Dijkstra-Algorithmus

Im Folgenden sind die Grundkonzepte des Dijkstra-Algorithmus aufgeführt:

1. Der Dijkstra-Algorithmus beginnt an dem von uns ausgewählten Knoten (dem Quellknoten) und untersucht den Graphen, um den kürzesten Weg zwischen diesem Knoten und allen anderen Knoten im Graphen zu finden.
2. Der Algorithmus zeichnet die aktuell anerkannte kürzeste Entfernung von jedem Knoten zum Quellknoten auf und aktualisiert diese Werte, wenn er einen kürzeren Weg findet.
3. Sobald der Algorithmus den kürzesten Pfad zwischen der Quelle und einem anderen Knoten ermittelt hat, wird dieser Knoten als „besucht“ markiert und in den Pfad aufgenommen.
4. Der Vorgang wird fortgesetzt, bis alle Knoten im Diagramm in den Pfad einbezogen wurden. Auf diese Weise haben wir einen Pfad, der den Quellknoten mit allen anderen Knoten verbindet und dem kürzestmöglichen Weg folgt, um jeden Knoten zu erreichen.

Die Funktionsweise des Dijkstra-Algorithmus verstehen

A Graph Und Quellscheitelpunkt sind Anforderungen für den Dijkstra-Algorithmus. Dieser Algorithmus basiert auf dem Greedy-Ansatz und findet somit bei jedem Schritt des Algorithmus die lokal optimale Wahl (in diesem Fall lokale Minima).

Für jeden Scheitelpunkt in diesem Algorithmus sind zwei Eigenschaften definiert:

1. Besichtigte Immobilie
2. Path-Eigenschaft

Lassen Sie uns diese Eigenschaften kurz verstehen.

Besichtigtes Objekt:

1. Die Eigenschaft „visited“ gibt an, ob der Knoten besucht wurde oder nicht.
2. Wir verwenden diese Eigenschaft, damit wir keinen Knoten erneut besuchen.
3. Ein Knoten wird nur dann als besucht markiert, wenn der kürzeste Weg gefunden wurde.

Pfadeigenschaft:

1. Die Eigenschaft „Pfad“ speichert den Wert des aktuellen Mindestpfads zum Knoten.
2. Der aktuelle minimale Pfad impliziert den kürzesten Weg, den wir bisher zu diesem Knoten erreicht haben.
3. Diese Eigenschaft wird überarbeitet, wenn ein Nachbar des Knotens besucht wird.
4. Diese Eigenschaft ist wichtig, da sie die endgültige Antwort für jeden Knoten speichert.

Zunächst markieren wir alle Scheitelpunkte oder Knoten als nicht besucht, da sie noch besucht werden müssen. Der Pfad zu allen Knoten außer dem Quellknoten ist ebenfalls auf unendlich festgelegt. Darüber hinaus wird der Pfad zum Quellknoten auf Null (0) gesetzt.

Anschließend wählen wir den Quellknoten aus und markieren ihn als besucht. Danach greifen wir auf alle Nachbarknoten des Quellknotens zu und führen auf jedem Knoten eine Entspannung durch. Entspannung ist der Prozess, bei dem die Kosten für das Erreichen eines Knotens mithilfe eines anderen Knotens gesenkt werden.

Im Entspannungsprozess wird der Pfad jedes Knotens auf den Minimalwert aus dem aktuellen Pfad des Knotens, der Summe des Pfads zum vorherigen Knoten und dem Pfad vom vorherigen Knoten zum aktuellen Knoten korrigiert.

Nehmen wir an, dass p[n] der Wert des aktuellen Pfads für Knoten n ist, p[m] der Wert des Pfads bis zum zuvor besuchten Knoten m ist und w das Gewicht der Kante zwischen dem aktuellen Knoten und ist zuvor besuchtes (Kantengewicht zwischen n und m).

wie man string in int ändert

Im mathematischen Sinne lässt sich Entspannung wie folgt darstellen:

p[n] = Minimum(p[n], p[m] + w)

Anschließend markieren wir in jedem weiteren Schritt einen nicht besuchten Knoten mit dem geringsten Pfad als besucht und aktualisieren die Pfade seiner Nachbarn.

Wir wiederholen diesen Vorgang, bis alle Knoten im Diagramm als besucht markiert sind.

Immer wenn wir der besuchten Menge einen Knoten hinzufügen, ändert sich auch der Pfad zu allen benachbarten Knoten entsprechend.

Wenn ein Knoten unerreichbar bleibt (nicht verbundene Komponente), bleibt sein Pfad „unendlich“. Falls die Quelle selbst eine separate Komponente ist, bleibt der Pfad zu allen anderen Knoten „unendlich“.

Den Dijkstra-Algorithmus anhand eines Beispiels verstehen

Der folgende Schritt wird durchgeführt, um den Dijkstra-Algorithmus zu implementieren:

Schritt 1: Zuerst markieren wir den Quellknoten mit einem aktuellen Abstand von 0 und setzen die restlichen Knoten auf UNENDLICH.

Schritt 2: Wir werden dann den nicht besuchten Knoten mit der kleinsten aktuellen Entfernung als aktuellen Knoten festlegen, angenommen X.

Schritt 3: Für jeden Nachbarn N des aktuellen Knotens X: Wir addieren dann den aktuellen Abstand von X mit dem Gewicht der X-N verbindenden Kante. Wenn er kleiner als der aktuelle Abstand von N ist, legen Sie ihn als neuen aktuellen Abstand von N fest.

Schritt 4: Wir markieren dann den aktuellen Knoten X als besucht.

Schritt 5: Wir werden den Vorgang ab wiederholen 'Schritt 2' ob im Diagramm noch ein Knoten vorhanden ist, der noch nicht besucht wurde.

Lassen Sie uns nun die Implementierung des Algorithmus anhand eines Beispiels verstehen:

Abbildung 6: Der gegebene Graph

1. Wir werden das obige Diagramm mit Knoten als Eingabe verwenden A als Quelle.
2. Zuerst markieren wir alle Knoten als nicht besucht.
3. Wir legen den Weg fest 0 am Knoten A Und UNENDLICHKEIT für alle anderen Knoten.
4. Wir werden nun den Quellknoten markieren A wie besucht und auf seine Nachbarknoten zugreifen.
   Notiz: Wir haben nur auf die benachbarten Knoten zugegriffen, sie nicht besucht.
5. Wir werden nun den Pfad zum Knoten aktualisieren B von 4 mit Hilfe der Entspannung, weil der Weg zum Knoten A Ist 0 und der Pfad vom Knoten A Zu B Ist 4 , und das Minimum((0 + 4), UNENDLICH) Ist 4 .
6. Wir werden auch den Pfad zum Knoten aktualisieren C von 5 mit Hilfe der Entspannung, weil der Weg zum Knoten A Ist 0 und der Pfad vom Knoten A Zu C Ist 5 , und das Minimum((0 + 5), UNENDLICH) Ist 5 . Beide Nachbarn des Knotens A sind jetzt entspannt; Daher können wir weitermachen.
7. Wir werden nun den nächsten nicht besuchten Knoten mit dem geringsten Pfad auswählen und ihn besuchen. Daher werden wir den Knoten besuchen B und entspanne seine unbesuchten Nachbarn. Nach der Durchführung der Entspannung erfolgt der Weg zum Knoten C wird bleiben 5 , während der Pfad zum Knoten UND wird werden elf und der Pfad zum Knoten D wird werden 13 .
8. Wir werden jetzt den Knoten besuchen UND und führen Sie eine Entspannung an den benachbarten Knoten durch B, D , Und F . Da nur Knoten F ist unbesucht, es wird entspannt. Somit der Pfad zum Knoten B bleibt so wie es ist, d.h. 4 , der Pfad zum Knoten D wird auch bleiben 13 und der Pfad zum Knoten F wird werden 14 (8 + 6) .
9. Jetzt besuchen wir den Knoten D , und nur Knoten F wird entspannt sein. Allerdings ist der Pfad zum Knoten F bleibt unverändert, d.h. 14 .
10. Da nur Knoten F verbleibt, werden wir ihn besuchen, aber keine Entspannung durchführen, da alle benachbarten Knoten bereits besucht sind.
11. Sobald alle Knoten der Diagramme besucht wurden, wird das Programm beendet.

Daher sind die endgültigen Pfade, zu denen wir gekommen sind:

 A = 0 B = 4 (A -> B) C = 5 (A -> C) D = 4 + 9 = 13 (A -> B -> D) E = 5 + 3 = 8 (A -> C -> E) F = 5 + 3 + 6 = 14 (A -> C -> E -> F) 

Pseudocode für Dijkstras Algorithmus

Wir werden nun einen Pseudocode für Dijkstras Algorithmus verstehen.

• Wir müssen die Pfadentfernung jedes Knotens protokollieren. Daher können wir die Pfadentfernung jedes Knotens in einem Array der Größe n speichern, wobei n die Gesamtzahl der Knoten ist.
• Darüber hinaus möchten wir den kürzesten Pfad zusammen mit der Länge dieses Pfads ermitteln. Um dieses Problem zu lösen, ordnen wir jeden Knoten dem Knoten zu, der seine Pfadlänge zuletzt aktualisiert hat.
• Sobald der Algorithmus abgeschlossen ist, können wir den Zielknoten zum Quellknoten zurückverfolgen, um den Pfad abzurufen.
• Wir können eine Warteschlange mit minimaler Priorität verwenden, um den Knoten mit der geringsten Pfadentfernung auf effiziente Weise abzurufen.

Lassen Sie uns nun einen Pseudocode der obigen Abbildung implementieren:

einfaches Java-Programm

Pseudocode:

 function Dijkstra_Algorithm(Graph, source_node) // iterating through the nodes in Graph and set their distances to INFINITY for each node N in Graph: distance[N] = INFINITY previous[N] = NULL If N != source_node, add N to Priority Queue G // setting the distance of the source node of the Graph to 0 distance[source_node] = 0 // iterating until the Priority Queue G is not empty while G is NOT empty: // selecting a node Q having the least distance and marking it as visited Q = node in G with the least distance[] mark Q visited // iterating through the unvisited neighboring nodes of the node Q and performing relaxation accordingly for each unvisited neighbor node N of Q: temporary_distance = distance[Q] + distance_between(Q, N) // if the temporary distance is less than the given distance of the path to the Node, updating the resultant distance with the minimum value if temporary_distance <distance[n] distance[n] :="temporary_distance" previous[n] returning the final list of distance return distance[], previous[] < pre> <p> <strong>Explanation:</strong> </p> <p>In the above pseudocode, we have defined a function that accepts multiple parameters - the Graph consisting of the nodes and the source node. Inside this function, we have iterated through each node in the Graph, set their initial distance to <strong>INFINITY</strong> , and set the previous node value to <strong>NULL</strong> . We have also checked whether any selected node is not a source node and added the same into the Priority Queue. Moreover, we have set the distance of the source node to <strong>0</strong> . We then iterated through the nodes in the priority queue, selected the node with the least distance, and marked it as visited. We then iterated through the unvisited neighboring nodes of the selected node and performed relaxation accordingly. At last, we have compared both the distances (original and temporary distance) between the source node and the destination node, updated the resultant distance with the minimum value and previous node information, and returned the final list of distances with their previous node information.</p> <h2>Implementation of Dijkstra&apos;s Algorithm in Different Programming Languages</h2> <p>Now that we have successfully understood the pseudocode of Dijkstra&apos;s Algorithm, it is time to see its implementation in different programming languages like C, C++, Java, and Python.</p> <h3>Code for Dijkstra&apos;s Algorithm in C</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the C Programming Language:</p> <p> <strong>File: DijkstraAlgorithm.c</strong> </p> <pre> // Implementation of Dijkstra&apos;s Algorithm in C // importing the standard I/O header file #include // defining some constants #define INF 9999 #define MAX 10 // prototyping of the function void DijkstraAlgorithm(int Graph[MAX][MAX], int size, int start); // defining the function for Dijkstra&apos;s Algorithm void DijkstraAlgorithm(int Graph[MAX][MAX], int size, int start) { int cost[MAX][MAX], distance[MAX], previous[MAX]; int visited_nodes[MAX], counter, minimum_distance, next_node, i, j; // creating cost matrix for (i = 0; i <size; i++) for (j="0;" j < size; j++) if (graph[i][j]="=" 0) cost[i][j]="INF;" else (i="0;" i { distance[i]="cost[start][i];" previous[i]="start;" visited_nodes[i]="0;" } distance[start]="0;" visited_nodes[start]="1;" counter="1;" while (counter size - 1) minimum_distance="INF;" (distance[i] && !visited_nodes[i]) next_node="i;" visited_nodes[next_node]="1;" (!visited_nodes[i]) (minimum_distance + cost[next_node][i] distance[i]) cost[next_node][i]; counter++; printing the distance !="start)" printf('
distance from source node to %d: %d', i, distance[i]); main function int main() defining variables graph[max][max], j, size, source; declaring of matrix nodes graph graph[0][0]="0;" graph[0][1]="4;" graph[0][2]="0;" graph[0][3]="0;" graph[0][4]="0;" graph[0][5]="8;" graph[0][6]="0;" graph[1][0]="4;" graph[1][1]="0;" graph[1][2]="8;" graph[1][3]="0;" graph[1][4]="0;" graph[1][5]="11;" graph[1][6]="0;" graph[2][0]="0;" graph[2][1]="8;" graph[2][2]="0;" graph[2][3]="7;" graph[2][4]="0;" graph[2][5]="4;" graph[2][6]="0;" graph[3][0]="0;" graph[3][1]="0;" graph[3][2]="7;" graph[3][3]="0;" graph[3][4]="9;" graph[3][5]="14;" graph[3][6]="0;" graph[4][0]="0;" graph[4][1]="0;" graph[4][2]="0;" graph[4][3]="9;" graph[4][4]="0;" graph[4][5]="10;" graph[4][6]="2;" graph[5][0]="0;" graph[5][1]="0;" graph[5][2]="4;" graph[5][3]="14;" graph[5][4]="10;" graph[5][5]="0;" graph[5][6]="2;" graph[6][0]="0;" graph[6][1]="0;" graph[6][2]="0;" graph[6][3]="0;" graph[6][4]="2;" graph[6][5]="0;" graph[6][6]="1;" calling dijkstraalgorithm() by passing graph, number and dijkstraalgorithm(graph, source); return 0; pre> <p> <strong>Output</strong> </p> <pre> Distance from the Source Node to 1: 4 Distance from the Source Node to 2: 12 Distance from the Source Node to 3: 19 Distance from the Source Node to 4: 12 Distance from the Source Node to 5: 8 Distance from the Source Node to 6: 10 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have included the <strong>stdio.h</strong> header file defined two constant values: <strong>INF = 9999</strong> and <strong>MAX = 10</strong> . We have declared the prototyping of the function and then defined the function for Dijkstra&apos;s Algorithm as <strong>DijkstraAlgorithm</strong> that accepts three arguments - the Graph consisting of the nodes, the number of nodes in the Graph, and the source node. Inside this function, we have defined some data structures such as a 2D matrix that will work as the Priority Queue for the algorithm, an array to main the distance between the nodes, an array to maintain the record of previous nodes, an array to store the visited nodes information, and some integer variables to store minimum distance value, counter, next node value and more. We then used a <strong>nested for-loop</strong> to iterate through the nodes of the Graph and add them to the priority queue accordingly. We have again used the <strong>for-loop</strong> to iterate through the elements in the priority queue starting from the source node and update their distances. Outside the loop, we have set the distance of the source node as <strong>0</strong> and marked it as visited in the <strong>visited_nodes[]</strong> array. We then set the counter value as one and used the <strong>while</strong> loop iterating through the number of nodes. Inside this loop, we have set the value of <strong>minimum_distance</strong> as <strong>INF</strong> and used the <strong>for-loop</strong> to update the value of the <strong>minimum_distance</strong> variable with the minimum value from a <strong>distance[]</strong> array. We then iterated through the unvisited neighboring nodes of the selected node using the <strong>for-loop</strong> and performed relaxation. We then printed the resulting data of the distances calculated using Dijkstra&apos;s Algorithm.</p> <p>In the <strong>main</strong> function, we have defined and declared the variables representing the Graph, the number of nodes, and the source node. At last, we have called the <strong>DijkstraAlgorithm()</strong> function by passing the required parameters.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h3>Code for Dijkstra&apos;s Algorithm in C++</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the C++ Programming Language:</p> <p> <strong>File: DijkstraAlgorithm.cpp</strong> </p> <pre> // Implementation of Dijkstra&apos;s Algorithm in C++ // importing the required header files #include #include // defining constant #define MAX_INT 10000000 // using the standard namespace using namespace std; // prototyping of the DijkstraAlgorithm() function void DijkstraAlgorithm(); // main function int main() { DijkstraAlgorithm(); return 0; } // declaring the classes class Vertex; class Edge; // prototyping the functions void Dijkstra(); vector* Adjacent_Remaining_Nodes(Vertex* vertex); Vertex* Extract_Smallest(vector&amp; vertices); int Distance(Vertex* vertexOne, Vertex* vertexTwo); bool Contains(vector&amp; vertices, Vertex* vertex); void Print_Shortest_Route_To(Vertex* des); // instantiating the classes vector vertices; vector edges; // defining the class for the vertices of the graph class Vertex { public: Vertex(char id) : id(id), prev(NULL), distance_from_start(MAX_INT) { vertices.push_back(this); } public: char id; Vertex* prev; int distance_from_start; }; // defining the class for the edges of the graph class Edge { public: Edge(Vertex* vertexOne, Vertex* vertexTwo, int distance) : vertexOne(vertexOne), vertexTwo(vertexTwo), distance(distance) { edges.push_back(this); } bool Connects(Vertex* vertexOne, Vertex* vertexTwo) public: Vertex* vertexOne; Vertex* vertexTwo; int distance; }; // defining the function to collect the details of the graph void DijkstraAlgorithm() { // declaring some vertices Vertex* vertex_a = new Vertex(&apos;A&apos;); Vertex* vertex_b = new Vertex(&apos;B&apos;); Vertex* vertex_c = new Vertex(&apos;C&apos;); Vertex* vertex_d = new Vertex(&apos;D&apos;); Vertex* vertex_e = new Vertex(&apos;E&apos;); Vertex* vertex_f = new Vertex(&apos;F&apos;); Vertex* vertex_g = new Vertex(&apos;G&apos;); // declaring some edges Edge* edge_1 = new Edge(vertex_a, vertex_c, 1); Edge* edge_2 = new Edge(vertex_a, vertex_d, 2); Edge* edge_3 = new Edge(vertex_b, vertex_c, 2); Edge* edge_4 = new Edge(vertex_c, vertex_d, 1); Edge* edge_5 = new Edge(vertex_b, vertex_f, 3); Edge* edge_6 = new Edge(vertex_c, vertex_e, 3); Edge* edge_7 = new Edge(vertex_e, vertex_f, 2); Edge* edge_8 = new Edge(vertex_d, vertex_g, 1); Edge* edge_9 = new Edge(vertex_g, vertex_f, 1); vertex_a -&gt; distance_from_start = 0; // setting a start vertex // calling the Dijkstra() function to find the shortest route possible Dijkstra(); // calling the Print_Shortest_Route_To() function to print the shortest route from the source vertex to the destination vertex Print_Shortest_Route_To(vertex_f); } // defining the function for Dijkstra&apos;s Algorithm void Dijkstra() { while (vertices.size() &gt; 0) { Vertex* smallest = Extract_Smallest(vertices); vector* adjacent_nodes = Adjacent_Remaining_Nodes(smallest); const int size = adjacent_nodes -&gt; size(); for (int i = 0; i at(i); int distance = Distance(smallest, adjacent) + smallest -&gt; distance_from_start; if (distance distance_from_start) { adjacent -&gt; distance_from_start = distance; adjacent -&gt; prev = smallest; } } delete adjacent_nodes; } } // defining the function to find the vertex with the shortest distance, removing it, and returning it Vertex* Extract_Smallest(vector&amp; vertices) { int size = vertices.size(); if (size == 0) return NULL; int smallest_position = 0; Vertex* smallest = vertices.at(0); for (int i = 1; i distance_from_start distance_from_start) { smallest = current; smallest_position = i; } } vertices.erase(vertices.begin() + smallest_position); return smallest; } // defining the function to return all vertices adjacent to &apos;vertex&apos; which are still in the &apos;vertices&apos; collection. vector* Adjacent_Remaining_Nodes(Vertex* vertex) { vector* adjacent_nodes = new vector(); const int size = edges.size(); for (int i = 0; i vertexOne == vertex) { adjacent = edge -&gt; vertexTwo; } else if (edge -&gt; vertexTwo == vertex) { adjacent = edge -&gt; vertexOne; } if (adjacent &amp;&amp; Contains(vertices, adjacent)) { adjacent_nodes -&gt; push_back(adjacent); } } return adjacent_nodes; } // defining the function to return distance between two connected vertices int Distance(Vertex* vertexOne, Vertex* vertexTwo) { const int size = edges.size(); for (int i = 0; i Connects(vertexOne, vertexTwo)) { return edge -&gt; distance; } } return -1; // should never happen } // defining the function to check if the &apos;vertices&apos; vector contains &apos;vertex&apos; bool Contains(vector&amp; vertices, Vertex* vertex) { const int size = vertices.size(); for (int i = 0; i <size; ++i) { if (vertex="=" vertices.at(i)) return true; } false; defining the function to print shortest route destination void print_shortest_route_to(vertex* des) vertex* prev="des;" cout << 'distance from start: ' < distance_from_start endl; while (prev) id prev; pre> <p> <strong>Output</strong> </p> <pre> Distance from start: 4 F G D A </pre> <p> <strong>Explanation:</strong> </p> <p>In the above code snippet, we included the <strong>&apos;iostream&apos;</strong> and <strong>&apos;vector&apos;</strong> header files and defined a constant value as <strong>MAX_INT = 10000000</strong> . We then used the standard namespace and prototyped the <strong>DijkstraAlgorithm()</strong> function. We then defined the main function of the program within, which we have called the <strong>DijkstraAlgorithm()</strong> function. After that, we declared some classes to create vertices and edges. We have also prototyped more functions to find the shortest possible path from the source vertex to the destination vertex and instantiated the Vertex and Edge classes. We then defined both classes to create the vertices and edges of the graph. We have then defined the <strong>DijkstraAlgorithm()</strong> function to create a graph and perform different operations. Inside this function, we have declared some vertices and edges. We then set the source vertex of the graph and called the <strong>Dijkstra()</strong> function to find the shortest possible distance and <strong>Print_Shortest_Route_To()</strong> function to print the shortest distance from the source vertex to vertex <strong>&apos;F&apos;</strong> . We have then defined the <strong>Dijkstra()</strong> function to calculate the shortest possible distances of the all the vertices from the source vertex. We have also defined some more functions to find the vertex with the shortest distance to return all the vertices adjacent to the remaining vertex, to return the distance between two connected vertices, to check if the selected vertex exists in the graph, and to print the shortest possible path from the source vertex to the destination vertex.</p> <p>As a result, the required shortest path for the vertex <strong>&apos;F&apos;</strong> from the source node is printed for the users.</p> <h3>Code for Dijkstra&apos;s Algorithm in Java</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the Java Programming Language:</p> <p> <strong>File: DijkstraAlgorithm.java</strong> </p> <pre> // Implementation of Dijkstra&apos;s Algorithm in Java // defining the public class for Dijkstra&apos;s Algorithm public class DijkstraAlgorithm { // defining the method to implement Dijkstra&apos;s Algorithm public void dijkstraAlgorithm(int[][] graph, int source) { // number of nodes int nodes = graph.length; boolean[] visited_vertex = new boolean[nodes]; int[] dist = new int[nodes]; for (int i = 0; i <nodes; 0 1 i++) { visited_vertex[i]="false;" dist[i]="Integer.MAX_VALUE;" } distance of self loop is zero dist[source]="0;" for (int i="0;" < nodes; updating the between neighboring vertex and source int u="find_min_distance(dist," visited_vertex); visited_vertex[u]="true;" distances all vertices v="0;" v++) if (!visited_vertex[v] && graph[u][v] !="0" (dist[u] + dist[v])) dist[v]="dist[u]" graph[u][v]; dist.length; system.out.println(string.format('distance from %s to %s', source, i, dist[i])); defining method find minimum private static find_min_distance(int[] dist, boolean[] visited_vertex) minimum_distance="Integer.MAX_VALUE;" minimum_distance_vertex="-1;" (!visited_vertex[i] minimum_distance) return minimum_distance_vertex; main function public void main(string[] args) declaring nodes graphs graph[][]="new" int[][] 0, 1, 2, }, 3, }; instantiating dijkstraalgorithm() class dijkstraalgorithm test="new" dijkstraalgorithm(); calling shortest node destination test.dijkstraalgorithm(graph, 0); pre> <p> <strong>Output</strong> </p> <pre> Distance from Vertex 0 to Vertex 0 is 0 Distance from Vertex 0 to Vertex 1 is 1 Distance from Vertex 0 to Vertex 2 is 1 Distance from Vertex 0 to Vertex 3 is 2 Distance from Vertex 0 to Vertex 4 is 4 Distance from Vertex 0 to Vertex 5 is 4 Distance from Vertex 0 to Vertex 6 is 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have defined a public class as <strong>DijkstraAlgorithm()</strong> . Inside this class, we have defined a public method as <strong>dijkstraAlgorithm()</strong> to find the shortest distance from the source vertex to the destination vertex. Inside this method, we have defined a variable to store the number of nodes. We have then defined a Boolean array to store the information regarding the visited vertices and an integer array to store their respective distances. Initially, we declared the values in both the arrays as <strong>False</strong> and <strong>MAX_VALUE</strong> , respectively. We have also set the distance of the source vertex as zero and used the <strong>for-loop</strong> to update the distance between the source vertex and destination vertices with the minimum distance. We have then updated the distances of the neighboring vertices of the selected vertex by performing relaxation and printed the shortest distances for every vertex. We have then defined a method to find the minimum distance from the source vertex to the destination vertex. We then defined the main function where we declared the vertices of the graph and instantiated the <strong>DijkstraAlgorithm()</strong> class. Finally, we have called the <strong>dijkstraAlgorithm()</strong> method to find the shortest distance between the source vertex and the destination vertices.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h3>Code for Dijkstra&apos;s Algorithm in Python</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the Python Programming Language:</p> <p> <strong>File: DikstraAlgorithm.py</strong> </p> <pre> # Implementation of Dijkstra&apos;s Algorithm in Python # importing the sys module import sys # declaring the list of nodes for the graph nodes = [ [0, 0, 1, 0, 1, 0, 0], [0, 0, 1, 0, 0, 1, 0], [1, 1, 0, 1, 1, 0, 0], [1, 0, 1, 0, 0, 0, 1], [0, 0, 1, 0, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # declaring the list of edges for the graph edges = [ [0, 0, 1, 0, 2, 0, 0], [0, 0, 2, 0, 0, 3, 0], [1, 2, 0, 1, 3, 0, 0], [2, 0, 1, 0, 0, 0, 1], [0, 0, 3, 0, 0, 2, 0], [0, 3, 0, 0, 2, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # defining the function to find which node is to be visited next def toBeVisited(): global visitedAndDistance v = -10 for index in range(numberOfNodes): if visitedAndDistance[index][0] == 0 and (v <0 1 or visitedanddistance[index][1] <="visitedAndDistance[v][1]):" v="index" return # finding the number of nodes in graph numberofnodes="len(nodes[0])" visitedanddistance="[[0," 0]] for i range(numberofnodes - 1): visitedanddistance.append([0, sys.maxsize]) node range(numberofnodes): next to be visited tovisit="toBeVisited()" neighborindex updating new distances if nodes[tovisit][neighborindex]="=" and visitedanddistance[neighborindex][0]="=" 0: newdistance="visitedAndDistance[toVisit][1]" + edges[tovisit][neighborindex] visitedanddistance[neighborindex][1]> newDistance: visitedAndDistance[neighborIndex][1] = newDistance visitedAndDistance[toVisit][0] = 1 i = 0 # printing the distance for distance in visitedAndDistance: print(&apos;Distance of&apos;, chr(ord(&apos;A&apos;) + i), &apos;from source node:&apos;, distance[1]) i = i + 1 </0></pre> <p> <strong>Output</strong> </p> <pre> Distance of A from source node: 0 Distance of B from source node: 3 Distance of C from source node: 1 Distance of D from source node: 2 Distance of E from source node: 2 Distance of F from source node: 4 Distance of G from source node: 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have imported the <strong>sys</strong> module and declared the lists consisting of the values for the nodes and edges. We have then defined a function as <strong>toBeVisited()</strong> to find which node will be visited next. We then found the total number of nodes in the graph and set the initial distances for every node. We have then calculated the minimum distance from the source node to the destination node, performed relaxation on neighboring nodes, and updated the distances in the list. We then printed those distances from the list for the users.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h2>Time and Space Complexity of Dijkstra&apos;s Algorithm</h2> <ul> <li>The Time Complexity of Dijkstra&apos;s Algorithm is <strong>O(E log V)</strong> , where E is the number of edges and V is the number of vertices.</li> <li>The Space Complexity of Dijkstra&apos;s Algorithm is O(V), where V is the number of vertices.</li> </ul> <h2>Advantages and Disadvantages of Dijkstra&apos;s Algorithm</h2> <p> <strong>Let us discuss some advantages of Dijkstra&apos;s Algorithm:</strong> </p> <ol class="points"> <li>One primary advantage of using Dijkstra&apos;s Algorithm is that it has an almost linear time and space complexity.</li> <li>We can use this algorithm to calculate the shortest path from a single vertex to all other vertices and a single source vertex to a single destination vertex by stopping the algorithm once we get the shortest distance for the destination vertex.</li> <li>This algorithm only works for directed weighted graphs, and all the edges of this graph should be non-negative.</li> </ol> <p> <strong>Despite having multiple advantages, Dijkstra&apos;s algorithm has some disadvantages also, such as:</strong> </p> <ol class="points"> <li>Dijkstra&apos;s Algorithm performs a concealed exploration that utilizes a lot of time during the process.</li> <li>This algorithm is impotent to handle negative edges.</li> <li>Since this algorithm heads to the acyclic graph, it cannot calculate the exact shortest path.</li> <li>It also requires maintenance to keep a record of vertices that have been visited.</li> </ol> <h2>Some Applications of Dijkstra&apos;s Algorithm</h2> <p> <strong>Dijkstra&apos;s Algorithm has various real-world applications, some of which are stated below:</strong> </p> <ol class="points"> <tr><td>Digital Mapping Services in Google Maps:</td> There are various times when we have tried to find the distance in Google Maps either from our location to the nearest preferred location or from one city to another, which comprises multiple routes/paths connecting them; however, the application must display the minimum distance. This is only possible because Dijkstra&apos;s algorithm helps the application find the shortest between two given locations along the path. Let us consider the USA as a graph wherein the cities/places are represented as vertices, and the routes between two cities/places are represented as edges. Then with the help of Dijkstra&apos;s Algorithm, we can calculate the shortest routes between any two cities/places. </tr><tr><td>Social Networking Applications:</td> In many applications like Facebook, Twitter, Instagram, and more, many of us might have observed that these apps suggest the list of friends that a specific user may know. How do many social media companies implement this type of feature in an efficient and effective way, specifically when the system has over a billion users? The answer to this question is Dijkstra&apos;s Algorithm. The standard Dijkstra&apos;s Algorithm is generally used to estimate the shortest distance between the users measured through the connections or mutuality among them. When social networking is very small, it uses the standard Dijkstra&apos;s Algorithm in addition to some other features in order to determine the shortest paths. However, when the graph is much bigger, the standard algorithm takes several seconds to count, and thus, some advanced algorithms are used as the alternative. </tr><tr><td>Telephone Network:</td> As some of us might know, in a telephone network, each transmission line has a bandwidth, &apos;b&apos;. The bandwidth is the highest frequency that the transmission line can support. In general, if the frequency of the signal is higher in a specific line, the signal is reduced by that line. Bandwidth represents the amount of information that can be transmitted by the line. Let us consider a city a graph wherein the switching stations are represented using the vertices, the transmission lines are represented as the edges, and the bandwidth, &apos;b&apos;, is represented using the weight of the edges. Thus, as we can observe, the telephone network can also fall into the category of the shortest distance problem and can be solved using Dijkstra&apos;s Algorithm. </tr><tr><td>Flight Program:</td> Suppose that a person requires software to prepare an agenda of flights for customers. The agent has access to a database with all flights and airports. In addition to the flight number, origin airport, and destination, the flights also have departure and arrival times. So, in order to determine the earliest arrival time for the selected destination from the original airport and given start time, the agents make use of Dijkstra&apos;s Algorithm. </tr><tr><td>IP routing to find Open Shortest Path First:</td> Open Shortest Path First (abbreviated as OSPF) is a link-state routing protocol used to find the best path between the source and destination router with the help of its own Shortest Path First. Dijkstra&apos;s Algorithm is extensively utilized in the routing protocols required by the routers in order to update their forwarding table. The algorithm gives the shortest cost path from the source router to the other routers present in the network. </tr><tr><td>Robotic Path:</td> These days, drones and robots have come into existence, some operated manually and some automatically. The drones and robots which are operated automatically and used to deliver the packages to a given location or used for any certain task are configured with Dijkstra&apos;s Algorithm module so that whenever the source and destination are known, the drone and robot will move in the ordered direction by following the shortest path keeping the time taken to a minimum in order to deliver the packages. </tr><tr><td>Designate the File Server:</td> Dijkstra&apos;s Algorithm is also used to designate a file server in a Local Area Network (LAN). Suppose that an infinite period of time is needed for the transmission of the files from one computer to another. So, to minimize the number of &apos;hops&apos; from the file server to every other computer on the network, we will use Dijkstra&apos;s Algorithm. This algorithm will return the shortest path between the networks resulting in the minimum number of hops. </tr></ol> <h2>The Conclusion</h2> <ul> <li>In the above tutorial, firstly, we have understood the basic concepts of Graph along with its types and applications.</li> <li>We then learned about Dijkstra&apos;s Algorithm and its history.</li> <li>We have also understood the fundamental working of Dijkstra&apos;s Algorithm with the help of an example.</li> <li>After that, we studied how to write code for Dijkstra&apos;s Algorithm with the help of Pseudocode.</li> <li>We observed its implementation in programming languages like C, C++, Java, and Python with proper outputs and explanations.</li> <li>We have also understood the Time and Space Complexity of Dijkstra&apos;s Algorithm.</li> <li>Finally, we have discussed the advantages and disadvantages of Dijkstra&apos;s algorithm and some of its real-life applications.</li> </ul> <hr></nodes;></pre></size;></pre></size;></pre></distance[n]>

Erläuterung:

Im obigen Codeausschnitt haben wir Folgendes eingefügt stdio.h Die Header-Datei definiert zwei konstante Werte: INF = 9999 Und MAX = 10 . Wir haben das Prototyping der Funktion deklariert und dann die Funktion für den Dijkstra-Algorithmus definiert als DijkstraAlgorithmus das drei Argumente akzeptiert: den aus den Knoten bestehenden Graphen, die Anzahl der Knoten im Graphen und den Quellknoten. Innerhalb dieser Funktion haben wir einige Datenstrukturen definiert, z. B. eine 2D-Matrix, die als Prioritätswarteschlange für den Algorithmus fungiert, ein Array zum Festlegen des Abstands zwischen den Knoten, ein Array zum Verwalten der Aufzeichnung vorheriger Knoten und ein Array zum Speichern die Informationen zu den besuchten Knoten und einige ganzzahlige Variablen zum Speichern des Mindestabstandswerts, des Zählers, des nächsten Knotenwerts und mehr. Wir haben dann eine verwendet verschachtelte for-Schleife um die Knoten des Diagramms zu durchlaufen und sie entsprechend zur Prioritätswarteschlange hinzuzufügen. Wir haben das wieder genutzt for-Schleife um die Elemente in der Prioritätswarteschlange ausgehend vom Quellknoten zu durchlaufen und ihre Abstände zu aktualisieren. Außerhalb der Schleife haben wir den Abstand des Quellknotens auf festgelegt 0 und markierte es als besucht im besuchte_knoten[] Array. Wir haben dann den Zählerwert auf eins gesetzt und verwendet während Schleife, die die Anzahl der Knoten durchläuft. Innerhalb dieser Schleife haben wir den Wert von festgelegt minimale_Entfernung als INF und benutzte die for-Schleife um den Wert zu aktualisieren minimale_Entfernung Variable mit dem Minimalwert von a Distanz[] Array. Anschließend haben wir mithilfe von die nicht besuchten Nachbarknoten des ausgewählten Knotens durchlaufen for-Schleife und Entspannung durchgeführt. Anschließend haben wir die resultierenden Daten der mit dem Dijkstra-Algorithmus berechneten Entfernungen ausgedruckt.

Im hauptsächlich Mit der Funktion haben wir die Variablen definiert und deklariert, die den Graphen, die Anzahl der Knoten und den Quellknoten darstellen. Endlich haben wir das angerufen DijkstraAlgorithmus() Funktion durch Übergabe der erforderlichen Parameter.

Dadurch werden den Benutzern für jeden Knoten vom Quellknoten aus die erforderlichen kürzestmöglichen Pfade ausgedruckt.

Code für Dijkstras Algorithmus in C++

Das Folgende ist die Implementierung des Dijkstra-Algorithmus in der Programmiersprache C++:

Datei: DijkstraAlgorithm.cpp

 // Implementation of Dijkstra&apos;s Algorithm in C++ // importing the required header files #include #include // defining constant #define MAX_INT 10000000 // using the standard namespace using namespace std; // prototyping of the DijkstraAlgorithm() function void DijkstraAlgorithm(); // main function int main() { DijkstraAlgorithm(); return 0; } // declaring the classes class Vertex; class Edge; // prototyping the functions void Dijkstra(); vector* Adjacent_Remaining_Nodes(Vertex* vertex); Vertex* Extract_Smallest(vector&amp; vertices); int Distance(Vertex* vertexOne, Vertex* vertexTwo); bool Contains(vector&amp; vertices, Vertex* vertex); void Print_Shortest_Route_To(Vertex* des); // instantiating the classes vector vertices; vector edges; // defining the class for the vertices of the graph class Vertex { public: Vertex(char id) : id(id), prev(NULL), distance_from_start(MAX_INT) { vertices.push_back(this); } public: char id; Vertex* prev; int distance_from_start; }; // defining the class for the edges of the graph class Edge { public: Edge(Vertex* vertexOne, Vertex* vertexTwo, int distance) : vertexOne(vertexOne), vertexTwo(vertexTwo), distance(distance) { edges.push_back(this); } bool Connects(Vertex* vertexOne, Vertex* vertexTwo) public: Vertex* vertexOne; Vertex* vertexTwo; int distance; }; // defining the function to collect the details of the graph void DijkstraAlgorithm() { // declaring some vertices Vertex* vertex_a = new Vertex(&apos;A&apos;); Vertex* vertex_b = new Vertex(&apos;B&apos;); Vertex* vertex_c = new Vertex(&apos;C&apos;); Vertex* vertex_d = new Vertex(&apos;D&apos;); Vertex* vertex_e = new Vertex(&apos;E&apos;); Vertex* vertex_f = new Vertex(&apos;F&apos;); Vertex* vertex_g = new Vertex(&apos;G&apos;); // declaring some edges Edge* edge_1 = new Edge(vertex_a, vertex_c, 1); Edge* edge_2 = new Edge(vertex_a, vertex_d, 2); Edge* edge_3 = new Edge(vertex_b, vertex_c, 2); Edge* edge_4 = new Edge(vertex_c, vertex_d, 1); Edge* edge_5 = new Edge(vertex_b, vertex_f, 3); Edge* edge_6 = new Edge(vertex_c, vertex_e, 3); Edge* edge_7 = new Edge(vertex_e, vertex_f, 2); Edge* edge_8 = new Edge(vertex_d, vertex_g, 1); Edge* edge_9 = new Edge(vertex_g, vertex_f, 1); vertex_a -&gt; distance_from_start = 0; // setting a start vertex // calling the Dijkstra() function to find the shortest route possible Dijkstra(); // calling the Print_Shortest_Route_To() function to print the shortest route from the source vertex to the destination vertex Print_Shortest_Route_To(vertex_f); } // defining the function for Dijkstra&apos;s Algorithm void Dijkstra() { while (vertices.size() &gt; 0) { Vertex* smallest = Extract_Smallest(vertices); vector* adjacent_nodes = Adjacent_Remaining_Nodes(smallest); const int size = adjacent_nodes -&gt; size(); for (int i = 0; i at(i); int distance = Distance(smallest, adjacent) + smallest -&gt; distance_from_start; if (distance distance_from_start) { adjacent -&gt; distance_from_start = distance; adjacent -&gt; prev = smallest; } } delete adjacent_nodes; } } // defining the function to find the vertex with the shortest distance, removing it, and returning it Vertex* Extract_Smallest(vector&amp; vertices) { int size = vertices.size(); if (size == 0) return NULL; int smallest_position = 0; Vertex* smallest = vertices.at(0); for (int i = 1; i distance_from_start distance_from_start) { smallest = current; smallest_position = i; } } vertices.erase(vertices.begin() + smallest_position); return smallest; } // defining the function to return all vertices adjacent to &apos;vertex&apos; which are still in the &apos;vertices&apos; collection. vector* Adjacent_Remaining_Nodes(Vertex* vertex) { vector* adjacent_nodes = new vector(); const int size = edges.size(); for (int i = 0; i vertexOne == vertex) { adjacent = edge -&gt; vertexTwo; } else if (edge -&gt; vertexTwo == vertex) { adjacent = edge -&gt; vertexOne; } if (adjacent &amp;&amp; Contains(vertices, adjacent)) { adjacent_nodes -&gt; push_back(adjacent); } } return adjacent_nodes; } // defining the function to return distance between two connected vertices int Distance(Vertex* vertexOne, Vertex* vertexTwo) { const int size = edges.size(); for (int i = 0; i Connects(vertexOne, vertexTwo)) { return edge -&gt; distance; } } return -1; // should never happen } // defining the function to check if the &apos;vertices&apos; vector contains &apos;vertex&apos; bool Contains(vector&amp; vertices, Vertex* vertex) { const int size = vertices.size(); for (int i = 0; i <size; ++i) { if (vertex="=" vertices.at(i)) return true; } false; defining the function to print shortest route destination void print_shortest_route_to(vertex* des) vertex* prev="des;" cout << \'distance from start: \' < distance_from_start endl; while (prev) id prev; pre> <p> <strong>Output</strong> </p> <pre> Distance from start: 4 F G D A </pre> <p> <strong>Explanation:</strong> </p> <p>In the above code snippet, we included the <strong>&apos;iostream&apos;</strong> and <strong>&apos;vector&apos;</strong> header files and defined a constant value as <strong>MAX_INT = 10000000</strong> . We then used the standard namespace and prototyped the <strong>DijkstraAlgorithm()</strong> function. We then defined the main function of the program within, which we have called the <strong>DijkstraAlgorithm()</strong> function. After that, we declared some classes to create vertices and edges. We have also prototyped more functions to find the shortest possible path from the source vertex to the destination vertex and instantiated the Vertex and Edge classes. We then defined both classes to create the vertices and edges of the graph. We have then defined the <strong>DijkstraAlgorithm()</strong> function to create a graph and perform different operations. Inside this function, we have declared some vertices and edges. We then set the source vertex of the graph and called the <strong>Dijkstra()</strong> function to find the shortest possible distance and <strong>Print_Shortest_Route_To()</strong> function to print the shortest distance from the source vertex to vertex <strong>&apos;F&apos;</strong> . We have then defined the <strong>Dijkstra()</strong> function to calculate the shortest possible distances of the all the vertices from the source vertex. We have also defined some more functions to find the vertex with the shortest distance to return all the vertices adjacent to the remaining vertex, to return the distance between two connected vertices, to check if the selected vertex exists in the graph, and to print the shortest possible path from the source vertex to the destination vertex.</p> <p>As a result, the required shortest path for the vertex <strong>&apos;F&apos;</strong> from the source node is printed for the users.</p> <h3>Code for Dijkstra&apos;s Algorithm in Java</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the Java Programming Language:</p> <p> <strong>File: DijkstraAlgorithm.java</strong> </p> <pre> // Implementation of Dijkstra&apos;s Algorithm in Java // defining the public class for Dijkstra&apos;s Algorithm public class DijkstraAlgorithm { // defining the method to implement Dijkstra&apos;s Algorithm public void dijkstraAlgorithm(int[][] graph, int source) { // number of nodes int nodes = graph.length; boolean[] visited_vertex = new boolean[nodes]; int[] dist = new int[nodes]; for (int i = 0; i <nodes; 0 1 i++) { visited_vertex[i]="false;" dist[i]="Integer.MAX_VALUE;" } distance of self loop is zero dist[source]="0;" for (int i="0;" < nodes; updating the between neighboring vertex and source int u="find_min_distance(dist," visited_vertex); visited_vertex[u]="true;" distances all vertices v="0;" v++) if (!visited_vertex[v] && graph[u][v] !="0" (dist[u] + dist[v])) dist[v]="dist[u]" graph[u][v]; dist.length; system.out.println(string.format(\'distance from %s to %s\', source, i, dist[i])); defining method find minimum private static find_min_distance(int[] dist, boolean[] visited_vertex) minimum_distance="Integer.MAX_VALUE;" minimum_distance_vertex="-1;" (!visited_vertex[i] minimum_distance) return minimum_distance_vertex; main function public void main(string[] args) declaring nodes graphs graph[][]="new" int[][] 0, 1, 2, }, 3, }; instantiating dijkstraalgorithm() class dijkstraalgorithm test="new" dijkstraalgorithm(); calling shortest node destination test.dijkstraalgorithm(graph, 0); pre> <p> <strong>Output</strong> </p> <pre> Distance from Vertex 0 to Vertex 0 is 0 Distance from Vertex 0 to Vertex 1 is 1 Distance from Vertex 0 to Vertex 2 is 1 Distance from Vertex 0 to Vertex 3 is 2 Distance from Vertex 0 to Vertex 4 is 4 Distance from Vertex 0 to Vertex 5 is 4 Distance from Vertex 0 to Vertex 6 is 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have defined a public class as <strong>DijkstraAlgorithm()</strong> . Inside this class, we have defined a public method as <strong>dijkstraAlgorithm()</strong> to find the shortest distance from the source vertex to the destination vertex. Inside this method, we have defined a variable to store the number of nodes. We have then defined a Boolean array to store the information regarding the visited vertices and an integer array to store their respective distances. Initially, we declared the values in both the arrays as <strong>False</strong> and <strong>MAX_VALUE</strong> , respectively. We have also set the distance of the source vertex as zero and used the <strong>for-loop</strong> to update the distance between the source vertex and destination vertices with the minimum distance. We have then updated the distances of the neighboring vertices of the selected vertex by performing relaxation and printed the shortest distances for every vertex. We have then defined a method to find the minimum distance from the source vertex to the destination vertex. We then defined the main function where we declared the vertices of the graph and instantiated the <strong>DijkstraAlgorithm()</strong> class. Finally, we have called the <strong>dijkstraAlgorithm()</strong> method to find the shortest distance between the source vertex and the destination vertices.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h3>Code for Dijkstra&apos;s Algorithm in Python</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the Python Programming Language:</p> <p> <strong>File: DikstraAlgorithm.py</strong> </p> <pre> # Implementation of Dijkstra&apos;s Algorithm in Python # importing the sys module import sys # declaring the list of nodes for the graph nodes = [ [0, 0, 1, 0, 1, 0, 0], [0, 0, 1, 0, 0, 1, 0], [1, 1, 0, 1, 1, 0, 0], [1, 0, 1, 0, 0, 0, 1], [0, 0, 1, 0, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # declaring the list of edges for the graph edges = [ [0, 0, 1, 0, 2, 0, 0], [0, 0, 2, 0, 0, 3, 0], [1, 2, 0, 1, 3, 0, 0], [2, 0, 1, 0, 0, 0, 1], [0, 0, 3, 0, 0, 2, 0], [0, 3, 0, 0, 2, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # defining the function to find which node is to be visited next def toBeVisited(): global visitedAndDistance v = -10 for index in range(numberOfNodes): if visitedAndDistance[index][0] == 0 and (v <0 1 or visitedanddistance[index][1] <="visitedAndDistance[v][1]):" v="index" return # finding the number of nodes in graph numberofnodes="len(nodes[0])" visitedanddistance="[[0," 0]] for i range(numberofnodes - 1): visitedanddistance.append([0, sys.maxsize]) node range(numberofnodes): next to be visited tovisit="toBeVisited()" neighborindex updating new distances if nodes[tovisit][neighborindex]="=" and visitedanddistance[neighborindex][0]="=" 0: newdistance="visitedAndDistance[toVisit][1]" + edges[tovisit][neighborindex] visitedanddistance[neighborindex][1]> newDistance: visitedAndDistance[neighborIndex][1] = newDistance visitedAndDistance[toVisit][0] = 1 i = 0 # printing the distance for distance in visitedAndDistance: print(&apos;Distance of&apos;, chr(ord(&apos;A&apos;) + i), &apos;from source node:&apos;, distance[1]) i = i + 1 </0></pre> <p> <strong>Output</strong> </p> <pre> Distance of A from source node: 0 Distance of B from source node: 3 Distance of C from source node: 1 Distance of D from source node: 2 Distance of E from source node: 2 Distance of F from source node: 4 Distance of G from source node: 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have imported the <strong>sys</strong> module and declared the lists consisting of the values for the nodes and edges. We have then defined a function as <strong>toBeVisited()</strong> to find which node will be visited next. We then found the total number of nodes in the graph and set the initial distances for every node. We have then calculated the minimum distance from the source node to the destination node, performed relaxation on neighboring nodes, and updated the distances in the list. We then printed those distances from the list for the users.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h2>Time and Space Complexity of Dijkstra&apos;s Algorithm</h2> <ul> <li>The Time Complexity of Dijkstra&apos;s Algorithm is <strong>O(E log V)</strong> , where E is the number of edges and V is the number of vertices.</li> <li>The Space Complexity of Dijkstra&apos;s Algorithm is O(V), where V is the number of vertices.</li> </ul> <h2>Advantages and Disadvantages of Dijkstra&apos;s Algorithm</h2> <p> <strong>Let us discuss some advantages of Dijkstra&apos;s Algorithm:</strong> </p> <ol class="points"> <li>One primary advantage of using Dijkstra&apos;s Algorithm is that it has an almost linear time and space complexity.</li> <li>We can use this algorithm to calculate the shortest path from a single vertex to all other vertices and a single source vertex to a single destination vertex by stopping the algorithm once we get the shortest distance for the destination vertex.</li> <li>This algorithm only works for directed weighted graphs, and all the edges of this graph should be non-negative.</li> </ol> <p> <strong>Despite having multiple advantages, Dijkstra&apos;s algorithm has some disadvantages also, such as:</strong> </p> <ol class="points"> <li>Dijkstra&apos;s Algorithm performs a concealed exploration that utilizes a lot of time during the process.</li> <li>This algorithm is impotent to handle negative edges.</li> <li>Since this algorithm heads to the acyclic graph, it cannot calculate the exact shortest path.</li> <li>It also requires maintenance to keep a record of vertices that have been visited.</li> </ol> <h2>Some Applications of Dijkstra&apos;s Algorithm</h2> <p> <strong>Dijkstra&apos;s Algorithm has various real-world applications, some of which are stated below:</strong> </p> <ol class="points"> <tr><td>Digital Mapping Services in Google Maps:</td> There are various times when we have tried to find the distance in Google Maps either from our location to the nearest preferred location or from one city to another, which comprises multiple routes/paths connecting them; however, the application must display the minimum distance. This is only possible because Dijkstra&apos;s algorithm helps the application find the shortest between two given locations along the path. Let us consider the USA as a graph wherein the cities/places are represented as vertices, and the routes between two cities/places are represented as edges. Then with the help of Dijkstra&apos;s Algorithm, we can calculate the shortest routes between any two cities/places. </tr><tr><td>Social Networking Applications:</td> In many applications like Facebook, Twitter, Instagram, and more, many of us might have observed that these apps suggest the list of friends that a specific user may know. How do many social media companies implement this type of feature in an efficient and effective way, specifically when the system has over a billion users? The answer to this question is Dijkstra&apos;s Algorithm. The standard Dijkstra&apos;s Algorithm is generally used to estimate the shortest distance between the users measured through the connections or mutuality among them. When social networking is very small, it uses the standard Dijkstra&apos;s Algorithm in addition to some other features in order to determine the shortest paths. However, when the graph is much bigger, the standard algorithm takes several seconds to count, and thus, some advanced algorithms are used as the alternative. </tr><tr><td>Telephone Network:</td> As some of us might know, in a telephone network, each transmission line has a bandwidth, &apos;b&apos;. The bandwidth is the highest frequency that the transmission line can support. In general, if the frequency of the signal is higher in a specific line, the signal is reduced by that line. Bandwidth represents the amount of information that can be transmitted by the line. Let us consider a city a graph wherein the switching stations are represented using the vertices, the transmission lines are represented as the edges, and the bandwidth, &apos;b&apos;, is represented using the weight of the edges. Thus, as we can observe, the telephone network can also fall into the category of the shortest distance problem and can be solved using Dijkstra&apos;s Algorithm. </tr><tr><td>Flight Program:</td> Suppose that a person requires software to prepare an agenda of flights for customers. The agent has access to a database with all flights and airports. In addition to the flight number, origin airport, and destination, the flights also have departure and arrival times. So, in order to determine the earliest arrival time for the selected destination from the original airport and given start time, the agents make use of Dijkstra&apos;s Algorithm. </tr><tr><td>IP routing to find Open Shortest Path First:</td> Open Shortest Path First (abbreviated as OSPF) is a link-state routing protocol used to find the best path between the source and destination router with the help of its own Shortest Path First. Dijkstra&apos;s Algorithm is extensively utilized in the routing protocols required by the routers in order to update their forwarding table. The algorithm gives the shortest cost path from the source router to the other routers present in the network. </tr><tr><td>Robotic Path:</td> These days, drones and robots have come into existence, some operated manually and some automatically. The drones and robots which are operated automatically and used to deliver the packages to a given location or used for any certain task are configured with Dijkstra&apos;s Algorithm module so that whenever the source and destination are known, the drone and robot will move in the ordered direction by following the shortest path keeping the time taken to a minimum in order to deliver the packages. </tr><tr><td>Designate the File Server:</td> Dijkstra&apos;s Algorithm is also used to designate a file server in a Local Area Network (LAN). Suppose that an infinite period of time is needed for the transmission of the files from one computer to another. So, to minimize the number of &apos;hops&apos; from the file server to every other computer on the network, we will use Dijkstra&apos;s Algorithm. This algorithm will return the shortest path between the networks resulting in the minimum number of hops. </tr></ol> <h2>The Conclusion</h2> <ul> <li>In the above tutorial, firstly, we have understood the basic concepts of Graph along with its types and applications.</li> <li>We then learned about Dijkstra&apos;s Algorithm and its history.</li> <li>We have also understood the fundamental working of Dijkstra&apos;s Algorithm with the help of an example.</li> <li>After that, we studied how to write code for Dijkstra&apos;s Algorithm with the help of Pseudocode.</li> <li>We observed its implementation in programming languages like C, C++, Java, and Python with proper outputs and explanations.</li> <li>We have also understood the Time and Space Complexity of Dijkstra&apos;s Algorithm.</li> <li>Finally, we have discussed the advantages and disadvantages of Dijkstra&apos;s algorithm and some of its real-life applications.</li> </ul> <hr></nodes;></pre></size;>

Erläuterung:

Im obigen Codeausschnitt haben wir Folgendes eingefügt 'iostream' Und 'Vektor' Header-Dateien und definierte einen konstanten Wert als MAX_INT = 10000000 . Anschließend haben wir den Standard-Namespace verwendet und einen Prototyp erstellt DijkstraAlgorithmus() Funktion. Anschließend haben wir die Hauptfunktion des Programms definiert, die wir aufgerufen haben DijkstraAlgorithmus() Funktion. Danach haben wir einige Klassen deklariert, um Scheitelpunkte und Kanten zu erstellen. Wir haben außerdem Prototypen für weitere Funktionen erstellt, um den kürzestmöglichen Pfad vom Quellscheitelpunkt zum Zielscheitelpunkt zu finden, und die Klassen Vertex und Edge instanziiert. Anschließend haben wir beide Klassen definiert, um die Eckpunkte und Kanten des Diagramms zu erstellen. Wir haben dann die definiert DijkstraAlgorithmus() Funktion zum Erstellen eines Diagramms und zum Ausführen verschiedener Operationen. Innerhalb dieser Funktion haben wir einige Eckpunkte und Kanten deklariert. Anschließend legen wir den Quellscheitelpunkt des Diagramms fest und rufen den auf Dijkstra() Funktion, um die kürzestmögliche Entfernung zu finden und Print_Shortest_Route_To() Funktion zum Drucken des kürzesten Abstands vom Quellscheitelpunkt zum Scheitelpunkt 'F' . Wir haben dann die definiert Dijkstra() Funktion zum Berechnen der kürzestmöglichen Abstände aller Scheitelpunkte vom Quellscheitelpunkt. Wir haben auch einige weitere Funktionen definiert, um den Scheitelpunkt mit dem kürzesten Abstand zu finden, alle Scheitelpunkte neben dem verbleibenden Scheitelpunkt zurückzugeben, den Abstand zwischen zwei verbundenen Scheitelpunkten zurückzugeben, zu prüfen, ob der ausgewählte Scheitelpunkt im Diagramm vorhanden ist, und ihn auszudrucken kürzestmöglicher Weg vom Quellscheitelpunkt zum Zielscheitelpunkt.

Daraus ergibt sich der erforderliche kürzeste Weg für den Scheitelpunkt 'F' vom Quellknoten wird für die Benutzer gedruckt.

Code für Dijkstras Algorithmus in Java

Das Folgende ist die Implementierung des Dijkstra-Algorithmus in der Programmiersprache Java:

Datei: DijkstraAlgorithm.java

 // Implementation of Dijkstra&apos;s Algorithm in Java // defining the public class for Dijkstra&apos;s Algorithm public class DijkstraAlgorithm { // defining the method to implement Dijkstra&apos;s Algorithm public void dijkstraAlgorithm(int[][] graph, int source) { // number of nodes int nodes = graph.length; boolean[] visited_vertex = new boolean[nodes]; int[] dist = new int[nodes]; for (int i = 0; i <nodes; 0 1 i++) { visited_vertex[i]="false;" dist[i]="Integer.MAX_VALUE;" } distance of self loop is zero dist[source]="0;" for (int i="0;" < nodes; updating the between neighboring vertex and source int u="find_min_distance(dist," visited_vertex); visited_vertex[u]="true;" distances all vertices v="0;" v++) if (!visited_vertex[v] && graph[u][v] !="0" (dist[u] + dist[v])) dist[v]="dist[u]" graph[u][v]; dist.length; system.out.println(string.format(\'distance from %s to %s\', source, i, dist[i])); defining method find minimum private static find_min_distance(int[] dist, boolean[] visited_vertex) minimum_distance="Integer.MAX_VALUE;" minimum_distance_vertex="-1;" (!visited_vertex[i] minimum_distance) return minimum_distance_vertex; main function public void main(string[] args) declaring nodes graphs graph[][]="new" int[][] 0, 1, 2, }, 3, }; instantiating dijkstraalgorithm() class dijkstraalgorithm test="new" dijkstraalgorithm(); calling shortest node destination test.dijkstraalgorithm(graph, 0); pre> <p> <strong>Output</strong> </p> <pre> Distance from Vertex 0 to Vertex 0 is 0 Distance from Vertex 0 to Vertex 1 is 1 Distance from Vertex 0 to Vertex 2 is 1 Distance from Vertex 0 to Vertex 3 is 2 Distance from Vertex 0 to Vertex 4 is 4 Distance from Vertex 0 to Vertex 5 is 4 Distance from Vertex 0 to Vertex 6 is 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have defined a public class as <strong>DijkstraAlgorithm()</strong> . Inside this class, we have defined a public method as <strong>dijkstraAlgorithm()</strong> to find the shortest distance from the source vertex to the destination vertex. Inside this method, we have defined a variable to store the number of nodes. We have then defined a Boolean array to store the information regarding the visited vertices and an integer array to store their respective distances. Initially, we declared the values in both the arrays as <strong>False</strong> and <strong>MAX_VALUE</strong> , respectively. We have also set the distance of the source vertex as zero and used the <strong>for-loop</strong> to update the distance between the source vertex and destination vertices with the minimum distance. We have then updated the distances of the neighboring vertices of the selected vertex by performing relaxation and printed the shortest distances for every vertex. We have then defined a method to find the minimum distance from the source vertex to the destination vertex. We then defined the main function where we declared the vertices of the graph and instantiated the <strong>DijkstraAlgorithm()</strong> class. Finally, we have called the <strong>dijkstraAlgorithm()</strong> method to find the shortest distance between the source vertex and the destination vertices.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h3>Code for Dijkstra&apos;s Algorithm in Python</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the Python Programming Language:</p> <p> <strong>File: DikstraAlgorithm.py</strong> </p> <pre> # Implementation of Dijkstra&apos;s Algorithm in Python # importing the sys module import sys # declaring the list of nodes for the graph nodes = [ [0, 0, 1, 0, 1, 0, 0], [0, 0, 1, 0, 0, 1, 0], [1, 1, 0, 1, 1, 0, 0], [1, 0, 1, 0, 0, 0, 1], [0, 0, 1, 0, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # declaring the list of edges for the graph edges = [ [0, 0, 1, 0, 2, 0, 0], [0, 0, 2, 0, 0, 3, 0], [1, 2, 0, 1, 3, 0, 0], [2, 0, 1, 0, 0, 0, 1], [0, 0, 3, 0, 0, 2, 0], [0, 3, 0, 0, 2, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # defining the function to find which node is to be visited next def toBeVisited(): global visitedAndDistance v = -10 for index in range(numberOfNodes): if visitedAndDistance[index][0] == 0 and (v <0 1 or visitedanddistance[index][1] <="visitedAndDistance[v][1]):" v="index" return # finding the number of nodes in graph numberofnodes="len(nodes[0])" visitedanddistance="[[0," 0]] for i range(numberofnodes - 1): visitedanddistance.append([0, sys.maxsize]) node range(numberofnodes): next to be visited tovisit="toBeVisited()" neighborindex updating new distances if nodes[tovisit][neighborindex]="=" and visitedanddistance[neighborindex][0]="=" 0: newdistance="visitedAndDistance[toVisit][1]" + edges[tovisit][neighborindex] visitedanddistance[neighborindex][1]> newDistance: visitedAndDistance[neighborIndex][1] = newDistance visitedAndDistance[toVisit][0] = 1 i = 0 # printing the distance for distance in visitedAndDistance: print(&apos;Distance of&apos;, chr(ord(&apos;A&apos;) + i), &apos;from source node:&apos;, distance[1]) i = i + 1 </0></pre> <p> <strong>Output</strong> </p> <pre> Distance of A from source node: 0 Distance of B from source node: 3 Distance of C from source node: 1 Distance of D from source node: 2 Distance of E from source node: 2 Distance of F from source node: 4 Distance of G from source node: 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have imported the <strong>sys</strong> module and declared the lists consisting of the values for the nodes and edges. We have then defined a function as <strong>toBeVisited()</strong> to find which node will be visited next. We then found the total number of nodes in the graph and set the initial distances for every node. We have then calculated the minimum distance from the source node to the destination node, performed relaxation on neighboring nodes, and updated the distances in the list. We then printed those distances from the list for the users.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h2>Time and Space Complexity of Dijkstra&apos;s Algorithm</h2> <ul> <li>The Time Complexity of Dijkstra&apos;s Algorithm is <strong>O(E log V)</strong> , where E is the number of edges and V is the number of vertices.</li> <li>The Space Complexity of Dijkstra&apos;s Algorithm is O(V), where V is the number of vertices.</li> </ul> <h2>Advantages and Disadvantages of Dijkstra&apos;s Algorithm</h2> <p> <strong>Let us discuss some advantages of Dijkstra&apos;s Algorithm:</strong> </p> <ol class="points"> <li>One primary advantage of using Dijkstra&apos;s Algorithm is that it has an almost linear time and space complexity.</li> <li>We can use this algorithm to calculate the shortest path from a single vertex to all other vertices and a single source vertex to a single destination vertex by stopping the algorithm once we get the shortest distance for the destination vertex.</li> <li>This algorithm only works for directed weighted graphs, and all the edges of this graph should be non-negative.</li> </ol> <p> <strong>Despite having multiple advantages, Dijkstra&apos;s algorithm has some disadvantages also, such as:</strong> </p> <ol class="points"> <li>Dijkstra&apos;s Algorithm performs a concealed exploration that utilizes a lot of time during the process.</li> <li>This algorithm is impotent to handle negative edges.</li> <li>Since this algorithm heads to the acyclic graph, it cannot calculate the exact shortest path.</li> <li>It also requires maintenance to keep a record of vertices that have been visited.</li> </ol> <h2>Some Applications of Dijkstra&apos;s Algorithm</h2> <p> <strong>Dijkstra&apos;s Algorithm has various real-world applications, some of which are stated below:</strong> </p> <ol class="points"> <tr><td>Digital Mapping Services in Google Maps:</td> There are various times when we have tried to find the distance in Google Maps either from our location to the nearest preferred location or from one city to another, which comprises multiple routes/paths connecting them; however, the application must display the minimum distance. This is only possible because Dijkstra&apos;s algorithm helps the application find the shortest between two given locations along the path. Let us consider the USA as a graph wherein the cities/places are represented as vertices, and the routes between two cities/places are represented as edges. Then with the help of Dijkstra&apos;s Algorithm, we can calculate the shortest routes between any two cities/places. </tr><tr><td>Social Networking Applications:</td> In many applications like Facebook, Twitter, Instagram, and more, many of us might have observed that these apps suggest the list of friends that a specific user may know. How do many social media companies implement this type of feature in an efficient and effective way, specifically when the system has over a billion users? The answer to this question is Dijkstra&apos;s Algorithm. The standard Dijkstra&apos;s Algorithm is generally used to estimate the shortest distance between the users measured through the connections or mutuality among them. When social networking is very small, it uses the standard Dijkstra&apos;s Algorithm in addition to some other features in order to determine the shortest paths. However, when the graph is much bigger, the standard algorithm takes several seconds to count, and thus, some advanced algorithms are used as the alternative. </tr><tr><td>Telephone Network:</td> As some of us might know, in a telephone network, each transmission line has a bandwidth, &apos;b&apos;. The bandwidth is the highest frequency that the transmission line can support. In general, if the frequency of the signal is higher in a specific line, the signal is reduced by that line. Bandwidth represents the amount of information that can be transmitted by the line. Let us consider a city a graph wherein the switching stations are represented using the vertices, the transmission lines are represented as the edges, and the bandwidth, &apos;b&apos;, is represented using the weight of the edges. Thus, as we can observe, the telephone network can also fall into the category of the shortest distance problem and can be solved using Dijkstra&apos;s Algorithm. </tr><tr><td>Flight Program:</td> Suppose that a person requires software to prepare an agenda of flights for customers. The agent has access to a database with all flights and airports. In addition to the flight number, origin airport, and destination, the flights also have departure and arrival times. So, in order to determine the earliest arrival time for the selected destination from the original airport and given start time, the agents make use of Dijkstra&apos;s Algorithm. </tr><tr><td>IP routing to find Open Shortest Path First:</td> Open Shortest Path First (abbreviated as OSPF) is a link-state routing protocol used to find the best path between the source and destination router with the help of its own Shortest Path First. Dijkstra&apos;s Algorithm is extensively utilized in the routing protocols required by the routers in order to update their forwarding table. The algorithm gives the shortest cost path from the source router to the other routers present in the network. </tr><tr><td>Robotic Path:</td> These days, drones and robots have come into existence, some operated manually and some automatically. The drones and robots which are operated automatically and used to deliver the packages to a given location or used for any certain task are configured with Dijkstra&apos;s Algorithm module so that whenever the source and destination are known, the drone and robot will move in the ordered direction by following the shortest path keeping the time taken to a minimum in order to deliver the packages. </tr><tr><td>Designate the File Server:</td> Dijkstra&apos;s Algorithm is also used to designate a file server in a Local Area Network (LAN). Suppose that an infinite period of time is needed for the transmission of the files from one computer to another. So, to minimize the number of &apos;hops&apos; from the file server to every other computer on the network, we will use Dijkstra&apos;s Algorithm. This algorithm will return the shortest path between the networks resulting in the minimum number of hops. </tr></ol> <h2>The Conclusion</h2> <ul> <li>In the above tutorial, firstly, we have understood the basic concepts of Graph along with its types and applications.</li> <li>We then learned about Dijkstra&apos;s Algorithm and its history.</li> <li>We have also understood the fundamental working of Dijkstra&apos;s Algorithm with the help of an example.</li> <li>After that, we studied how to write code for Dijkstra&apos;s Algorithm with the help of Pseudocode.</li> <li>We observed its implementation in programming languages like C, C++, Java, and Python with proper outputs and explanations.</li> <li>We have also understood the Time and Space Complexity of Dijkstra&apos;s Algorithm.</li> <li>Finally, we have discussed the advantages and disadvantages of Dijkstra&apos;s algorithm and some of its real-life applications.</li> </ul> <hr></nodes;>

Erläuterung:

Im obigen Codeausschnitt haben wir eine öffentliche Klasse definiert als DijkstraAlgorithmus() . Innerhalb dieser Klasse haben wir eine öffentliche Methode definiert als dijkstraAlgorithmus() um den kürzesten Abstand vom Quellscheitelpunkt zum Zielscheitelpunkt zu finden. Innerhalb dieser Methode haben wir eine Variable definiert, um die Anzahl der Knoten zu speichern. Anschließend haben wir ein boolesches Array zum Speichern der Informationen zu den besuchten Eckpunkten und ein ganzzahliges Array zum Speichern ihrer jeweiligen Entfernungen definiert. Zunächst haben wir die Werte in beiden Arrays als deklariert FALSCH Und MAX_VALUE , jeweils. Wir haben auch den Abstand des Quellscheitelpunkts auf Null gesetzt und verwendet for-Schleife um den Abstand zwischen dem Quellscheitelpunkt und den Zielscheitelpunkten mit dem Mindestabstand zu aktualisieren. Anschließend haben wir die Abstände der benachbarten Scheitelpunkte des ausgewählten Scheitelpunkts durch eine Entspannung aktualisiert und die kürzesten Abstände für jeden Scheitelpunkt gedruckt. Anschließend haben wir eine Methode definiert, um den Mindestabstand vom Quellscheitelpunkt zum Zielscheitelpunkt zu ermitteln. Anschließend haben wir die Hauptfunktion definiert, in der wir die Eckpunkte des Diagramms deklariert und instanziiert haben DijkstraAlgorithmus() Klasse. Schließlich haben wir das aufgerufen dijkstraAlgorithmus() Methode, um den kürzesten Abstand zwischen dem Quellscheitelpunkt und den Zielscheitelpunkten zu ermitteln.

Dadurch werden den Benutzern für jeden Knoten vom Quellknoten aus die erforderlichen kürzestmöglichen Pfade ausgedruckt.

Code für Dijkstras Algorithmus in Python

Das Folgende ist die Implementierung des Dijkstra-Algorithmus in der Programmiersprache Python:

Datei: DikstraAlgorithm.py

 # Implementation of Dijkstra&apos;s Algorithm in Python # importing the sys module import sys # declaring the list of nodes for the graph nodes = [ [0, 0, 1, 0, 1, 0, 0], [0, 0, 1, 0, 0, 1, 0], [1, 1, 0, 1, 1, 0, 0], [1, 0, 1, 0, 0, 0, 1], [0, 0, 1, 0, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # declaring the list of edges for the graph edges = [ [0, 0, 1, 0, 2, 0, 0], [0, 0, 2, 0, 0, 3, 0], [1, 2, 0, 1, 3, 0, 0], [2, 0, 1, 0, 0, 0, 1], [0, 0, 3, 0, 0, 2, 0], [0, 3, 0, 0, 2, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # defining the function to find which node is to be visited next def toBeVisited(): global visitedAndDistance v = -10 for index in range(numberOfNodes): if visitedAndDistance[index][0] == 0 and (v <0 1 or visitedanddistance[index][1] <="visitedAndDistance[v][1]):" v="index" return # finding the number of nodes in graph numberofnodes="len(nodes[0])" visitedanddistance="[[0," 0]] for i range(numberofnodes - 1): visitedanddistance.append([0, sys.maxsize]) node range(numberofnodes): next to be visited tovisit="toBeVisited()" neighborindex updating new distances if nodes[tovisit][neighborindex]="=" and visitedanddistance[neighborindex][0]="=" 0: newdistance="visitedAndDistance[toVisit][1]" + edges[tovisit][neighborindex] visitedanddistance[neighborindex][1]> newDistance: visitedAndDistance[neighborIndex][1] = newDistance visitedAndDistance[toVisit][0] = 1 i = 0 # printing the distance for distance in visitedAndDistance: print(&apos;Distance of&apos;, chr(ord(&apos;A&apos;) + i), &apos;from source node:&apos;, distance[1]) i = i + 1 </0>

Ausgabe

 Distance of A from source node: 0 Distance of B from source node: 3 Distance of C from source node: 1 Distance of D from source node: 2 Distance of E from source node: 2 Distance of F from source node: 4 Distance of G from source node: 3 

Erläuterung:

Im obigen Codeausschnitt haben wir das importiert sys Modul und deklarierte die Listen bestehend aus den Werten für die Knoten und Kanten. Wir haben dann eine Funktion definiert als toBeVisited() um herauszufinden, welcher Knoten als nächstes besucht wird. Anschließend haben wir die Gesamtzahl der Knoten im Diagramm ermittelt und die Anfangsabstände für jeden Knoten festgelegt. Anschließend haben wir den Mindestabstand vom Quellknoten zum Zielknoten berechnet, eine Entspannung für benachbarte Knoten durchgeführt und die Abstände in der Liste aktualisiert. Anschließend haben wir diese Abstände aus der Liste für die Benutzer ausgedruckt.

Dadurch werden den Benutzern für jeden Knoten vom Quellknoten aus die erforderlichen kürzestmöglichen Pfade ausgedruckt.

Objekt für JSON in Java

Zeit- und Raumkomplexität des Dijkstra-Algorithmus

• Die Zeitkomplexität des Dijkstra-Algorithmus beträgt O(E log V) , wobei E die Anzahl der Kanten und V die Anzahl der Eckpunkte ist.
• Die Raumkomplexität des Dijkstra-Algorithmus beträgt O(V), wobei V die Anzahl der Eckpunkte ist.

Vor- und Nachteile des Dijkstra-Algorithmus

Lassen Sie uns einige Vorteile des Dijkstra-Algorithmus diskutieren:

1. Ein Hauptvorteil der Verwendung des Dijkstra-Algorithmus besteht darin, dass er eine nahezu lineare zeitliche und räumliche Komplexität aufweist.
2. Mit diesem Algorithmus können wir den kürzesten Weg von einem einzelnen Scheitelpunkt zu allen anderen Scheitelpunkten und von einem einzelnen Quellscheitelpunkt zu einem einzelnen Zielscheitelpunkt berechnen, indem wir den Algorithmus stoppen, sobald wir die kürzeste Entfernung für den Zielscheitelpunkt erhalten.
3. Dieser Algorithmus funktioniert nur für gerichtete gewichtete Diagramme und alle Kanten dieses Diagramms sollten nicht negativ sein.

Trotz zahlreicher Vorteile hat der Dijkstra-Algorithmus auch einige Nachteile, wie zum Beispiel:

1. Der Dijkstra-Algorithmus führt eine verdeckte Erkundung durch, die während des Prozesses viel Zeit in Anspruch nimmt.
2. Dieser Algorithmus kann negative Kanten nicht verarbeiten.
3. Da dieser Algorithmus zum azyklischen Graphen geht, kann er nicht den exakt kürzesten Weg berechnen.
4. Es erfordert auch Wartung, um eine Aufzeichnung der besuchten Scheitelpunkte zu führen.

Einige Anwendungen des Dijkstra-Algorithmus

Der Dijkstra-Algorithmus hat verschiedene reale Anwendungen, von denen einige im Folgenden aufgeführt sind:

Digitale Kartendienste in Google Maps:Es gibt verschiedene Gelegenheiten, in denen wir versucht haben, in Google Maps die Entfernung von unserem Standort zum nächstgelegenen bevorzugten Standort oder von einer Stadt zu einer anderen zu ermitteln, was aus mehreren Routen/Pfaden besteht, die sie verbinden. Allerdings muss die Anwendung den Mindestabstand anzeigen. Dies ist nur möglich, weil der Dijkstra-Algorithmus der Anwendung hilft, den kürzesten Abstand zwischen zwei vorgegebenen Orten entlang des Pfades zu finden. Betrachten wir die USA als einen Graphen, in dem die Städte/Orte als Eckpunkte und die Routen zwischen zwei Städten/Orten als Kanten dargestellt werden. Mithilfe des Dijkstra-Algorithmus können wir dann die kürzesten Routen zwischen zwei beliebigen Städten/Orten berechnen.Anwendungen für soziale Netzwerke:In vielen Anwendungen wie Facebook, Twitter, Instagram und anderen haben viele von uns vielleicht beobachtet, dass diese Apps die Liste der Freunde vorschlagen, die ein bestimmter Benutzer möglicherweise kennt. Wie implementieren viele Social-Media-Unternehmen diese Art von Funktion effizient und effektiv, insbesondere wenn das System über eine Milliarde Nutzer hat? Die Antwort auf diese Frage ist der Dijkstra-Algorithmus. Der standardmäßige Dijkstra-Algorithmus wird im Allgemeinen verwendet, um die kürzeste Entfernung zwischen den Benutzern zu schätzen, gemessen durch die Verbindungen oder die Gegenseitigkeit zwischen ihnen. Wenn das soziale Netzwerk sehr klein ist, wird zusätzlich zu einigen anderen Funktionen der standardmäßige Dijkstra-Algorithmus verwendet, um die kürzesten Wege zu ermitteln. Wenn das Diagramm jedoch viel größer ist, benötigt der Standardalgorithmus mehrere Sekunden zum Zählen, weshalb einige erweiterte Algorithmen als Alternative verwendet werden.Telefonnetz:Wie einige von uns vielleicht wissen, hat in einem Telefonnetz jede Übertragungsleitung eine Bandbreite, „b“. Die Bandbreite ist die höchste Frequenz, die die Übertragungsleitung unterstützen kann. Wenn die Frequenz des Signals in einer bestimmten Leitung höher ist, wird das Signal im Allgemeinen um diese Leitung verringert. Die Bandbreite stellt die Menge an Informationen dar, die über die Leitung übertragen werden kann. Betrachten wir eine Stadt als Diagramm, in dem die Schaltstationen durch die Eckpunkte, die Übertragungsleitungen durch die Kanten und die Bandbreite „b“ durch das Gewicht der Kanten dargestellt werden. Somit kann, wie wir beobachten können, auch das Telefonnetz in die Kategorie des Problems der kürzesten Entfernung fallen und mit dem Dijkstra-Algorithmus gelöst werden.Flugprogramm:Angenommen, eine Person benötigt eine Software, um einen Flugplan für Kunden zu erstellen. Der Agent hat Zugriff auf eine Datenbank mit allen Flügen und Flughäfen. Neben der Flugnummer, dem Abflughafen und dem Zielort verfügen die Flüge auch über Abflug- und Ankunftszeiten. Um also die früheste Ankunftszeit für das ausgewählte Ziel vom ursprünglichen Flughafen und der gegebenen Startzeit zu bestimmen, nutzen die Agenten den Dijkstra-Algorithmus.IP-Routing, um den offenen kürzesten Pfad zuerst zu finden:Open Shortest Path First (abgekürzt als OSPF) ist ein Link-State-Routing-Protokoll, das verwendet wird, um mithilfe seines eigenen Shortest Path First den besten Pfad zwischen dem Quell- und Zielrouter zu finden. Der Dijkstra-Algorithmus wird in großem Umfang in den Routing-Protokollen verwendet, die die Router benötigen, um ihre Weiterleitungstabelle zu aktualisieren. Der Algorithmus gibt den kürzesten Kostenpfad vom Quellrouter zu den anderen im Netzwerk vorhandenen Routern an.Roboterpfad:Heutzutage gibt es Drohnen und Roboter, die teils manuell, teils automatisch betrieben werden. Die Drohnen und Roboter, die automatisch betrieben werden und zur Lieferung der Pakete an einen bestimmten Ort oder für eine bestimmte Aufgabe verwendet werden, werden mit dem Algorithmusmodul von Dijkstra so konfiguriert, dass sich Drohne und Roboter immer dann in die gewünschte Richtung bewegen, wenn Quelle und Ziel bekannt sind Indem wir den kürzesten Weg einschlagen und die Zeit für die Zustellung der Pakete auf ein Minimum beschränken.Bestimmen Sie den Dateiserver:Der Dijkstra-Algorithmus wird auch verwendet, um einen Dateiserver in einem lokalen Netzwerk (LAN) zu bestimmen. Nehmen wir an, dass für die Übertragung der Dateien von einem Computer auf einen anderen eine unendliche Zeitspanne benötigt wird. Um also die Anzahl der „Sprünge“ vom Dateiserver zu jedem anderen Computer im Netzwerk zu minimieren, verwenden wir den Dijkstra-Algorithmus. Dieser Algorithmus gibt den kürzesten Pfad zwischen den Netzwerken zurück, was zu einer minimalen Anzahl von Sprüngen führt.

Der Abschluss

• Im obigen Tutorial haben wir zunächst die Grundkonzepte von Graph sowie seine Typen und Anwendungen verstanden.
• Anschließend lernten wir den Dijkstra-Algorithmus und seine Geschichte kennen.
• Anhand eines Beispiels haben wir auch die grundlegende Funktionsweise des Dijkstra-Algorithmus verstanden.
• Danach haben wir untersucht, wie man mithilfe von Pseudocode Code für den Dijkstra-Algorithmus schreibt.
• Wir haben die Implementierung in Programmiersprachen wie C, C++, Java und Python mit geeigneten Ausgaben und Erklärungen beobachtet.
• Wir haben auch die zeitliche und räumliche Komplexität des Dijkstra-Algorithmus verstanden.
• Abschließend haben wir die Vor- und Nachteile des Dijkstra-Algorithmus und einige seiner realen Anwendungen besprochen.