DIJKSTRAS KORTESTE VEI-ALGORITME MED EKSEMPLER

Følgende opplæring vil lære oss om Dijkstras Shortest Path Algorithm. Vi vil forstå hvordan Dijkstras algoritme fungerer med en trinnvis grafisk forklaring.

Vi vil dekke følgende:

En kort oversikt over de grunnleggende konseptene for graf
Forstå bruken av Dijkstras algoritme
Forstå hvordan algoritmen fungerer med et trinn-for-trinn-eksempel

Så la oss komme i gang.

En kort introduksjon til grafer

Grafer er ikke-lineære datastrukturer som representerer 'forbindelsene' mellom elementene. Disse elementene er kjent som Topppunkter , og linjene eller buene som forbinder to punkter i grafen er kjent som Kanter . Mer formelt omfatter en graf et sett med hjørner (V) og et sett med kanter (E) . Grafen er merket med G(V, E) .

Komponenter i en graf

Topppunkter:Topppunkter er de grunnleggende enhetene i grafen som brukes til å representere virkelige objekter, personer eller enheter. Noen ganger er hjørner også kjent som noder.Kanter:Kanter tegnes eller brukes til å koble sammen to hjørner av grafen. Noen ganger er kanter også kjent som buer.

Følgende figur viser en grafisk representasjon av en graf:

Figur 1: Grafisk representasjon av en graf

I figuren ovenfor er toppunktene/nodene merket med fargede sirkler, og kantene er merket med linjene som forbinder nodene.

Anvendelser av grafene

Grafer brukes til å løse mange virkelige problemer. Grafer brukes til å representere nettverkene. Disse nettverkene kan inkludere telefon- eller kretsnettverk eller stier i en by.

For eksempel kan vi bruke Graphs til å designe en transportnettverksmodell der toppunktene viser fasilitetene som sender eller mottar produktene, og kantene representerer veier eller stier som forbinder dem. Følgende er en billedlig fremstilling av det samme:

Figur 2: Bildepresentasjon av transportnettverket

Grafer brukes også i forskjellige sosiale medieplattformer som LinkedIn, Facebook, Twitter og mer. For eksempel bruker plattformer som Facebook Graphs for å lagre dataene til brukerne deres der hver person er indikert med et toppunkt, og hver av dem er en struktur som inneholder informasjon som person-ID, navn, kjønn, adresse, etc.

Typer grafer

Grafene kan kategoriseres i to typer:

Udirigert graf
Regissert graf

Udirigert graf: En graf med kanter som ikke har en retning kalles en urettet graf. Kantene på denne grafen innebærer et toveis forhold der hver kant kan krysses i begge retninger. Følgende figur viser en enkel urettet graf med fire noder og fem kanter.

Figur 3: En enkel udirigert graf

Regissert graf: En graf med kanter med retning kalles en rettet graf. Kantene på denne grafen innebærer et enveisforhold der hver kant bare kan krysses i en enkelt retning. Følgende figur viser en enkel rettet graf med fire noder og fem kanter.

Figur 4: En enkel rettet graf

Den absolutte lengden, posisjonen eller orienteringen til kantene i en grafillustrasjon har karakteristisk ikke betydning. Med andre ord kan vi visualisere den samme grafen på forskjellige måter ved å omorganisere toppunktene eller forvrenge kantene hvis den underliggende strukturen til grafen ikke endres.

Hva er vektede grafer?

En graf sies å være vektet hvis hver kant er tildelt en 'vekt'. Vekten til en kant kan angi avstand, tid eller noe som helst som modellerer 'forbindelsen' mellom paret av topper den forbinder.

For eksempel kan vi observere et blått tall ved siden av hver kant i den følgende figuren av den vektede grafen. Dette tallet brukes til å angi vekten til den tilsvarende kanten.

Figur 5: Et eksempel på en vektet graf

En introduksjon til Dijkstras algoritme

Nå som vi kjenner noen grunnleggende grafer-konsepter, la oss dykke ned i å forstå konseptet med Dijkstras algoritme.

Har du noen gang lurt på hvordan Google Maps finner den korteste og raskeste ruten mellom to steder?

Vel, svaret er Dijkstras algoritme . Dijkstras algoritme er en grafalgoritme som finner den korteste veien fra et kildepunkt til alle andre toppunkter i grafen (enkeltkilde korteste vei). Det er en type grådig algoritme som bare fungerer på vektede grafer med positive vekter. Tidskompleksiteten til Dijkstras algoritme er O(V²) ved hjelp av tilstøtende matriserepresentasjon av grafen. Denne tiden kan kompleksiteten reduseres til O((V + E) log V) ved hjelp av en tilstøtende listerepresentasjon av grafen, hvor I er antall hjørner og OG er antall kanter i grafen.

hvis annet i java

Historien om Dijkstras algoritme

Dijkstras algoritme ble designet og utgitt av Dr. Edsger W. Dijkstra , en nederlandsk informatiker, programvareingeniør, programmerer, vitenskapsessayist og systemviter.

Under et intervju med Philip L. Frana for Communications of the ACM journal i år 2001, avslørte Dr. Edsger W. Dijkstra:

'Hva er den korteste veien å reise fra Rotterdam til Groningen, generelt: fra gitt by til gitt by? Det er algoritmen for den korteste veien, som jeg designet på omtrent tjue minutter. En morgen var jeg på shopping i Amsterdam med min unge forlovede, og slitne satte vi oss ned på kaféterrassen for å drikke en kopp kaffe, og jeg tenkte bare på om jeg kunne gjøre dette, og så designet jeg algoritmen for den korteste veien . Det var som sagt en tjue minutters oppfinnelse. Faktisk ble den publisert i '59, tre år senere. Publikasjonen er fortsatt lesbar, den er faktisk ganske fin. En av grunnene til at den er så fin var at jeg designet den uten blyant og papir. Jeg lærte senere at en av fordelene med å designe uten blyant og papir er at du nesten er tvunget til å unngå all unngåelig kompleksitet. Til slutt ble den algoritmen til min store forbauselse, en av hjørnesteinene i min berømmelse.'

Dijkstra tenkte på den korteste veien mens han jobbet som programmerer ved Mathematical Center i Amsterdam i 1956 for å illustrere egenskapene til en ny datamaskin kjent som ARMAC. Målet hans var å velge både et problem og en løsning (produsert av datamaskinen) som folk uten databakgrunn kunne forstå. Han utviklet den korteste veialgoritmen og utførte den senere for ARMAC for et vagt forkortet transportkart over 64 byer i Nederland (64 byer, så 6 biter ville være tilstrekkelig til å kode bynummeret). Et år senere kom han over et annet problem fra maskinvareingeniører som driver den neste datamaskinen til instituttet: Minimer mengden ledning som kreves for å koble til pinnene på maskinens bakpanel. Som en løsning gjenoppdaget han algoritmen kalt Prims minimal spanning tree-algoritme og publiserte den i 1959.

Grunnleggende om Dijkstras algoritme

Følgende er de grunnleggende konseptene til Dijkstras algoritme:

Dijkstras algoritme begynner ved noden vi velger (kildenoden), og den undersøker grafen for å finne den korteste veien mellom den noden og alle de andre nodene i grafen.
Algoritmen holder oversikt over den nåværende erkjente korteste avstanden fra hver node til kildenoden, og den oppdaterer disse verdiene hvis den finner en kortere vei.
Når algoritmen har hentet den korteste veien mellom kilden og en annen node, blir den noden merket som 'besøkt' og inkludert i banen.
Prosedyren fortsetter til alle nodene i grafen er inkludert i banen. På denne måten har vi en bane som forbinder kildenoden til alle andre noder, og følger den kortest mulige veien for å nå hver node.

Forstå hvordan Dijkstras algoritme fungerer

EN kurve og kildetoppunktet er krav til Dijkstras algoritme. Denne algoritmen er etablert på Greedy Approach og finner dermed det lokalt optimale valget (lokale minima i dette tilfellet) ved hvert trinn i algoritmen.

Hver toppunkt i denne algoritmen vil ha to egenskaper definert for den:

Besøkte eiendom
Sti Eiendom

La oss kort forstå disse egenskapene.

Besøkt eiendom:

Egenskapen 'besøkt' angir om noden har blitt besøkt eller ikke.
Vi bruker denne egenskapen slik at vi ikke besøker noen node igjen.
En node merkes besøkt først når den korteste veien er funnet.

Baneegenskap:

'path'-egenskapen lagrer verdien av gjeldende minimumsbane til noden.
Den nåværende minimumsveien innebærer den korteste veien vi har nådd denne noden til nå.
Denne egenskapen revideres når en nabo til noden besøkes.
Denne egenskapen er betydelig fordi den vil lagre det endelige svaret for hver node.

Til å begynne med markerer vi alle toppunktene, eller nodene, ubesøkte da de ennå ikke er besøkt. Banen til alle nodene er også satt til uendelig bortsett fra kildenoden. Dessuten er banen til kildenoden satt til null (0).

Vi velger deretter kildenoden og merker den som besøkt. Etter det får vi tilgang til alle nabonodene til kildenoden og utfører avspenning på hver node. Avslapping er prosessen med å senke kostnadene for å nå en node ved hjelp av en annen node.

I prosessen med avspenning blir banen til hver node revidert til minimumsverdien blant nodens nåværende bane, summen av banen til forrige node og banen fra forrige node til nåværende node.

La oss anta at p[n] er verdien av den nåværende banen for node n, p[m] er verdien av banen opp til den tidligere besøkte noden m, og w er vekten av kanten mellom den nåværende noden og tidligere besøkt en (kantvekt mellom n og m).

I matematisk forstand kan avslapning eksemplifiseres som:

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

Vi markerer deretter en ubesøkt node med den minste banen som er besøkt i hvert påfølgende trinn og oppdaterer naboens stier.

Vi gjentar denne prosedyren til alle nodene i grafen er merket som besøkt.

Hver gang vi legger til en node til det besøkte settet, endres også banen til alle nabonodene tilsvarende.

Hvis en node ikke kan nås (frakoblet komponent), forblir banen 'uendelig'. I tilfelle selve kilden er en separat komponent, forblir banen til alle andre noder 'uendelig'.

Forstå Dijkstras algoritme med et eksempel

Følgende er trinnet vi vil følge for å implementere Dijkstras algoritme:

Trinn 1: Først vil vi merke kildenoden med en gjeldende avstand på 0 og sette resten av nodene til INFINITY.

Steg 2: Vi vil da sette den ubesøkte noden med den minste strømavstanden som gjeldende node, anta X.

Trinn 3: For hver nabo N til gjeldende node X: Vi vil da legge til gjeldende avstand til X med vekten av kanten som forbinder X-N. Hvis den er mindre enn den nåværende avstanden til N, sett den som den nye gjeldende avstanden til N.

Trinn 4: Vi vil da merke gjeldende node X som besøkt.

Trinn 5: Vi vil gjenta prosessen fra 'Steg 2' hvis det er noen ubesøkt node igjen i grafen.

La oss nå forstå implementeringen av algoritmen ved hjelp av et eksempel:

Figur 6: Den gitte grafen

Vi vil bruke grafen ovenfor som input, med node EN som kilde.
Først vil vi merke alle nodene som ubesøkte.
Vi vil sette veien til 0 ved node EN og EVIGHET for alle de andre nodene.
Vi skal nå merke kildenoden EN som besøkt og få tilgang til de nærliggende nodene.
Merk: Vi har kun fått tilgang til nabonodene, ikke besøkt dem.
Vi vil nå oppdatere banen til noden B av 4 ved hjelp av avslapning fordi banen til node EN er 0 og banen fra noden EN til B er 4 , og minimum((0 + 4), UENDELIG) er 4 .
Vi vil også oppdatere banen til node C av 5 ved hjelp av avslapning fordi banen til node EN er 0 og banen fra noden EN til C er 5 , og minimum((0 + 5), UENDELIG) er 5 . Begge naboene til node EN er nå avslappet; derfor kan vi gå videre.
Vi vil nå velge den neste ubesøkte noden med den minste banen og besøke den. Derfor vil vi besøke node B og utføre avslapping på sine ubesøkte naboer. Etter å ha utført avslapning, veien til node C vil forbli 5 , mens banen til node OG vil bli elleve , og banen til noden D vil bli 1. 3 .
Vi vil nå besøke node OG og utføre avslapning på de nærliggende nodene B, D , og F . Siden bare node F er ubesøkt, blir det avslappet. Dermed veien til node B vil forbli som det er, dvs. 4 , banen til node D vil også forbli 1. 3 , og banen til noden F vil bli 14 (8 + 6) .
Nå skal vi besøke node D , og bare node F vil være avslappet. Imidlertid veien til node F vil forbli uendret, dvs. 14 .
Siden bare node F er igjen, vil vi besøke den, men ikke utføre noen avslapning da alle nabonodene allerede er besøkt.
Når alle nodene til grafene er besøkt, avsluttes programmet.

Derfor er de siste veiene vi konkluderte med:

hva er skjermstørrelsen min

 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 nå forstå en pseudokode for Dijkstras algoritme.

delvis derivat i lateks

Vi må holde oversikt over baneavstanden til hver node. Derfor kan vi lagre baneavstanden til hver node i en matrise med størrelse n, der n er det totale antallet noder.
Dessuten ønsker vi å hente den korteste veien sammen med lengden på den veien. For å overvinne dette problemet vil vi kartlegge hver node til noden som sist oppdaterte banelengden.
Når algoritmen er fullført, kan vi spore destinasjonsnoden tilbake til kildenoden for å hente banen.
Vi kan bruke en minimum Priority Queue for å hente noden med minst baneavstand på en effektiv måte.

La oss nå implementere en pseudokode av illustrasjonen ovenfor:

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 kodebiten ovenfor har vi inkludert stio.h header-fil definerte to konstante verdier: INF = 9999 og MAKS = 10 . Vi har erklært prototypingen av funksjonen og deretter definert funksjonen for Dijkstras algoritme som Dijkstra Algoritme som godtar tre argumenter - Graph som består av nodene, antall noder i Graph og kildenoden. Inne i denne funksjonen har vi definert noen datastrukturer, for eksempel en 2D-matrise som vil fungere som Priority Queue for algoritmen, en matrise for å styre avstanden mellom nodene, en matrise for å opprettholde registreringen av tidligere noder, en matrise for å lagre informasjon om besøkte noder, og noen heltallsvariabler for å lagre minimumsavstandsverdi, teller, neste nodeverdi og mer. Vi brukte da en nestet for-løkke å iterere gjennom nodene i grafen og legge dem til i prioritetskøen tilsvarende. Vi har igjen brukt for-løkke å iterere gjennom elementene i prioritetskøen fra kildenoden og oppdatere avstandene deres. Utenfor loopen har vi satt avstanden til kildenoden som 0 og merket den som besøkt i besøkte_noder[] array. Vi satte deretter tellerverdien som én og brukte samtidig som løkke som itererer gjennom antall noder. Inne i denne sløyfen har vi satt verdien på minimum_distanse som INF og brukte for-løkke for å oppdatere verdien av minimum_distanse variabel med minimumsverdien fra a avstand[] array. Vi itererte deretter gjennom de ubesøkte nabonodene til den valgte noden ved å bruke for-løkke og utførte avspenning. Vi skrev deretter ut de resulterende dataene for avstandene beregnet ved hjelp av Dijkstras algoritme.

I hoved- funksjon, har vi definert og erklært variablene som representerer grafen, antall noder og kildenoden. Endelig har vi ringt DijkstraAlgorithm() funksjon ved å sende de nødvendige parameterne.

Som et resultat blir de nødvendige kortest mulige banene for hver node fra kildenoden skrevet ut for brukerne.

Kode for Dijkstras algoritme i C++

Følgende er implementeringen av Dijkstras algoritme i programmeringsspråket 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 kodebiten ovenfor inkluderte vi 'iostream' og 'vektor' header-filer og definerte en konstant verdi som MAX_INT = 10000000 . Vi brukte deretter standard navneområde og prototypte DijkstraAlgorithm() funksjon. Vi definerte deretter hovedfunksjonen til programmet innenfor, som vi har kalt DijkstraAlgorithm() funksjon. Etter det erklærte vi noen klasser for å lage hjørner og kanter. Vi har også prototypet flere funksjoner for å finne kortest mulig vei fra kildetoppunktet til destinasjonsvertekset og instansiert Vertex- og Edge-klassene. Vi definerte deretter begge klassene for å lage toppunktene og kantene på grafen. Vi har da definert DijkstraAlgorithm() funksjon for å lage en graf og utføre forskjellige operasjoner. Inne i denne funksjonen har vi deklarert noen hjørner og kanter. Vi satte deretter kildetoppunktet til grafen og kalte Dijkstra() funksjon for å finne kortest mulig avstand og Print_Shortest_Route_To() funksjon for å skrive ut den korteste avstanden fra kildetoppunktet til toppunktet 'F' . Vi har da definert Dijkstra() funksjon for å beregne kortest mulig avstander til alle toppunktene fra kildetoppunktet. Vi har også definert noen flere funksjoner for å finne toppunktet med kortest avstand for å returnere alle toppunktene ved siden av det gjenværende toppunktet, for å returnere avstanden mellom to sammenkoblede toppunkter, for å sjekke om det valgte toppunktet finnes i grafen, og for å skrive ut kortest mulig vei fra kildetoppunktet til destinasjonstoppunktet.

Som et resultat, den nødvendige korteste banen for toppunktet 'F' fra kildenoden skrives ut for brukerne.

Kode for Dijkstras algoritme i Java

Følgende er implementeringen av Dijkstras algoritme i programmeringsspråket Java:

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 kodebiten ovenfor har vi definert en offentlig klasse som DijkstraAlgorithm() . Inne i denne klassen har vi definert en offentlig metode som dijkstraAlgorithm() for å finne den korteste avstanden fra kildetoppunktet til destinasjonstoppunktet. Inne i denne metoden har vi definert en variabel for å lagre antall noder. Vi har deretter definert en boolsk matrise for å lagre informasjonen om de besøkte toppunktene og en heltallsmatrise for å lagre deres respektive avstander. Opprinnelig erklærte vi verdiene i begge matrisene som Falsk og MAX_VALUE , henholdsvis. Vi har også satt avstanden til kildetoppunktet til null og brukt for-løkke for å oppdatere avstanden mellom kildetoppunktet og destinasjonspunktene med minimumsavstanden. Vi har deretter oppdatert avstandene til nabopunktene til det valgte toppunktet ved å utføre avspenning og skrevet ut de korteste avstandene for hvert toppunkt. Vi har da definert en metode for å finne minimumsavstanden fra kildetoppunktet til destinasjonsvertekset. Vi definerte deretter hovedfunksjonen der vi erklærte toppunktene til grafen og instansierte DijkstraAlgorithm() klasse. Til slutt har vi kalt dijkstraAlgorithm() metode for å finne den korteste avstanden mellom kildetoppunktet og destinasjonspunktene.

Som et resultat blir de nødvendige kortest mulige banene for hver node fra kildenoden skrevet ut for brukerne.

Kode for Dijkstras algoritme i Python

Følgende er implementeringen av Dijkstras algoritme i Python-programmeringsspråket:

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>

Produksjon

 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 kodebiten ovenfor har vi importert sys modul og erklærte listene som består av verdiene for nodene og kantene. Vi har da definert en funksjon som toBeVisited() for å finne hvilken node som skal besøkes neste gang. Vi fant så det totale antallet noder i grafen og satte inn startavstandene for hver node. Vi har da beregnet minimumsavstanden fra kildenoden til destinasjonsnoden, utført avspenning på nabonodene, og oppdatert avstandene i listen. Vi skrev deretter ut disse avstandene fra listen for brukerne.

Som et resultat blir de nødvendige kortest mulige banene for hver node fra kildenoden skrevet ut for brukerne.

Tid og rom kompleksiteten til Dijkstras algoritme

Tidskompleksiteten til Dijkstras algoritme er O(E log V) , hvor E er antall kanter og V er antall toppunkter.
Romkompleksiteten til Dijkstras algoritme er O(V), der V er antall toppunkter.

Fordeler og ulemper med Dijkstras algoritme

La oss diskutere noen fordeler med Dijkstras algoritme:

En primær fordel med å bruke Dijkstras algoritme er at den har en nesten lineær tid og romkompleksitet.
Vi kan bruke denne algoritmen til å beregne den korteste veien fra et enkelt toppunkt til alle andre toppunkter og et enkelt kildepunkt til et enkelt destinasjonspunkt ved å stoppe algoritmen når vi får den korteste avstanden for destinasjonstoppunktet.
Denne algoritmen fungerer bare for rettet vektede grafer, og alle kantene på denne grafen skal være ikke-negative.

Til tross for flere fordeler, har Dijkstras algoritme også noen ulemper, for eksempel:

Dijkstras algoritme utfører en skjult utforskning som bruker mye tid under prosessen.
Denne algoritmen er impotent til å håndtere negative kanter.
Siden denne algoritmen går til den asykliske grafen, kan den ikke beregne den nøyaktige korteste veien.
Det krever også vedlikehold for å føre oversikt over toppunkter som er besøkt.

Noen applikasjoner av Dijkstras algoritme

Dijkstras algoritme har forskjellige applikasjoner i den virkelige verden, hvorav noen er oppgitt nedenfor:

Digitale karttjenester i Google Maps:Det er flere ganger vi har forsøkt å finne avstanden i Google Maps enten fra vår plassering til nærmeste foretrukne plassering eller fra en by til en annen, som omfatter flere ruter/stier som forbinder dem; applikasjonen må imidlertid vise minimumsavstanden. Dette er bare mulig fordi Dijkstras algoritme hjelper applikasjonen med å finne den korteste mellom to gitte steder langs banen. La oss se på USA som en graf der byene/stedene er representert som hjørner, og rutene mellom to byer/steder er representert som kanter. Deretter kan vi ved hjelp av Dijkstras algoritme beregne de korteste rutene mellom to byer/steder.Sosiale nettverksapplikasjoner:I mange applikasjoner som Facebook, Twitter, Instagram og flere, kan mange av oss ha observert at disse appene foreslår listen over venner som en spesifikk bruker kanskje kjenner. Hvordan implementerer mange sosiale medieselskaper denne typen funksjoner på en effektiv og effektiv måte, spesielt når systemet har over en milliard brukere? Svaret på dette spørsmålet er Dijkstras algoritme. Standard Dijkstras algoritme brukes vanligvis til å estimere den korteste avstanden mellom brukerne målt gjennom forbindelsene eller gjensidigheten mellom dem. Når sosiale nettverk er svært små, bruker det standard Dijkstras algoritme i tillegg til noen andre funksjoner for å bestemme de korteste veiene. Men når grafen er mye større, tar standardalgoritmen flere sekunder å telle, og derfor brukes noen avanserte algoritmer som alternativ.Telefonnettverk:Som noen av oss kanskje vet, i et telefonnettverk har hver overføringslinje en båndbredde, 'b'. Båndbredden er den høyeste frekvensen som overføringslinjen kan støtte. Generelt, hvis frekvensen til signalet er høyere i en spesifikk linje, reduseres signalet med den linjen. Båndbredde representerer mengden informasjon som kan overføres av linjen. La oss betrakte en by som en graf der koblingsstasjonene er representert ved hjelp av toppunktene, overføringslinjene er representert som kantene, og båndbredden, 'b', er representert ved å bruke vekten av kantene. Dermed, som vi kan observere, kan telefonnettet også falle inn i kategorien med korteste avstandsproblem og kan løses ved hjelp av Dijkstras algoritme.Flyprogram:Anta at en person trenger programvare for å utarbeide en agenda med flyreiser for kunder. Agenten har tilgang til en database med alle flyreiser og flyplasser. I tillegg til flightnummer, opprinnelsesflyplass og destinasjon, har flyvningene også avgangs- og ankomsttider. Så, for å bestemme den tidligste ankomsttiden for den valgte destinasjonen fra den opprinnelige flyplassen og gitt starttidspunkt, bruker agentene Dijkstras algoritme.IP-ruting for å finne Open Shortest Path først:Open Shortest Path First (forkortet OSPF) er en link-state ruting-protokoll som brukes til å finne den beste banen mellom kilden og destinasjonsruteren ved hjelp av sin egen Shortest Path First. Dijkstras algoritme er mye brukt i rutingprotokollene som kreves av ruterne for å oppdatere videresendingstabellen deres. Algoritmen gir den korteste kostnadsveien fra kilderuteren til de andre ruterne som finnes i nettverket.Robotbane:I disse dager har droner og roboter blitt til, noen operert manuelt og noen automatisk. Dronene og robotene som betjenes automatisk og brukes til å levere pakkene til et gitt sted eller brukes til en bestemt oppgave er konfigurert med Dijkstras algoritmemodul slik at når kilden og destinasjonen er kjent, vil dronen og roboten bevege seg i den bestilte retningen ved å følge den korteste veien og holde tiden det tar på et minimum for å levere pakkene.Angi filserveren:Dijkstras algoritme brukes også til å angi en filserver i et lokalt nettverk (LAN). Anta at en uendelig tidsperiode er nødvendig for overføring av filene fra en datamaskin til en annen. Så for å minimere antall 'hopp' fra filserveren til alle andre datamaskiner på nettverket, vil vi bruke Dijkstras algoritme. Denne algoritmen vil returnere den korteste veien mellom nettverkene, noe som resulterer i minimum antall hopp.

Konklusjonen

I opplæringen ovenfor har vi for det første forstått de grunnleggende konseptene til Graph sammen med dens typer og applikasjoner.
Vi lærte deretter om Dijkstras algoritme og dens historie.
Vi har også forstått den grunnleggende funksjonen til Dijkstras algoritme ved hjelp av et eksempel.
Etter det studerte vi hvordan man skriver kode for Dijkstras algoritme ved hjelp av Pseudokode.
Vi observerte implementeringen i programmeringsspråk som C, C++, Java og Python med riktige utdata og forklaringer.
Vi har også forstått kompleksiteten av tid og rom til Dijkstras algoritme.
Til slutt har vi diskutert fordelene og ulempene med Dijkstras algoritme og noen av dens virkelige applikasjoner.