DIJKSTRAS KORTESTE VEJALGORITME MED EKSEMPLER

Følgende tutorial vil lære os om Dijkstra's Shortest Path Algorithm. Vi vil forstå, hvordan Dijkstras algoritme fungerer med en trinvis grafisk forklaring.

Vi vil dække følgende:

En kort oversigt over grafens grundlæggende begreber
Forstå brugen af Dijkstras algoritme
Forstå algoritmens virkemåde med et trin-for-trin eksempel

Så lad os komme i gang.

En kort introduktion til grafer

Grafer er ikke-lineære datastrukturer, der repræsenterer 'forbindelserne' mellem elementerne. Disse elementer er kendt som Toppunkter , og de linjer eller buer, der forbinder to vilkårlige hjørner i grafen, er kendt som Kanter . Mere formelt omfatter en graf et sæt toppunkter (V) og et sæt kanter (E) . Grafen er angivet med G(V, E) .

Komponenter i en graf

Hjørner:Hjørner er de grundlæggende enheder i grafen, der bruges til at repræsentere virkelige objekter, personer eller enheder. Nogle gange er hjørner også kendt som noder.Kanter:Kanter tegnes eller bruges til at forbinde to hjørner af grafen. Nogle gange er kanter også kendt som buer.

Følgende figur viser en grafisk repræsentation af en graf:

Figur 1: Grafisk fremstilling af en graf

I ovenstående figur er hjørnerne/knuderne angivet med farvede cirkler, og kanterne er markeret med linjerne, der forbinder knuderne.

Anvendelser af graferne

Grafer bruges til at løse mange problemer i det virkelige liv. Grafer bruges til at repræsentere netværkene. Disse netværk kan omfatte telefon- eller kredsløbsnetværk eller stier i en by.

For eksempel kunne vi bruge Graphs til at designe en transportnetværksmodel, hvor toppunkterne viser de faciliteter, der sender eller modtager produkterne, og kanterne repræsenterer veje eller stier, der forbinder dem. Følgende er en billedlig fremstilling af det samme:

Figur 2: Billedrepræsentation af transportnetværk

Grafer bruges også i forskellige sociale medieplatforme som LinkedIn, Facebook, Twitter og mere. For eksempel bruger platforme som Facebook Graphs til at gemme data fra deres brugere, hvor hver person er angivet med et vertex, og hver af dem er en struktur, der indeholder information som person-id, navn, køn, adresse osv.

Typer af grafer

Graferne kan kategoriseres i to typer:

Udirigeret graf
Instrueret graf

Udirigeret graf: En graf med kanter, der ikke har en retning, kaldes en urettet graf. Kanterne på denne graf antyder et tovejsforhold, hvor hver kant kan krydses i begge retninger. Den følgende figur viser en simpel, ikke-rettet graf med fire noder og fem kanter.

Figur 3: En simpel udirigeret graf

Instrueret graf: En graf med kanter med retning kaldes en rettet graf. Kanterne på denne graf antyder et envejsforhold, hvor hver kant kun kan krydses i en enkelt retning. Den følgende figur viser en simpel rettet graf med fire noder og fem kanter.

Figur 4: En simpel rettet graf

Den absolutte længde, position eller orientering af kanterne i en grafillustration har karakteristisk ikke betydning. Med andre ord kan vi visualisere den samme graf på forskellige måder ved at omarrangere hjørnerne eller forvrænge kanterne, hvis den underliggende struktur af grafen ikke ændres.

Hvad er vægtede grafer?

En graf siges at være vægtet, hvis hver kant er tildelt en 'vægt'. Vægten af en kant kan angive afstand, tid eller noget, der modellerer 'forbindelsen' mellem det par af hjørner, den forbinder.

For eksempel kan vi observere et blåt tal ved siden af hver kant i den følgende figur af den vægtede graf. Dette tal bruges til at angive vægten af den tilsvarende kant.

Figur 5: Et eksempel på en vægtet graf

En introduktion til Dijkstras algoritme

Nu hvor vi kender nogle grundlæggende grafer-begreber, lad os dykke ned i at forstå konceptet med Dijkstras algoritme.

Har du nogensinde spekuleret på, hvordan finder Google Maps den korteste og hurtigste rute mellem to steder?

Nå, svaret er Dijkstras algoritme . Dijkstras algoritme er en grafalgoritme der finder den korteste vej fra et kildepunkt til alle andre hjørner i grafen (enkelt kilde korteste vej). Det er en type grådig algoritme, der kun virker på vægtede grafer med positive vægte. Tidskompleksiteten af Dijkstras algoritme er O(V²) ved hjælp af nabomatrix-repræsentationen af grafen. Denne tid kompleksitet kan reduceres til O((V + E) log V) ved hjælp af en adjacency liste repræsentation af grafen, hvor I er antallet af hjørner og OG er antallet af kanter i grafen.

hvis ellers i java

Historien om Dijkstras algoritme

Dijkstras algoritme er designet og udgivet af Dr. Edsger W. Dijkstra , en hollandsk computerforsker, softwareingeniør, programmør, videnskabsessayist og systemforsker.

Under et interview med Philip L. Frana for ACM-tidsskriftets kommunikation i år 2001 afslørede Dr. Edsger W. Dijkstra:

'Hvad er den korteste vej at rejse fra Rotterdam til Groningen generelt: fra given by til given by? Det er algoritmen for den korteste vej, som jeg designede på cirka tyve minutter. En morgen var jeg på indkøb i Amsterdam med min unge forlovede, og trætte satte vi os ned på caféterrassen for at drikke en kop kaffe, og jeg tænkte bare på, om jeg kunne gøre det her, og så designede jeg algoritmen for den korteste vej. . Som sagt var det en tyve minutters opfindelse. Faktisk blev den udgivet i '59, tre år senere. Udgivelsen er stadig læseværdig, den er faktisk ganske fin. En af grundene til at den er så fin var, at jeg designede den uden blyant og papir. Jeg lærte senere, at en af fordelene ved at designe uden blyant og papir er, at du næsten er tvunget til at undgå alle undgåelige kompleksiteter. Til sidst blev den algoritme til min store forbløffelse en af hjørnestenene i min berømmelse.'

Dijkstra tænkte på den korteste vej, mens han arbejdede som programmør på Mathematical Center i Amsterdam i 1956 for at illustrere mulighederne for en ny computer kendt som ARMAC. Hans mål var at vælge både et problem og en løsning (produceret af computeren), som folk uden computerbaggrund kunne forstå. Han udviklede den korteste vejs algoritme og udførte den senere for ARMAC til et vagt forkortet transportkort over 64 byer i Holland (64 byer, så 6 bit ville være tilstrækkeligt til at kode bynummeret). Et år senere stødte han på et andet problem fra hardwareingeniører, der betjener instituttets næste computer: Minimer mængden af ledninger, der kræves for at forbinde stifterne på maskinens bagpanel. Som en løsning genopdagede han algoritmen kaldet Prims minimale spændingstræ-algoritme og udgav den i år 1959.

Grundlæggende om Dijkstras algoritme

Følgende er de grundlæggende begreber i Dijkstras algoritme:

Dijkstras algoritme begynder ved den node, vi vælger (kildenoden), og den undersøger grafen for at finde den korteste vej mellem den node og alle de andre noder i grafen.
Algoritmen gemmer optegnelser over den aktuelt anerkendte korteste afstand fra hver knude til kildenoden, og den opdaterer disse værdier, hvis den finder en kortere vej.
Når først algoritmen har hentet den korteste vej mellem kilden og en anden node, markeres den node som 'besøgt' og inkluderet i stien.
Proceduren fortsætter, indtil alle knudepunkter i grafen er inkluderet i stien. På denne måde har vi en sti, der forbinder kildenoden til alle andre knudepunkter, og følger den kortest mulige sti for at nå hver knude.

Forståelse af, hvordan Dijkstras algoritme fungerer

EN kurve og kildespids er krav til Dijkstras algoritme. Denne algoritme er etableret på Greedy Approach og finder således det lokalt optimale valg (lokale minima i dette tilfælde) ved hvert trin i algoritmen.

Hvert vertex i denne algoritme vil have to egenskaber defineret for det:

Besøgte ejendom
Sti Ejendom

Lad os kort forstå disse egenskaber.

Besøgt ejendom:

Egenskaben 'besøgt' angiver, om knudepunktet er blevet besøgt eller ej.
Vi bruger denne egenskab, så vi ikke besøger nogen node igen.
En knude markeres først som besøgt, når den korteste vej er fundet.

Stiegenskab:

Egenskaben 'sti' gemmer værdien af den aktuelle minimumsti til noden.
Den nuværende minimumsvej antyder den korteste vej, vi har nået denne node indtil nu.
Denne egenskab revideres, når en nabo til noden besøges.
Denne egenskab er vigtig, fordi den gemmer det endelige svar for hver node.

I første omgang markerer vi alle knudepunkter, eller knudepunkter, ubesøgte, da de endnu ikke er besøgt. Stien til alle noderne er også indstillet til uendelig bortset fra kildenoden. Desuden er stien til kildenoden sat til nul (0).

Vi vælger derefter kildenoden og markerer den som besøgt. Derefter får vi adgang til alle de tilstødende noder til kildenoden og udfører afslapning på hver node. Afslapning er processen med at sænke omkostningerne ved at nå en knude ved hjælp af en anden knude.

I afspændingsprocessen revideres stien for hver knude til minimumsværdien blandt knudepunktets aktuelle sti, summen af stien til den forrige knude og stien fra den forrige knude til den aktuelle knude.

Lad os antage, at p[n] er værdien af den aktuelle vej for node n, p[m] er værdien af stien op til den tidligere besøgte node m, og w er vægten af kanten mellem den aktuelle node og tidligere besøgt en (kantvægt mellem n og m).

I matematisk forstand kan afslapning eksemplificeres som:

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

Vi markerer derefter en ubesøgt node med den mindste sti som besøgt i hvert efterfølgende trin og opdaterer naboens stier.

Vi gentager denne procedure, indtil alle knudepunkter i grafen er markeret som besøgt.

Hver gang vi føjer en node til det besøgte sæt, ændres stien til alle dens naboknuder også i overensstemmelse hermed.

Hvis en node efterlades utilgængelig (afbrudt komponent), forbliver dens sti 'uendelig'. Hvis selve kilden er en separat komponent, så forbliver stien til alle andre noder 'uendelig'.

Forstå Dijkstras algoritme med et eksempel

Det følgende er det trin, vi vil følge for at implementere Dijkstras algoritme:

Trin 1: Først vil vi markere kildenoden med en aktuel afstand på 0 og indstille resten af noderne til UENDELIG.

Trin 2: Vi vil derefter indstille den ubesøgte node med den mindste aktuelle afstand som den aktuelle node, antag X.

Trin 3: For hver nabo N af den aktuelle node X: Vi vil derefter tilføje den aktuelle afstand af X med vægten af kanten, der forbinder X-N. Hvis den er mindre end den aktuelle afstand af N, skal du indstille den som den nye aktuelle afstand for N.

Trin 4: Vi vil derefter markere den aktuelle node X som besøgt.

Trin 5: Vi gentager processen fra kl 'Trin 2' hvis der er en ubesøgt node tilbage i grafen.

Lad os nu forstå implementeringen af algoritmen ved hjælp af et eksempel:

Figur 6: Den givne graf

Vi vil bruge ovenstående graf som input, med node EN som kilde.
Først vil vi markere alle noderne som ubesøgte.
Vi vil sætte vejen til 0 ved node EN og UENDELIGHED for alle de andre noder.
Vi vil nu markere kildenoden EN som besøgt og få adgang til dens naboknuder.
Bemærk: Vi har kun tilgået de nærliggende knudepunkter, ikke besøgt dem.
Vi vil nu opdatere stien til node B ved 4 ved hjælp af afslapning, fordi vejen til node EN er 0 og stien fra node EN til B er 4 , og minimum((0 + 4), UENDELIG) er 4 .
Vi vil også opdatere stien til node C ved 5 ved hjælp af afslapning, fordi vejen til node EN er 0 og stien fra node EN til C er 5 , og minimum((0 + 5), UENDELIG) er 5 . Begge naboer til node EN er nu afslappede; derfor kan vi komme videre.
Vi vil nu vælge den næste ubesøgte node med den mindste sti og besøge den. Derfor vil vi besøge node B og udføre afslapning på sine ubesøgte naboer. Efter at have udført afslapning, vejen til node C vil forblive 5 , hvorimod stien til node OG vil blive elleve , og stien til node D vil blive 13 .
Vi vil nu besøge node OG og udføre afslapning på sine naboknuder B, D , og F . Da kun node F er ubesøgt, bliver det afslappet. Således vejen til node B vil forblive som det er, dvs. 4 , stien til node D vil også forblive 13 , og stien til node F vil blive 14 (8 + 6) .
Nu vil vi besøge node D , og kun node F vil være afslappet. Dog vejen til node F vil forblive uændret, dvs. 14 .
Da kun node F er tilbage, vil vi besøge den, men ikke udføre nogen afslapning, da alle dens naboknudepunkter allerede er besøgt.
Når alle grafernes noder er besøgt, slutter programmet.

Derfor er de sidste veje, vi konkluderede,:

hvad er min skærmstørrelse

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

Pseudokode for Dijkstras algoritme

Vi vil nu forstå en pseudokode for Dijkstras algoritme.

delvist derivat i latex

Vi er nødt til at opretholde en registrering af vejafstanden for hver knude. Derfor kan vi gemme vejafstanden for hver knude i et array af størrelse n, hvor n er det samlede antal knudepunkter.
Desuden ønsker vi at hente den korteste vej sammen med længden af den vej. For at overvinde dette problem vil vi kortlægge hver node til den node, der sidst opdaterede sin sti-længde.
Når algoritmen er færdig, kan vi spore destinationsknuden tilbage til kildenoden for at hente stien.
Vi kan bruge en minimum Priority Queue til at hente noden med den mindste vejafstand på en effektiv måde.

Lad os nu implementere en pseudokode af ovenstående illustration:

Pseudokode:

 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]>

Forklaring:

I ovenstående kodestykke har vi inkluderet stdio.h header-fil definerede to konstante værdier: INF = 9999 og MAX = 10 . Vi har erklæret prototypen af funktionen og derefter defineret funktionen for Dijkstras algoritme som Dijkstra Algoritme der accepterer tre argumenter - grafen bestående af noderne, antallet af noder i grafen og kildenoden. Inde i denne funktion har vi defineret nogle datastrukturer såsom en 2D-matrix, der vil fungere som Priority Queue for algoritmen, et array til at styre afstanden mellem noderne, et array til at vedligeholde registreringen af tidligere noder, et array til at gemme oplysninger om de besøgte knudepunkter og nogle heltalsvariabler til lagring af minimumsafstandsværdi, tæller, næste knudepunktsværdi og mere. Vi brugte derefter en indlejret for-loop at iterere gennem grafens noder og føje dem til prioritetskøen i overensstemmelse hermed. Vi har igen brugt for-loop at iterere gennem elementerne i prioritetskøen startende fra kildenoden og opdatere deres afstande. Uden for løkken har vi indstillet afstanden til kildenoden som 0 og markerede det som besøgt i visited_nodes[] array. Vi satte derefter tællerværdien som én og brugte mens loop itererende gennem antallet af noder. Inde i denne løkke har vi sat værdien af minimum_distance som INF og brugte for-loop at opdatere værdien af minimum_distance variabel med minimumsværdien fra a afstand[] array. Vi itererede derefter gennem de ubesøgte naboknuder til den valgte node ved hjælp af for-loop og udførte afspænding. Vi udskrev derefter de resulterende data for afstandene beregnet ved hjælp af Dijkstras algoritme.

I den vigtigste funktion, har vi defineret og erklæret de variable, der repræsenterer grafen, antallet af noder og kildenoden. Endelig har vi ringet til DijkstraAlgorithm() funktion ved at sende de nødvendige parametre.

Som et resultat heraf udskrives de påkrævede kortest mulige stier for hver knude fra kildenoden til brugerne.

Kode til Dijkstras algoritme i C++

Følgende er implementeringen af Dijkstras algoritme i programmeringssproget C++:

Fil: 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;>

Forklaring:

I ovenstående kodestykke inkluderede vi 'iostream' og 'vektor' header-filer og defineret en konstant værdi som MAX_INT = 10000000 . Vi brugte derefter standardnavnerummet og lavede en prototype på DijkstraAlgorithm() fungere. Vi definerede derefter programmets hovedfunktion inden for, som vi har kaldt DijkstraAlgorithm() fungere. Derefter erklærede vi nogle klasser for at skabe hjørner og kanter. Vi har også lavet en prototype på flere funktioner for at finde den kortest mulige vej fra kildepunktet til destinationspunktet og instansieret klasserne Vertex og Edge. Vi definerede derefter begge klasser for at skabe toppunkter og kanter på grafen. Vi har så defineret DijkstraAlgorithm() funktion til at lave en graf og udføre forskellige operationer. Inde i denne funktion har vi erklæret nogle hjørner og kanter. Vi satte derefter kildepunktet for grafen og kaldte Dijkstra() funktion for at finde den kortest mulige afstand og Print_Shortest_Route_To() funktion til at udskrive den korteste afstand fra kildens toppunkt til toppunktet 'F' . Vi har så defineret Dijkstra() funktion til at beregne de kortest mulige afstande af alle toppunkterne fra kildens toppunkt. Vi har også defineret nogle flere funktioner til at finde toppunktet med den korteste afstand for at returnere alle de hjørner, der støder op til det resterende toppunkt, for at returnere afstanden mellem to forbundne toppunkter, for at kontrollere om det valgte toppunkt findes i grafen, og for at udskrive kortest mulige vej fra kildepunktet til destinationspunktet.

Som et resultat, den nødvendige korteste vej for toppunktet 'F' fra kildenoden udskrives for brugerne.

Kode til Dijkstras algoritme i Java

Følgende er implementeringen af Dijkstras algoritme i Java-programmeringssproget:

Fil: 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;>

Forklaring:

I ovenstående kodestykke har vi defineret en offentlig klasse som DijkstraAlgorithm() . Inde i denne klasse har vi defineret en offentlig metode som dijkstraAlgorithm() for at finde den korteste afstand fra kildepunktet til destinationspunktet. Inde i denne metode har vi defineret en variabel til at gemme antallet af noder. Vi har derefter defineret et boolesk array til at gemme informationen vedrørende de besøgte toppunkter og et heltals array til at gemme deres respektive afstande. Til at begynde med erklærede vi værdierne i begge arrays som Falsk og MAX_VALUE , henholdsvis. Vi har også sat afstanden af kildens toppunkt til nul og brugt for-loop for at opdatere afstanden mellem kildehjørnet og destinationsspidserne med minimumsafstanden. Vi har derefter opdateret afstandene for de tilstødende toppunkter af det valgte toppunkt ved at udføre afslapning og udskrevet de korteste afstande for hvert toppunkt. Vi har derefter defineret en metode til at finde den mindste afstand fra kilden til punktet. Vi definerede derefter hovedfunktionen, hvor vi erklærede grafens toppunkter og instansierede DijkstraAlgorithm() klasse. Endelig har vi ringet til dijkstraAlgorithm() metode til at finde den korteste afstand mellem kildehjørnet og destinationsspidserne.

Som et resultat heraf udskrives de påkrævede kortest mulige stier for hver knude fra kildenoden til brugerne.

Kode til Dijkstras algoritme i Python

Følgende er implementeringen af Dijkstras algoritme i Python-programmeringssproget:

Fil: 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>

Produktion

 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

Forklaring:

I ovenstående kodestykke har vi importeret sys modul og erklærede listerne bestående af værdierne for noderne og kanterne. Vi har så defineret en funktion som toBeVisited() for at finde, hvilken node der skal besøges næste gang. Vi fandt derefter det samlede antal knudepunkter i grafen og indstillede de indledende afstande for hver knude. Vi har derefter beregnet minimumsafstanden fra kildenoden til destinationsknuden, udført afslapning på naboknudepunkterne og opdateret afstandene i listen. Vi udskrev derefter disse afstande fra listen til brugerne.

Som et resultat heraf udskrives de påkrævede kortest mulige stier for hver knude fra kildenoden til brugerne.

Tid og rum kompleksitet af Dijkstras algoritme

Tidskompleksiteten af Dijkstras algoritme er O(E log V) , hvor E er antallet af kanter og V er antallet af hjørner.
Rumkompleksiteten af Dijkstras algoritme er O(V), hvor V er antallet af hjørner.

Fordele og ulemper ved Dijkstras algoritme

Lad os diskutere nogle fordele ved Dijkstras algoritme:

En primær fordel ved at bruge Dijkstras algoritme er, at den har en næsten lineær tids- og rumkompleksitet.
Vi kan bruge denne algoritme til at beregne den korteste vej fra et enkelt toppunkt til alle andre toppunkter og et enkelt kildepunkt til et enkelt destinationspunkt ved at stoppe algoritmen, når vi har fået den korteste afstand til destinationspunktet.
Denne algoritme virker kun for rettede vægtede grafer, og alle kanter af denne graf bør være ikke-negative.

På trods af at den har flere fordele, har Dijkstras algoritme også nogle ulemper, såsom:

Dijkstras algoritme udfører en skjult udforskning, der bruger meget tid under processen.
Denne algoritme er impotent til at håndtere negative kanter.
Da denne algoritme går til den acykliske graf, kan den ikke beregne den nøjagtige korteste vej.
Det kræver også vedligeholdelse at føre et register over hjørner, der er blevet besøgt.

Nogle anvendelser af Dijkstras algoritme

Dijkstras algoritme har forskellige applikationer i den virkelige verden, hvoraf nogle er angivet nedenfor:

Digitale korttjenester i Google Maps:Der er forskellige tidspunkter, hvor vi har forsøgt at finde afstanden i Google Maps enten fra vores placering til den nærmeste foretrukne placering eller fra en by til en anden, som omfatter flere ruter/stier, der forbinder dem; dog skal applikationen vise minimumsafstanden. Dette er kun muligt, fordi Dijkstras algoritme hjælper applikationen med at finde den korteste mellem to givne placeringer langs stien. Lad os betragte USA som en graf, hvor byerne/stederne er repræsenteret som hjørner, og ruterne mellem to byer/steder er repræsenteret som kanter. Derefter kan vi ved hjælp af Dijkstras algoritme beregne de korteste ruter mellem to byer/steder.Sociale netværksapplikationer:I mange applikationer som Facebook, Twitter, Instagram og flere har mange af os måske observeret, at disse apps foreslår en liste over venner, som en bestemt bruger måske kender. Hvordan implementerer mange sociale medievirksomheder denne type funktion på en effektiv måde, specifikt når systemet har over en milliard brugere? Svaret på dette spørgsmål er Dijkstras algoritme. Standard Dijkstras algoritme bruges generelt til at estimere den korteste afstand mellem brugerne målt gennem forbindelserne eller gensidigheden mellem dem. Når sociale netværk er meget små, bruger det standard Dijkstras algoritme ud over nogle andre funktioner for at bestemme de korteste veje. Men når grafen er meget større, tager standardalgoritmen flere sekunder at tælle, og derfor bruges nogle avancerede algoritmer som alternativ.Telefonnetværk:Som nogle af os måske ved, har hver transmissionslinje i et telefonnetværk en båndbredde, 'b'. Båndbredden er den højeste frekvens, som transmissionslinjen kan understøtte. Generelt, hvis frekvensen af signalet er højere i en specifik linje, reduceres signalet med denne linje. Båndbredde repræsenterer mængden af information, der kan transmitteres af linjen. Lad os betragte en by som en graf, hvor koblingsstationerne er repræsenteret ved hjælp af hjørnerne, transmissionslinjerne er repræsenteret som kanterne, og båndbredden, 'b', er repræsenteret ved hjælp af vægten af kanterne. Således, som vi kan observere, kan telefonnettet også falde ind under kategorien med korteste afstandsproblem og kan løses ved hjælp af Dijkstras algoritme.Flyprogram:Antag, at en person har brug for software til at udarbejde en dagsorden for flyvninger til kunder. Agenten har adgang til en database med alle flyvninger og lufthavne. Udover flynummer, afgangslufthavn og destination har flyene også afgangs- og ankomsttider. Så for at bestemme det tidligste ankomsttidspunkt for den valgte destination fra den oprindelige lufthavn og givet starttidspunkt, gør agenterne brug af Dijkstras algoritme.IP-routing for at finde den åbne korteste vej først:Open Shortest Path First (forkortet OSPF) er en link-state routing-protokol, der bruges til at finde den bedste sti mellem kilde- og destinationsrouteren ved hjælp af sin egen Shortest Path First. Dijkstras algoritme bruges i vid udstrækning i de routingprotokoller, der kræves af routerne for at opdatere deres videresendelsestabel. Algoritmen giver den korteste omkostningsvej fra kilderouteren til de andre routere, der findes i netværket.Robotsti:I disse dage er der opstået droner og robotter, nogle betjente manuelt og nogle automatisk. Dronerne og robotterne, som betjenes automatisk og bruges til at levere pakkerne til et givet sted eller bruges til en bestemt opgave, er konfigureret med Dijkstras algoritmemodul, så når kilden og destinationen er kendt, vil dronen og robotten bevæge sig i den bestilte retning ved at følge den korteste vej og holde den tid, det tager at levere pakkerne på et minimum.Udpeg filserveren:Dijkstras algoritme bruges også til at udpege en filserver i et lokalt netværk (LAN). Antag, at der er behov for en uendelig periode til overførsel af filerne fra en computer til en anden. Så for at minimere antallet af 'hop' fra filserveren til hver anden computer på netværket, vil vi bruge Dijkstras algoritme. Denne algoritme vil returnere den korteste vej mellem netværkene, hvilket resulterer i det mindste antal hop.

Konklusionen

I ovenstående tutorial har vi for det første forstået de grundlæggende begreber i Graph sammen med dets typer og applikationer.
Vi lærte derefter om Dijkstras algoritme og dens historie.
Vi har også forstået den grundlæggende funktion af Dijkstras algoritme ved hjælp af et eksempel.
Derefter studerede vi, hvordan man skriver kode til Dijkstras algoritme ved hjælp af Pseudokode.
Vi observerede dens implementering i programmeringssprog som C, C++, Java og Python med korrekte output og forklaringer.
Vi har også forstået tids- og rumkompleksiteten af Dijkstras algoritme.
Til sidst har vi diskuteret fordele og ulemper ved Dijkstras algoritme og nogle af dens virkelige applikationer.