DIJKSTRAJEV ALGORITEM NAJKRAJŠE POTI S PRIMERI

Naslednja vadnica nas bo naučila o Dijkstrovem algoritmu najkrajše poti. Razumeli bomo delovanje Dijkstrinega algoritma s postopno grafično razlago.

Pokrivali bomo naslednje:

Kratek pregled temeljnih konceptov grafa
Razumeti uporabo Dijkstrajevega algoritma
Razumejte delovanje algoritma s primerom po korakih

Torej, začnimo.

Kratek uvod v grafe

Grafi so nelinearne podatkovne strukture, ki predstavljajo 'povezave' med elementi. Ti elementi so znani kot Oglišča , in črte ali loki, ki povezujejo kateri koli dve točki v grafu, so znani kot Robovi . Bolj formalno, graf obsega nabor vrhov (V) in niz robov (E) . Graf je označen z G(V, E) .

Komponente grafa

Oglišča:Točke so osnovne enote grafa, ki se uporabljajo za predstavitev objektov, oseb ali entitet v resničnem življenju. Včasih so vozlišča znana tudi kot vozlišča.Robovi:Robovi so narisani ali uporabljeni za povezavo dveh vozlišč grafa. Včasih so robovi znani tudi kot loki.

Naslednja slika prikazuje grafični prikaz grafa:

Slika 1: Grafična predstavitev grafa

java regex $

Na zgornji sliki so oglišča/vozlišča označena z barvnimi krogi, robovi pa s črtami, ki povezujejo vozlišča.

Uporaba grafov

Grafi se uporabljajo za reševanje številnih problemov v resničnem življenju. Za predstavitev omrežij se uporabljajo grafi. Ta omrežja lahko vključujejo telefonska ali vezna omrežja ali poti v mestu.

Grafe lahko na primer uporabimo za oblikovanje modela prometnega omrežja, kjer oglišča prikazujejo objekte, ki pošiljajo ali prejemajo izdelke, robovi pa predstavljajo ceste ali poti, ki jih povezujejo. Sledi slikovni prikaz istega:

Slika 2: Slikovni prikaz prometnega omrežja

Grafi se uporabljajo tudi v različnih platformah družbenih medijev, kot so LinkedIn, Facebook, Twitter itd. Na primer, platforme, kot je Facebook, uporabljajo Grafe za shranjevanje podatkov svojih uporabnikov, kjer je vsaka oseba označena z vrhom, vsaka od njih pa je struktura, ki vsebuje informacije, kot so ID osebe, ime, spol, naslov itd.

Vrste grafov

Grafe lahko razvrstimo v dve vrsti:

Neusmerjeni graf
Usmerjeni graf

Neusmerjeni graf: Graf z robovi, ki nimajo smeri, se imenuje neusmerjen graf. Robovi tega grafa pomenijo dvosmerno razmerje, v katerem je vsak rob mogoče prečkati v obe smeri. Naslednja slika prikazuje preprost neusmerjen graf s štirimi vozlišči in petimi robovi.

Slika 3: Preprost neusmerjen graf

Usmerjeni graf: Graf z robovi s smerjo se imenuje usmerjen graf. Robovi tega grafa pomenijo enosmerno razmerje, v katerem je vsak rob mogoče prečkati samo v eni smeri. Naslednja slika prikazuje preprost usmerjen graf s štirimi vozlišči in petimi robovi.

Slika 4: Preprost usmerjen graf

Absolutna dolžina, položaj ali orientacija robov v ilustraciji grafa značilno nima pomena. Z drugimi besedami, isti graf lahko vizualiziramo na različne načine s preurejanjem vozlišč ali popačenjem robov, če se osnovna struktura grafa ne spremeni.

Kaj so uteženi grafi?

Za graf velja, da je utežen, če je vsakemu robu dodeljena 'teža'. Teža roba lahko označuje razdaljo, čas ali karkoli, kar modelira 'povezavo' med parom vozlišč, ki jih povezuje.

Na primer, lahko opazimo modro številko poleg vsakega roba na naslednji sliki uteženega grafa. Ta številka se uporablja za označevanje teže ustreznega roba.

Slika 5: Primer uteženega grafa

Uvod v Dijkstrajev algoritem

Zdaj, ko poznamo nekaj osnovnih konceptov grafov, se poglobimo v razumevanje koncepta Dijkstrajevega algoritma.

Ste se kdaj vprašali, kako Google Zemljevidi najdejo najkrajšo in najhitrejšo pot med dvema krajema?

No, odgovor je Dijkstrajev algoritem . Dijkstrajev algoritem je algoritem Graph ki najde najkrajšo pot od izvorne točke do vseh drugih točk v grafu (enotna izvorna najkrajša pot). Je vrsta pohlepnega algoritma, ki deluje samo na uteženih grafih s pozitivnimi utežmi. Časovna kompleksnost Dijkstrovega algoritma je O(V²) s pomočjo predstavitve grafa s sosednjo matriko. Ta časovna zapletenost se lahko zmanjša na O((V + E) log V) s pomočjo predstavitve grafa s seznamom sosednosti, kjer IN je število vozlišč in IN je število robov v grafu.

Zgodovina Dijkstrajevega algoritma

Dijkstrajev algoritem je oblikoval in objavil dr. Edsger W. Dijkstra , nizozemski računalničar, programski inženir, programer, znanstveni esejist in sistemski znanstvenik.

Med intervjujem s Philipom L. Frano za komunikacije revije ACM leta 2001 je dr. Edsger W. Dijkstra razkril:

„Katera je na splošno najkrajša pot za potovanje iz Rotterdama v Groningen: od določenega mesta do določenega mesta?“ Gre za algoritem za najkrajšo pot, ki sem ga oblikoval v približno dvajsetih minutah. Nekega jutra sem nakupoval v Amsterdamu s svojo mlado zaročenko in utrujeni sva se usedli na teraso kavarne, da bi spili skodelico kave in samo sem razmišljal, ali bi to zmogel, nato pa sem oblikoval algoritem za najkrajšo pot . Kot sem rekel, je bil to dvajsetminutni izum. Pravzaprav je bil objavljen leta '59, tri leta pozneje. Publikacija je še vedno berljiva, pravzaprav je kar lepa. Eden od razlogov, zakaj je tako lep, je bil ta, da sem ga oblikoval brez svinčnika in papirja. Kasneje sem izvedel, da je ena od prednosti oblikovanja brez svinčnika in papirja ta, da si se skoraj prisiljen izogniti vsem zapletenostim, ki se jim je mogoče izogniti. Sčasoma je ta algoritem na moje veliko presenečenje postal eden od temeljev moje slave.«

Dijkstra je razmišljal o problemu najkrajše poti, ko je delal kot programer v matematičnem centru v Amsterdamu leta 1956, da bi ponazoril zmogljivosti novega računalnika, znanega kot ARMAC. Njegov cilj je bil izbrati problem in rešitev (ki jo ustvari računalnik), ki bi ju lahko razumeli ljudje brez računalniškega znanja. Razvil je algoritem najkrajše poti in ga pozneje izvedel za ARMAC za nejasno skrajšan prometni zemljevid 64 mest na Nizozemskem (64 mest, torej bi 6 bitov zadostovalo za kodiranje številke mesta). Leto pozneje je naletel na drugo težavo inženirjev strojne opreme, ki so upravljali naslednji računalnik inštituta: Zmanjšajte količino žice, ki je potrebna za povezavo nožic na zadnji plošči stroja. Kot rešitev je ponovno odkril algoritem, imenovan Primov minimalni spanning tree algoritem, in ga objavil leta 1959.

Osnove Dijkstrajevega algoritma

Sledijo osnovni koncepti Dijkstrajevega algoritma:

Dijkstrajev algoritem se začne pri vozlišču, ki ga izberemo (izvorno vozlišče), in pregleda graf, da bi našel najkrajšo pot med tem vozliščem in vsemi drugimi vozlišči v grafu.
Algoritem hrani zapise o trenutno potrjeni najkrajši razdalji od vsakega vozlišča do izvornega vozlišča in te vrednosti posodobi, če najde krajšo pot.
Ko algoritem pridobi najkrajšo pot med virom in drugim vozliščem, je to vozlišče označeno kot 'obiskano' in vključeno v pot.
Postopek se nadaljuje, dokler vsa vozlišča v grafu niso vključena v pot. Na ta način imamo pot, ki povezuje izvorno vozlišče z vsemi drugimi vozlišči, po najkrajši možni poti do vsakega vozlišča.

Razumevanje delovanja Dijkstrinega algoritma

A graf in izvorno vozlišče so zahteve za Dijkstrajev algoritem. Ta algoritem je vzpostavljen na pohlepnem pristopu in tako najde lokalno optimalno izbiro (v tem primeru lokalne minimume) na vsakem koraku algoritma.

Vsako vozlišče v tem algoritmu bo imelo zanj definirani dve lastnosti:

Obiskana nepremičnina
Lastnost poti

Naj na kratko razumemo te lastnosti.

Obiskana nepremičnina:

Lastnost 'visited' označuje, ali je bilo vozlišče obiskano ali ne.
To lastnost uporabljamo, da ne obiščemo nobenega vozlišča.
Vozlišče je označeno kot obiskano šele, ko je bila najdena najkrajša pot.

Lastnost poti:

Lastnost 'path' shrani vrednost trenutne minimalne poti do vozlišča.
Trenutna najmanjša pot pomeni najkrajšo pot, ki smo jo do zdaj dosegli do tega vozlišča.
Ta lastnost se spremeni, ko je obiskan kateri koli sosed vozlišča.
Ta lastnost je pomembna, ker bo shranila končni odgovor za vsako vozlišče.

Na začetku označimo vsa vozlišča ali vozlišča kot neobiskana, saj jih je treba še obiskati. Pot do vseh vozlišč je prav tako nastavljena na neskončnost, razen izvornega vozlišča. Poleg tega je pot do izvornega vozlišča nastavljena na nič (0).

Nato izberemo izvorno vozlišče in ga označimo kot obiskano. Nato dostopamo do vseh sosednjih vozlišč izvornega vozlišča in na vsakem vozlišču izvedemo sprostitev. Sprostitev je proces znižanja stroškov doseganja vozlišča s pomočjo drugega vozlišča.

V procesu sproščanja se pot vsakega vozlišča revidira na najmanjšo vrednost med trenutno potjo vozlišča, vsoto poti do prejšnjega vozlišča in potjo od prejšnjega vozlišča do trenutnega vozlišča.

Predpostavimo, da je p[n] vrednost trenutne poti za vozlišče n, p[m] vrednost poti do predhodno obiskanega vozlišča m in w teža roba med trenutnim vozliščem in predhodno obiskan (teža roba med n in m).

V matematičnem smislu lahko sprostitev ponazorimo kot:

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

Nato neobiskano vozlišče z najmanjšo potjo označimo kot obiskano v vsakem naslednjem koraku in posodobimo njegove sosednje poti.

Ta postopek ponavljamo, dokler niso vsa vozlišča v grafu označena kot obiskana.

Kadarkoli obiskanemu nizu dodamo vozlišče, se ustrezno spremeni tudi pot do vseh njegovih sosednjih vozlišč.

Če katero koli vozlišče ostane nedosegljivo (odklopljena komponenta), njegova pot ostane 'neskončno'. V primeru, da je vir sam ločena komponenta, potem pot do vseh drugih vozlišč ostane 'neskončna'.

Razumevanje Dijkstrinega algoritma s primerom

Sledi korak, ki mu bomo sledili za implementacijo Dijkstrinega algoritma:

Korak 1: Najprej bomo izvorno vozlišče označili s trenutno razdaljo 0 in preostala vozlišča nastavili na NESKONČNOST.

2. korak: Nato bomo neobiskano vozlišče z najmanjšo trenutno razdaljo nastavili kot trenutno vozlišče, predpostavimo X.

3. korak: Za vsakega soseda N trenutnega vozlišča X: dodali bomo trenutno razdaljo X s težo roba, ki povezuje X-N. Če je manjša od trenutne razdalje N, jo nastavite kot novo trenutno razdaljo N.

4. korak: Nato bomo trenutno vozlišče X označili kot obiskano.

5. korak: Postopek bomo ponovili od '2. korak' če je na grafu še kakšno neobiskano vozlišče.

Razumejmo zdaj izvedbo algoritma s pomočjo primera:

Slika 6: Dani graf

Kot vhod bomo uporabili zgornji graf z vozliščem A kot vir.
Najprej bomo vsa vozlišča označili kot neobiskana.
Postavili bomo pot do 0 na vozlišču A in NESKONČNOST za vsa ostala vozlišča.
Zdaj bomo označili izvorno vozlišče A kot obiskano in dostop do sosednjih vozlišč.
Opomba: Do sosednjih vozlišč smo samo dostopali, ne pa jih obiskali.
Zdaj bomo posodobili pot do vozlišča B avtor 4 s pomočjo sprostitve, ker pot do vozlišča A je 0 in pot od vozlišča A do B je 4 , in minimalno ((0 + 4), NESKONČNO) je 4 .
Posodobili bomo tudi pot do vozlišča C avtor 5 s pomočjo sprostitve, ker pot do vozlišča A je 0 in pot od vozlišča A do C je 5 , in minimalno ((0 + 5), NESKONČNO) je 5 . Oba soseda vozlišča A so zdaj sproščeni; torej lahko gremo naprej.
Zdaj bomo izbrali naslednje neobiskano vozlišče z najmanjšo potjo in ga obiskali. Zato bomo obiskali vozlišče B in izvaja sprostitev na svojih neobiskanih sosedih. Po izvedbi sprostitve pot do vozlišča C bo ostal 5 , medtem ko pot do vozlišča IN bo enajst in pot do vozlišča D bo 13 .
Zdaj bomo obiskali vozlišče IN in izvaja sprostitev na sosednjih vozliščih B, D , in F . Ker samo vozlišče F je neobiskan, bo sproščen. Torej pot do vozlišča B bo ostalo tako, kot je, tj. 4 , pot do vozlišča D bo tudi ostalo 13 in pot do vozlišča F bo 14 (8 + 6) .
Zdaj bomo obiskali vozlišče D , in samo vozlišče F bo sproščeno. Vendar pot do vozlišča F bo ostala nespremenjena, tj. 14 .
Ker samo vozlišče F ostane, ga bomo obiskali, vendar ne bomo izvedli sprostitve, saj so vsa njegova sosednja vozlišča že obiskana.
Ko so obiskana vsa vozlišča grafov, se program zaključi.

Zato so končne poti, ki smo jih ugotovili, naslednje:

 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)

Psevdokoda za Dijkstrajev algoritem

Zdaj bomo razumeli psevdokodo za Dijkstrajev algoritem.

Voditi moramo evidenco razdalje poti vsakega vozlišča. Zato lahko razdaljo poti vsakega vozlišča shranimo v polje velikosti n, kjer je n skupno število vozlišč.
Poleg tega želimo pridobiti najkrajšo pot skupaj z dolžino te poti. Da bi odpravili to težavo, bomo vsako vozlišče preslikali v vozlišče, ki je nazadnje posodobilo svojo dolžino poti.
Ko je algoritem končan, lahko vrnemo ciljno vozlišče do izvornega vozlišča, da pridobimo pot.
Uporabimo lahko minimalno prednostno čakalno vrsto, da na učinkovit način pridobimo vozlišče z najmanjšo razdaljo poti.

Implementirajmo zdaj psevdokodo zgornje ilustracije:

Psevdokoda:

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

Pojasnilo:

V zgornji delček kode smo vključili stdio.h glava datoteke definira dve stalni vrednosti: INF = 9999 in NAJVEČ = 10 . Razglasili smo prototip funkcije in nato definirali funkcijo za Dijkstrajev algoritem kot DijkstraAlgoritem ki sprejme tri argumente - graf, sestavljen iz vozlišč, število vozlišč v grafu in izvorno vozlišče. Znotraj te funkcije smo definirali nekaj podatkovnih struktur, kot je 2D matrika, ki bo delovala kot prednostna čakalna vrsta za algoritem, polje za ohranjanje razdalje med vozlišči, polje za vzdrževanje zapisa prejšnjih vozlišč, polje za shranjevanje informacije o obiskanih vozliščih in nekaj celoštevilskih spremenljivk za shranjevanje vrednosti najmanjše razdalje, števca, vrednosti naslednjega vozlišča in več. Nato smo uporabili a ugnezdena for-zanka za ponavljanje skozi vozlišča grafa in njihovo ustrezno dodajanje v prednostno čakalno vrsto. Ponovno smo uporabili for-zanka za ponavljanje elementov v prednostni čakalni vrsti, začenši od izvornega vozlišča, in posodobitev njihovih razdalj. Zunaj zanke smo razdaljo izvornega vozlišča nastavili kot 0 in ga označil kot obiskanega v visited_nodes[] niz. Nato smo vrednost števca nastavili kot ena in uporabili medtem zanka, ki ponavlja število vozlišč. Znotraj te zanke smo nastavili vrednost minimalna_razdalja kot INF in uporabil for-zanka za posodobitev vrednosti minimalna_razdalja spremenljivka z najmanjšo vrednostjo od a razdalja[] niz. Nato smo ponovili skozi neobiskana sosednja vozlišča izbranega vozlišča z uporabo for-zanka in izvajali sprostitev. Nato smo natisnili dobljene podatke o razdaljah, izračunanih z uporabo Dijkstrovega algoritma.

V glavni smo definirali in deklarirali spremenljivke, ki predstavljajo graf, število vozlišč in izvorno vozlišče. Končno smo poklicali DijkstraAlgoritem() funkcijo s posredovanjem zahtevanih parametrov.

Posledično se za uporabnike natisnejo zahtevane najkrajše možne poti za vsako vozlišče iz izvornega vozlišča.

Koda za Dijkstrajev algoritem v C++

Sledi implementacija Dijkstrinega algoritma v programskem jeziku C++:

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

Pojasnilo:

V zgornji delček kode smo vključili 'iostream' in 'vektor' datoteke glave in definira konstantno vrednost kot MAX_INT = 10000000 . Nato smo uporabili standardni imenski prostor in izdelali prototip DijkstraAlgoritem() funkcijo. Nato smo znotraj programa definirali glavno funkcijo, ki smo jo poimenovali DijkstraAlgoritem() funkcijo. Po tem smo razglasili nekaj razredov za ustvarjanje oglišč in robov. Izdelali smo tudi prototip več funkcij za iskanje najkrajše možne poti od izvorne točke do ciljne točke in instancirali razreda Vertex in Edge. Nato smo definirali oba razreda, da ustvarimo oglišča in robove grafa. Nato smo definirali DijkstraAlgoritem() funkcijo za ustvarjanje grafa in izvajanje različnih operacij. Znotraj te funkcije smo deklarirali nekaj oglišč in robov. Nato smo nastavili izvorno točko grafa in poklicali Dijkstra () funkcijo za iskanje najkrajše možne razdalje in Natisni_najkrajšo_pot_do() funkcijo za izpis najkrajše razdalje od izvorne točke do točke 'F' . Nato smo definirali Dijkstra () funkcijo za izračun najkrajših možnih razdalj vseh vozlišč od izvornega vrha. Definirali smo tudi nekaj več funkcij za iskanje vozlišča z najkrajšo razdaljo za vrnitev vseh točk, ki mejijo na preostalo točko, za vrnitev razdalje med dvema povezanima točkoma, za preverjanje, ali izbrana oglišča obstaja v grafu, in za tiskanje najkrajša možna pot od izvorne točke do ciljne točke.

Kot rezultat, zahtevana najkrajša pot za točko 'F' iz izvornega vozlišča se natisne za uporabnike.

Koda za Dijkstrajev algoritem v Javi

Sledi implementacija Dijkstrinega algoritma v programskem jeziku Java:

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

Pojasnilo:

V zgornjem delčku kode smo definirali javni razred kot DijkstraAlgoritem() . Znotraj tega razreda smo definirali javno metodo kot dijkstraAlgoritem() da najdemo najkrajšo razdaljo od izvorne točke do ciljne točke. Znotraj te metode smo definirali spremenljivko za shranjevanje števila vozlišč. Nato smo definirali logično matriko za shranjevanje informacij o obiskanih točkah in matriko celih števil za shranjevanje njihovih razdalj. Na začetku smo vrednosti v obeh nizih razglasili kot False in MAX_VALUE , oz. Nastavili smo tudi razdaljo izvorne točke na nič in uporabili for-zanka za posodobitev razdalje med izvorno točko in ciljno točko z najmanjšo razdaljo. Nato smo z relaksacijo posodobili razdalje sosednjih oglišč izbranega oglišča in izpisali najkrajše razdalje za vsako oglišče. Nato smo definirali metodo za iskanje najmanjše razdalje od izvorne točke do ciljne točke. Nato smo definirali glavno funkcijo, kjer smo deklarirali vozlišča grafa in instancirali DijkstraAlgoritem() razred. Končno smo poklicali dijkstraAlgoritem() metoda za iskanje najkrajše razdalje med izvorno točko in ciljno točko.

Posledično se za uporabnike natisnejo zahtevane najkrajše možne poti za vsako vozlišče iz izvornega vozlišča.

Koda za Dijkstrajev algoritem v Pythonu

Sledi implementacija Dijkstrinega algoritma v programskem jeziku Python:

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

Izhod

 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

Pojasnilo:

V zgornjem delčku kode smo uvozili sys modul in deklariral sezname, sestavljene iz vrednosti za vozlišča in robove. Nato smo definirali funkcijo kot toBeVisited() da ugotovite, katero vozlišče bo naslednje obiskano. Nato smo našli skupno število vozlišč v grafu in določili začetne razdalje za vsako vozlišče. Nato smo izračunali najmanjšo razdaljo od izvornega vozlišča do ciljnega vozlišča, izvedli sprostitev na sosednjih vozliščih in posodobili razdalje na seznamu. Te razdalje smo nato natisnili s seznama za uporabnike.

Posledično se za uporabnike natisnejo zahtevane najkrajše možne poti za vsako vozlišče iz izvornega vozlišča.

Časovna in prostorska kompleksnost Dijkstrovega algoritma

Časovna kompleksnost Dijkstrovega algoritma je O(E log V) , kjer je E število robov in V število oglišč.
Prostorska kompleksnost Dijkstrovega algoritma je O(V), kjer je V število oglišč.

Prednosti in slabosti Dijkstrovega algoritma

Razpravljajmo o nekaterih prednostih Dijkstrinega algoritma:

Glavna prednost uporabe Dijkstrinega algoritma je, da ima skoraj linearno časovno in prostorsko kompleksnost.
Ta algoritem lahko uporabimo za izračun najkrajše poti od ene točke do vseh drugih točk in ene same izvorne točke do ene ciljne točke tako, da zaustavimo algoritem, ko dobimo najkrajšo razdaljo za ciljno točko.
Ta algoritem deluje samo za usmerjene utežene grafe in vsi robovi tega grafa morajo biti nenegativni.

Kljub številnim prednostim ima Dijkstrav algoritem tudi nekaj slabosti, kot so:

Dijkstrajev algoritem izvaja prikrito raziskovanje, ki med postopkom porabi veliko časa.
Ta algoritem je nemočen za obvladovanje negativnih robov.
Ker ta algoritem vodi do acikličnega grafa, ne more izračunati točne najkrajše poti.
Prav tako zahteva vzdrževanje za vodenje evidence o obiskanih točkah.

Nekaj aplikacij Dijkstrajevega algoritma

Dijkstrajev algoritem ima različne aplikacije v resničnem svetu, nekatere izmed njih so navedene spodaj:

Storitve digitalnega kartiranja v Google Zemljevidih:Včasih smo poskušali najti razdaljo v Google Zemljevidih od naše lokacije do najbližje želene lokacije ali od enega mesta do drugega, kar obsega več poti/poti, ki ju povezujejo; vendar mora aplikacija prikazati minimalno razdaljo. To je mogoče samo zato, ker Dijkstrajev algoritem pomaga aplikaciji najti najkrajšo med dvema podanima lokacijama na poti. Vzemimo ZDA kot graf, kjer so mesta/kraji predstavljeni kot vozlišča, poti med dvema mestoma/krajoma pa kot robovi. Nato lahko s pomočjo Dijkstrajevega algoritma izračunamo najkrajše poti med poljubnima mestoma/krajoma.Aplikacije za družabna omrežja:V mnogih aplikacijah, kot so Facebook, Twitter, Instagram in druge, smo mnogi od nas morda opazili, da te aplikacije predlagajo seznam prijateljev, ki jih določen uporabnik morda pozna. Kako mnoga podjetja za družbene medije izvajajo to vrsto funkcije na učinkovit in uspešen način, zlasti ko ima sistem več kot milijardo uporabnikov? Odgovor na to vprašanje je Dijkstrajev algoritem. Standardni Dijkstrajev algoritem se na splošno uporablja za oceno najkrajše razdalje med uporabniki, izmerjene prek povezav ali vzajemnosti med njimi. Ko je družabno omrežje zelo majhno, uporablja standardni Dijkstrajev algoritem poleg nekaterih drugih funkcij, da določi najkrajše poti. Ko pa je graf veliko večji, standardni algoritem šteje nekaj sekund, zato se kot alternativa uporabijo nekateri napredni algoritmi.Telefonsko omrežje:Kot nekateri morda vemo, ima v telefonskem omrežju vsak prenosni vod pasovno širino, 'b'. Pasovna širina je najvišja frekvenca, ki jo prenosni vod lahko podpira. Na splošno velja, da če je frekvenca signala višja v določeni liniji, se signal zmanjša za to linijo. Pasovna širina predstavlja količino informacij, ki jih lahko prenese linija. Vzemimo mesto kot graf, v katerem so preklopne postaje predstavljene z oglišči, prenosni vodi so predstavljeni kot robovi, pasovna širina, 'b', pa je predstavljena z uporabo teže robov. Kot lahko opazimo, lahko torej tudi telefonsko omrežje sodi v kategorijo problema najkrajše razdalje in ga je mogoče rešiti z Dijkstrovim algoritmom.Program letenja:Recimo, da oseba potrebuje programsko opremo za pripravo dnevnega reda letov za stranke. Agent ima dostop do podatkovne baze z vsemi leti in letališči. Poleg številke leta, izvornega letališča in cilja imajo leti tudi čas odhoda in prihoda. Za določitev najzgodnejšega časa prihoda za izbrano destinacijo s prvotnega letališča in danega začetnega časa agenti uporabijo Dijkstrajev algoritem.Usmerjanje IP za iskanje odprte najkrajše poti:Najprej odpri najkrajšo pot (skrajšano OSPF) je usmerjevalni protokol stanja povezave, ki se uporablja za iskanje najboljše poti med izvornim in ciljnim usmerjevalnikom s pomočjo lastnega protokola Najprej najkrajša pot. Dijkstrajev algoritem se v veliki meri uporablja v usmerjevalnih protokolih, ki jih zahtevajo usmerjevalniki za posodobitev svoje tabele za posredovanje. Algoritem poda najkrajšo stroškovno pot od izvornega usmerjevalnika do drugih usmerjevalnikov, prisotnih v omrežju.Robotska pot:Dandanes so se pojavili droni in roboti, nekateri se upravljajo ročno, drugi pa avtomatsko. Droni in roboti, ki se upravljajo samodejno in se uporabljajo za dostavo paketov na določeno lokacijo ali se uporabljajo za katero koli določeno nalogo, so konfigurirani z modulom Dijkstra's Algorithm, tako da se dron in robot premikata v naročeno smer, kadar koli sta znana vir in cilj. tako, da sledite najkrajši poti in pri tem čim bolj porabite čas za dostavo paketov.Določite datotečni strežnik:Dijkstrajev algoritem se uporablja tudi za določanje datotečnega strežnika v lokalnem omrežju (LAN). Recimo, da je za prenos datotek iz enega računalnika v drugega potrebno neskončno časovno obdobje. Torej, da bi zmanjšali število 'skokov' od datotečnega strežnika do vseh drugih računalnikov v omrežju, bomo uporabili Dijkstrajev algoritem. Ta algoritem bo vrnil najkrajšo pot med omrežji, kar bo povzročilo najmanjše število skokov.

Sklep

V zgornji vadnici smo najprej razumeli osnovne koncepte Grapha skupaj z njegovimi vrstami in aplikacijami.
Nato smo spoznali Dijkstrajev algoritem in njegovo zgodovino.
S pomočjo primera smo razumeli tudi temeljno delovanje Dijkstrajevega algoritma.
Nato smo se učili, kako s pomočjo psevdokoda napisati kodo za Dijkstrajev algoritem.
Opazovali smo njegovo implementacijo v programskih jezikih, kot so C, C++, Java in Python, z ustreznimi rezultati in razlagami.
Razumeli smo tudi časovno in prostorsko kompleksnost Dijkstrovega algoritma.
Nazadnje smo razpravljali o prednostih in slabostih Dijkstrinega algoritma in nekaterih njegovih resničnih aplikacijah.

Dijkstrajev algoritem

Kratek uvod v grafe

Komponente grafa

Uporaba grafov

Vrste grafov

Kaj so uteženi grafi?

Uvod v Dijkstrajev algoritem

Zgodovina Dijkstrajevega algoritma

Osnove Dijkstrajevega algoritma

Razumevanje delovanja Dijkstrinega algoritma

Obiskana nepremičnina:

Lastnost poti:

Razumevanje Dijkstrinega algoritma s primerom

Psevdokoda za Dijkstrajev algoritem

Koda za Dijkstrajev algoritem v C++

Koda za Dijkstrajev algoritem v Javi

Koda za Dijkstrajev algoritem v Pythonu

Časovna in prostorska kompleksnost Dijkstrovega algoritma

Prednosti in slabosti Dijkstrovega algoritma

Nekaj ​​aplikacij Dijkstrajevega algoritma

Sklep

Nekaj aplikacij Dijkstrajevega algoritma