DIJKSTRAS SHORTEST PATH ALGORITHM MED EXEMPEL

Följande handledning kommer att lära oss om Dijkstras Shortest Path Algorithm. Vi kommer att förstå hur Dijkstras algoritm fungerar med en stegvis grafisk förklaring.

Vi kommer att täcka följande:

En kort översikt av grafens grundläggande begrepp
Förstå användningen av Dijkstras algoritm
Förstå hur algoritmen fungerar med ett steg-för-steg-exempel

Så, låt oss börja.

En kort introduktion till grafer

Grafer är icke-linjära datastrukturer som representerar 'kopplingarna' mellan elementen. Dessa element är kända som Vertices , och linjerna eller bågarna som förbinder två hörn i grafen är kända som Kanter . Mer formellt omfattar en graf en uppsättning Vertices (V) och en uppsättning kanter (E) . Grafen betecknas med G(V, E) .

Komponenter i en graf

Vertices:Vertices är de grundläggande enheterna i grafen som används för att representera verkliga objekt, personer eller enheter. Ibland är hörn också kända som noder.Kanter:Kanter ritas eller används för att koppla samman två hörn av grafen. Ibland är kanter också kända som bågar.

Följande figur visar en grafisk representation av en graf:

kantigt material

Figur 1: Grafisk representation av en graf

I figuren ovan är Vertices/Noderna betecknade med färgade cirklar, och Edges betecknas med linjerna som förbinder noderna.

Tillämpningar av graferna

Grafer används för att lösa många verkliga problem. Grafer används för att representera nätverken. Dessa nätverk kan innefatta telefon- eller kretsnät eller vägar i en stad.

Till exempel kan vi använda grafer för att designa en transportnätverksmodell där hörnen visar anläggningarna som skickar eller tar emot produkterna, och kanterna representerar vägar eller stigar som förbinder dem. Följande är en bildrepresentation av detsamma:

Figur 2: Bildrepresentation av transportnätverk

Grafer används också i olika sociala medieplattformar som LinkedIn, Facebook, Twitter och mer. Till exempel använder plattformar som Facebook Graphs för att lagra data från sina användare där varje person är indikerad med en vertex, och var och en av dem är en struktur som innehåller information som person-ID, namn, kön, adress, etc.

Typer av grafer

Graferna kan delas in i två typer:

Oriktad graf
Regisserad graf

Oriktad graf: En graf med kanter som inte har en riktning kallas en oriktad graf. Kanterna på denna graf innebär ett tvåvägsförhållande där varje kant kan korsas i båda riktningarna. Följande figur visar en enkel oriktad graf med fyra noder och fem kanter.

Figur 3: En enkel oriktad graf

Riktad graf: En graf med kanter med riktning kallas en riktad graf. Kanterna på denna graf antyder ett enkelriktat förhållande där varje kant endast kan passeras i en enda riktning. Följande figur visar en enkel riktad graf med fyra noder och fem kanter.

Figur 4: En enkel riktad graf

Den absoluta längden, positionen eller orienteringen av kanterna i en grafillustration har typiskt ingen betydelse. Med andra ord kan vi visualisera samma graf på olika sätt genom att ordna om hörnen eller förvränga kanterna om den underliggande strukturen i grafen inte förändras.

Vad är viktade grafer?

En graf sägs vara viktad om varje kant tilldelas en 'vikt'. Vikten av en kant kan beteckna avstånd, tid eller något annat som modellerar 'kopplingen' mellan paret av hörn den förbinder.

Till exempel kan vi observera ett blått nummer bredvid varje kant i följande figur av den viktade grafen. Detta nummer används för att beteckna vikten av motsvarande kant.

Figur 5: Ett exempel på en viktad graf

En introduktion till Dijkstras algoritm

Nu när vi känner till några grundläggande grafer-koncept, låt oss dyka ner i att förstå konceptet med Dijkstras algoritm.

Har du någonsin undrat hur Google Maps hittar den kortaste och snabbaste vägen mellan två platser?

Tja, svaret är Dijkstras algoritm . Dijkstras algoritm är en grafalgoritm som hittar den kortaste vägen från ett källpunkt till alla andra hörn i grafen (enkel källas kortaste väg). Det är en typ av girig algoritm som bara fungerar på viktade grafer med positiva vikter. Tidskomplexiteten hos Dijkstras algoritm är O(V²) med hjälp av den närliggande matrisrepresentationen av grafen. Denna tid komplexitet kan reduceras till O((V + E) log V) med hjälp av en närliggande listrepresentation av grafen, där I är antalet hörn och OCH är antalet kanter i grafen.

Historien om Dijkstras algoritm

Dijkstras algoritm designades och publicerades av Dr. Edsger W. Dijkstra , en holländsk datavetare, mjukvaruingenjör, programmerare, vetenskapsessäist och systemvetare.

sorterad tuppel python

Under en intervju med Philip L. Frana för Communications of the ACM Journal år 2001, avslöjade Dr. Edsger W. Dijkstra:

'Vad är det kortaste sättet att resa från Rotterdam till Groningen, i allmänhet: från given stad till given stad? Det är algoritmen för den kortaste vägen, som jag designade på cirka tjugo minuter. En morgon var jag och handlade i Amsterdam med min unga fästmö, och trötta satte vi oss ner på caféterrassen för att dricka en kopp kaffe och jag tänkte bara på om jag kunde göra det här, och jag designade sedan algoritmen för den kortaste vägen . Det var som sagt en tjugo minuters uppfinning. Faktum är att den publicerades 59, tre år senare. Publikationen är fortfarande läsbar, den är faktiskt ganska fin. En av anledningarna till att den är så fin var att jag designade den utan penna och papper. Jag lärde mig senare att en av fördelarna med att designa utan penna och papper är att man nästan tvingas undvika alla svårigheter som kan undvikas. Så småningom blev den algoritmen till min stora förvåning en av hörnstenarna i min berömmelse.'

Dijkstra tänkte på problemet med den kortaste vägen när han arbetade som programmerare vid Mathematical Center i Amsterdam 1956 för att illustrera kapaciteten hos en ny dator känd som ARMAC. Hans mål var att välja både ett problem och en lösning (producerad av datorn) som människor utan datorbakgrund kunde förstå. Han utvecklade den kortaste vägalgoritmen och utförde den senare för ARMAC för en vagt förkortad transportkarta över 64 städer i Nederländerna (64 städer, så 6 bitar skulle vara tillräckligt för att koda stadsnumret). Ett år senare stötte han på ett annat problem från maskinvaruingenjörer som använde nästa dator på institutet: Minimera mängden tråd som krävs för att ansluta stiften på maskinens bakpanel. Som en lösning återupptäckte han algoritmen som kallas Prims minimala spaning tree-algoritm och publicerade den år 1959.

Grunderna i Dijkstras algoritm

Följande är de grundläggande begreppen i Dijkstras algoritm:

Dijkstras algoritm börjar vid den nod vi väljer (källnoden), och den undersöker grafen för att hitta den kortaste vägen mellan den noden och alla andra noder i grafen.
Algoritmen håller register över det för närvarande erkända kortaste avståndet från varje nod till källnoden, och den uppdaterar dessa värden om den hittar någon kortare väg.
När algoritmen har hämtat den kortaste vägen mellan källan och en annan nod, markeras den noden som 'besökt' och inkluderas i sökvägen.
Proceduren fortsätter tills alla noder i grafen har inkluderats i sökvägen. På detta sätt har vi en väg som förbinder källnoden med alla andra noder, och följer den kortaste möjliga vägen för att nå varje nod.

Förstå hur Dijkstras algoritm fungerar

A Graf och källpunkt är krav för Dijkstras algoritm. Denna algoritm är etablerad på Greedy Approach och hittar därför det lokalt optimala valet (lokala minima i detta fall) vid varje steg i algoritmen.

Varje vertex i denna algoritm kommer att ha två egenskaper definierade för sig:

Besökt fastighet
Path Property

Låt oss förstå dessa egenskaper i korthet.

Besökt egendom:

Egenskapen 'besökt' anger om noden har besökts eller inte.
Vi använder den här egenskapen så att vi inte besöker någon nod igen.
En nod markeras som besökt först när den kortaste vägen har hittats.

Sökvägsegenskap:

Egenskapen 'path' lagrar värdet på den aktuella minimivägen till noden.
Den nuvarande minimivägen innebär den kortaste vägen vi har nått denna nod hittills.
Den här egenskapen revideras när någon granne till noden besöks.
Den här egenskapen är betydande eftersom den kommer att lagra det slutliga svaret för varje nod.

Inledningsvis markerar vi alla hörn, eller noder, obesökta eftersom de ännu inte har besökts. Sökvägen till alla noder är också inställd på oändlighet förutom källnoden. Dessutom sätts vägen till källnoden till noll (0).

Vi väljer sedan källnoden och markerar den som besökt. Efter det kommer vi åt alla närliggande noder till källnoden och utför avslappning på varje nod. Avslappning är processen att sänka kostnaden för att nå en nod med hjälp av en annan nod.

Under avslappningsprocessen revideras banan för varje nod till minimivärdet bland nodens nuvarande väg, summan av vägen till föregående nod och vägen från föregående nod till nuvarande nod.

Låt oss anta att p[n] är värdet på den aktuella vägen för nod n, p[m] är värdet på vägen upp till den tidigare besökta noden m, och w är vikten av kanten mellan den aktuella noden och tidigare besökt en (kantvikt mellan n och m).

I matematisk mening kan avslappning exemplifieras som:

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

Vi markerar sedan en obesökt nod med den minsta sökvägen som besökts i varje efterföljande steg och uppdaterar dess grannes vägar.

Vi upprepar denna procedur tills alla noder i grafen är markerade som besökta.

När vi lägger till en nod till den besökta uppsättningen ändras också sökvägen till alla dess närliggande noder.

primtalsprogram i java

Om någon nod inte kan nås (bortkopplad komponent), förblir dess väg 'oändlig'. Om själva källan är en separat komponent, förblir vägen till alla andra noder 'oändlig'.

Förstå Dijkstras algoritm med ett exempel

Följande är steget som vi kommer att följa för att implementera Dijkstras algoritm:

Steg 1: Först kommer vi att markera källnoden med ett aktuellt avstånd på 0 och ställa in resten av noderna till INFINITY.

Steg 2: Vi kommer sedan att ställa in den obesökta noden med det minsta strömavståndet som den aktuella noden, anta X.

Steg 3: För varje granne N till den nuvarande noden X: Vi kommer sedan att lägga till det aktuella avståndet för X med vikten av kanten som förenar X-N. Om det är mindre än det aktuella avståndet för N, ställ in det som det nya aktuella avståndet för N.

Steg 4: Vi kommer då att markera den aktuella noden X som besökt.

Steg 5: Vi kommer att upprepa processen från 'Steg 2' om det finns någon nod obesökt kvar i grafen.

Låt oss nu förstå implementeringen av algoritmen med hjälp av ett exempel:

Figur 6: Den givna grafen

Vi kommer att använda ovanstående graf som indata, med nod A som källa.
Först kommer vi att markera alla noder som obesökta.
Vi kommer att ange vägen till 0 vid noden A och OÄNDLIGHET för alla andra noder.
Vi kommer nu att markera källnoden A som besökt och åtkomst till dess närliggande noder.
Notera: Vi har bara nått de närliggande noderna, inte besökt dem.
Vi kommer nu att uppdatera sökvägen till noden B förbi 4 med hjälp av avkoppling eftersom vägen till nod A är 0 och vägen från noden A till B är 4 , och den minimum((0 + 4), INFINITY) är 4 .
Vi kommer också att uppdatera sökvägen till noden C förbi 5 med hjälp av avkoppling eftersom vägen till nod A är 0 och vägen från noden A till C är 5 , och den minimum((0 + 5), INFINITY) är 5 . Båda grannarna till nod A är nu avslappnade; därför kan vi gå vidare.
Vi kommer nu att välja nästa obesökta nod med minsta sökväg och besöka den. Därför kommer vi att besöka noden B och koppla av på sina obesökta grannar. Efter att ha utfört avkoppling, vägen till nod C kommer att förbli 5 , medan sökvägen till noden OCH kommer att bli elva , och sökvägen till noden D kommer att bli 13 .
Vi kommer nu att besöka noden OCH och utför avslappning på dess närliggande noder B, D , och F . Eftersom endast nod F är obesökt blir det avslappnat. Alltså vägen till noden B kommer att förbli som det är, dvs. 4 , vägen till noden D kommer också att finnas kvar 13 , och sökvägen till noden F kommer att bli 14 (8 + 6) .
Nu ska vi besöka node D , och endast nod F kommer att vara avslappnad. Däremot vägen till nod F kommer att förbli oförändrad, dvs. 14 .
Eftersom endast nod F är kvar, kommer vi att besöka den men inte utföra någon avslappning eftersom alla dess närliggande noder redan är besökta.
När alla noder i graferna har besökts avslutas programmet.

Därför är de sista vägarna vi kom fram till:

 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)

Pseudokod för Dijkstras algoritm

Vi kommer nu att förstå en pseudokod för Dijkstras algoritm.

Vi måste hålla ett register över vägavståndet för varje nod. Därför kan vi lagra vägavståndet för varje nod i en matris med storleken n, där n är det totala antalet noder.
Dessutom vill vi hämta den kortaste vägen tillsammans med längden på den vägen. För att övervinna detta problem kommer vi att mappa varje nod till den nod som senast uppdaterade sin väglängd.
När algoritmen är klar kan vi spåra destinationsnoden till källnoden för att hämta sökvägen.
Vi kan använda en minsta Prioritetskö för att hämta noden med minsta vägavstånd på ett effektivt sätt.

Låt oss nu implementera en pseudokod av illustrationen ovan:

Pseudokod:

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

Förklaring:

I kodavsnittet ovan har vi inkluderat stdio.h header-filen definierade två konstanta värden: INF = 9999 och MAX = 10 . Vi har deklarerat prototyperna för funktionen och sedan definierat funktionen för Dijkstras algoritm som Dijkstra Algoritm som accepterar tre argument - grafen som består av noderna, antalet noder i grafen och källnoden. Inuti den här funktionen har vi definierat några datastrukturer såsom en 2D-matris som kommer att fungera som Priority Queue för algoritmen, en array för att styra avståndet mellan noderna, en array för att upprätthålla registreringen av tidigare noder, en array att lagra information om besökta noder och några heltalsvariabler för att lagra minimiavståndsvärde, räknare, nästa nodvärde och mer. Vi använde sedan en kapslad för-loop att iterera genom grafens noder och lägga till dem i prioritetskön i enlighet med detta. Vi har återigen använt för-loop att iterera genom elementen i prioritetskön med början från källnoden och uppdatera deras avstånd. Utanför slingan har vi ställt in avståndet för källnoden som 0 och markerade det som besökt i besökta_noder[] array. Vi ställde sedan in räknarvärdet som ett och använde medan loop itererande genom antalet noder. Inuti denna loop har vi satt värdet på minimum_distans som INF och använde för-loop för att uppdatera värdet på minimum_distans variabel med minimivärdet från a distans[] array. Vi itererade sedan genom de obesökta närliggande noderna för den valda noden med hjälp av för-loop och utförde avslappning. Vi skrev sedan ut de resulterande data för avstånden beräknade med Dijkstras algoritm.

I den huvud funktion har vi definierat och deklarerat variablerna som representerar grafen, antalet noder och källnoden. Äntligen har vi ringt till DijkstraAlgorithm() funktion genom att skicka de nödvändiga parametrarna.

Som ett resultat skrivs de kortaste möjliga vägarna för varje nod från källnoden ut för användarna.

Kod för Dijkstras algoritm i C++

Följande är implementeringen av Dijkstras algoritm i programmeringsspråket C++:

Fil: DijkstraAlgorithm.cpp

linux som

 // 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;>

Förklaring:

I kodavsnittet ovan inkluderade vi 'iostream' och 'vektor' header-filer och definierade ett konstant värde som MAX_INT = 10000000 . Vi använde sedan standardnamnrymden och prototypade DijkstraAlgorithm() fungera. Vi definierade sedan huvudfunktionen för programmet inom, som vi har kallat DijkstraAlgorithm() fungera. Efter det deklarerade vi några klasser för att skapa hörn och kanter. Vi har också tagit fram fler funktioner för att hitta den kortaste möjliga vägen från källpunkten till destinationspunkten och instansierat klasserna Vertex och Edge. Vi definierade sedan båda klasserna för att skapa grafens hörn och kanter. Vi har då definierat DijkstraAlgorithm() funktion för att skapa en graf och utföra olika operationer. Inuti den här funktionen har vi deklarerat några hörn och kanter. Vi ställde sedan in källpunkten för grafen och kallade Dijkstra() funktion för att hitta kortast möjliga avstånd och Print_Shortest_Route_To() funktion för att skriva ut det kortaste avståndet från källpunkt till vertex 'F' . Vi har då definierat Dijkstra() funktion för att beräkna kortast möjliga avstånd för alla hörn från källpunkten. Vi har också definierat några fler funktioner för att hitta det hörn som har det kortaste avståndet för att returnera alla hörn som gränsar till den återstående vertexen, för att returnera avståndet mellan två sammankopplade hörn, för att kontrollera om den valda vertexen finns i grafen, och för att skriva ut kortast möjliga väg från källpunkten till destinationspunkten.

Som ett resultat, den erforderliga kortaste vägen för vertex 'F' från källnoden skrivs ut för användarna.

Kod för Dijkstras algoritm i Java

Följande är implementeringen av Dijkstras algoritm 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;>

Förklaring:

I ovanstående kodavsnitt har vi definierat en publik klass som DijkstraAlgorithm() . Inuti den här klassen har vi definierat en offentlig metod som dijkstraAlgorithm() för att hitta det kortaste avståndet från källpunkten till målpunkten. Inuti denna metod har vi definierat en variabel för att lagra antalet noder. Vi har sedan definierat en boolesk matris för att lagra informationen om de besökta hörnen och en heltalsmatris för att lagra deras respektive avstånd. Inledningsvis deklarerade vi värdena i båda arrayerna som Falsk och MAX_VALUE , respektive. Vi har också ställt in avståndet för källpunkten till noll och använt för-loop för att uppdatera avståndet mellan källpunkten och destinationspunkten med det minsta avståndet. Vi har sedan uppdaterat avstånden för de angränsande hörnen av den valda vertexen genom att utföra relaxation och skrivit ut de kortaste avstånden för varje vertex. Vi har sedan definierat en metod för att hitta det minsta avståndet från källpunkten till destinationspunkten. Vi definierade sedan huvudfunktionen där vi deklarerade grafens hörn och instansierade DijkstraAlgorithm() klass. Slutligen har vi kallat dijkstraAlgorithm() metod för att hitta det kortaste avståndet mellan källpunkten och destinationspunkten.

Som ett resultat skrivs de kortaste möjliga vägarna för varje nod från källnoden ut för användarna.

alfabetet efter siffror

Kod för Dijkstras algoritm i Python

Följande är implementeringen av Dijkstras algoritm i programmeringsspråket Python:

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

Förklaring:

I kodavsnittet ovan har vi importerat sys modul och deklarerade listorna som består av värdena för noderna och kanterna. Vi har då definierat en funktion som toBeVisited() för att hitta vilken nod som kommer att besökas härnäst. Vi hittade sedan det totala antalet noder i grafen och ställde in initiala avstånd för varje nod. Vi har sedan beräknat minimiavståndet från källnoden till destinationsnoden, utfört relaxation på angränsande noder och uppdaterat avstånden i listan. Vi skrev sedan ut dessa avstånd från listan för användarna.

Som ett resultat skrivs de kortaste möjliga vägarna för varje nod från källnoden ut för användarna.

Tid och rums komplexitet hos Dijkstras algoritm

Tidskomplexiteten hos Dijkstras algoritm är O(E log V) , där E är antalet kanter och V är antalet hörn.
Rymdkomplexiteten för Dijkstras algoritm är O(V), där V är antalet hörn.

Fördelar och nackdelar med Dijkstras algoritm

Låt oss diskutera några fördelar med Dijkstras algoritm:

En primär fördel med att använda Dijkstras algoritm är att den har en nästan linjär tids- och rymdkomplexitet.
Vi kan använda den här algoritmen för att beräkna den kortaste vägen från en enda vertex till alla andra hörn och en enda källpunkt till en enda destinationspunkt genom att stoppa algoritmen när vi får det kortaste avståndet för destinationspunkten.
Denna algoritm fungerar bara för riktade viktade grafer, och alla kanter på denna graf bör vara icke-negativa.

Trots flera fördelar har Dijkstras algoritm också några nackdelar, som:

Dijkstras algoritm utför en dold utforskning som tar mycket tid i anspråk under processen.
Denna algoritm är impotent för att hantera negativa kanter.
Eftersom denna algoritm går till den acykliska grafen kan den inte beräkna den exakta kortaste vägen.
Det kräver också underhåll för att hålla ett register över hörn som har besökts.

Några tillämpningar av Dijkstras algoritm

Dijkstras algoritm har olika verkliga applikationer, av vilka några anges nedan:

Digitala karttjänster i Google Maps:Det finns olika tillfällen då vi har försökt hitta avståndet i Google Maps, antingen från vår plats till närmaste föredragna plats eller från en stad till en annan, som omfattar flera rutter/vägar som förbinder dem; dock måste applikationen visa minsta avstånd. Detta är endast möjligt eftersom Dijkstras algoritm hjälper applikationen att hitta den kortaste mellan två givna platser längs vägen. Låt oss betrakta USA som en graf där städerna/platserna representeras som hörn och rutterna mellan två städer/platser representeras som kanter. Sedan kan vi med hjälp av Dijkstras algoritm beräkna de kortaste vägarna mellan två valfria städer/platser.Applikationer för sociala nätverk:I många applikationer som Facebook, Twitter, Instagram och fler kanske många av oss har observerat att dessa appar föreslår en lista över vänner som en specifik användare kanske känner till. Hur implementerar många sociala medieföretag den här typen av funktioner på ett effektivt och effektivt sätt, specifikt när systemet har över en miljard användare? Svaret på denna fråga är Dijkstras algoritm. Standarden Dijkstras algoritm används vanligtvis för att uppskatta det kortaste avståndet mellan användarna mätt genom anslutningarna eller ömsesidigheten mellan dem. När sociala nätverk är mycket små, använder det standard Dijkstras algoritm utöver några andra funktioner för att bestämma de kortaste vägarna. Men när grafen är mycket större tar standardalgoritmen flera sekunder att räkna, och därför används vissa avancerade algoritmer som alternativ.Telefonnät:Som vissa av oss kanske vet, i ett telefonnätverk har varje transmissionslinje en bandbredd, 'b'. Bandbredden är den högsta frekvens som transmissionsledningen kan stödja. I allmänhet, om signalens frekvens är högre i en specifik linje, reduceras signalen med den linjen. Bandbredd representerar mängden information som kan överföras av linjen. Låt oss betrakta en stad som en graf där kopplingsstationerna representeras med hjälp av hörnen, transmissionslinjerna representeras som kanterna och bandbredden, 'b', representeras med hjälp av kanternas vikt. Således, som vi kan observera, kan telefonnätet också hamna i kategorin kortaste avståndsproblem och kan lösas med Dijkstras algoritm.Flygprogram:Antag att en person behöver programvara för att förbereda en agenda för flygningar för kunder. Agenten har tillgång till en databas med alla flyg och flygplatser. Utöver flightnummer, ursprungsflygplats och destination har flygen även avgångs- och ankomsttider. Så, för att bestämma den tidigaste ankomsttiden för den valda destinationen från den ursprungliga flygplatsen och given starttid, använder agenterna Dijkstras algoritm.IP-routing för att hitta den öppna kortaste vägen först:Open Shortest Path First (förkortat OSPF) är ett länktillståndsroutningsprotokoll som används för att hitta den bästa vägen mellan käll- och destinationsroutern med hjälp av sin egen Shortest Path First. Dijkstras algoritm används i stor utsträckning i de routningsprotokoll som krävs av routrarna för att uppdatera deras vidarebefordrantabell. Algoritmen ger den kortaste kostnadsvägen från källroutern till de andra routrarna som finns i nätverket.Robotisk väg:Nuförtiden har drönare och robotar kommit till, några manövrerade manuellt och andra automatiskt. Drönarna och robotarna som drivs automatiskt och används för att leverera paketen till en given plats eller som används för en viss uppgift är konfigurerade med Dijkstras algoritmmodul så att närhelst källan och destinationen är känd kommer drönaren och roboten att röra sig i den beställda riktningen genom att följa den kortaste vägen och hålla den tid det tar för att leverera paketen till ett minimum.Ange filservern:Dijkstras algoritm används också för att ange en filserver i ett lokalt nätverk (LAN). Antag att det behövs en oändlig tidsperiod för överföringen av filerna från en dator till en annan. Så för att minimera antalet 'hopp' från filservern till alla andra datorer i nätverket kommer vi att använda Dijkstras algoritm. Denna algoritm kommer att returnera den kortaste vägen mellan nätverken vilket resulterar i det minsta antalet hopp.

Slutsatsen

I handledningen ovan har vi för det första förstått de grundläggande koncepten för Graph tillsammans med dess typer och applikationer.
Vi lärde oss sedan om Dijkstras algoritm och dess historia.
Vi har också förstått den grundläggande funktionen av Dijkstras algoritm med hjälp av ett exempel.
Efter det studerade vi hur man skriver kod för Dijkstras algoritm med hjälp av Pseudokod.
Vi observerade dess implementering i programmeringsspråk som C, C++, Java och Python med korrekta utdata och förklaringar.
Vi har också förstått tid- och rumskomplexiteten hos Dijkstras algoritm.
Slutligen har vi diskuterat fördelarna och nackdelarna med Dijkstras algoritm och några av dess verkliga tillämpningar.