Nasledujúci tutoriál nás naučí o Dijkstrovom algoritme najkratšej cesty. Fungovanie Dijkstrovho algoritmu pochopíme postupným grafickým vysvetlením.

Budeme pokrývať nasledovné:

pomocný policajný komisár

• Stručný prehľad základných pojmov grafu
• Pochopte použitie Dijkstrovho algoritmu
• Pochopte fungovanie algoritmu pomocou príkladu krok za krokom

Takže, začnime.

Stručný úvod do grafov

Grafy sú nelineárne dátové štruktúry predstavujúce „spojenia“ medzi prvkami. Tieto prvky sú známe ako Vertices a čiary alebo oblúky, ktoré spájajú akékoľvek dva vrcholy v grafe, sú známe ako Hrany . Formálnejšie graf obsahuje množina vrcholov (V) a sada hrán (E) . Graf je označený G(V, E) .

Komponenty grafu

Vrcholy:Vrcholy sú základné jednotky grafu používané na znázornenie skutočných objektov, osôb alebo entít. Niekedy sú vrcholy známe aj ako uzly.Hrany:Hrany sú nakreslené alebo použité na spojenie dvoch vrcholov grafu. Hrany sú niekedy známe aj ako oblúky.

Nasledujúci obrázok znázorňuje grafické znázornenie grafu:

Postava 1: Grafické znázornenie grafu

Na obrázku vyššie sú vrcholy/uzly označené farebnými kruhmi a hrany sú označené čiarami spájajúcimi uzly.

Aplikácie grafov

Grafy sa používajú na riešenie mnohých problémov v reálnom živote. Na znázornenie sietí sa používajú grafy. Tieto siete môžu zahŕňať telefónne alebo okruhové siete alebo cesty v meste.

Napríklad by sme mohli použiť grafy na návrh modelu dopravnej siete, kde vrcholy zobrazujú zariadenia, ktoré odosielajú alebo prijímajú produkty, a okraje predstavujú cesty alebo cesty, ktoré ich spájajú. Nasleduje obrázkové znázornenie toho istého:

Obrázok 2: Obrazové znázornenie dopravnej siete

Grafy sa používajú aj na rôznych platformách sociálnych médií, ako sú LinkedIn, Facebook, Twitter a ďalšie. Napríklad platformy ako Facebook používajú grafy na ukladanie údajov svojich používateľov, kde je každá osoba označená vrcholom a každá z nich je štruktúrou obsahujúcou informácie ako ID osoby, meno, pohlavie, adresa atď.

Typy grafov

Grafy možno rozdeliť do dvoch typov:

1. Neorientovaný graf
2. Riadený graf

Neorientovaný graf: Graf s hranami, ktoré nemajú smer, sa nazýva neorientovaný graf. Hrany tohto grafu znamenajú obojsmerný vzťah, v ktorom možno každú hranu prechádzať v oboch smeroch. Nasledujúci obrázok zobrazuje jednoduchý neorientovaný graf so štyrmi uzlami a piatimi hranami.

Obrázok 3: Jednoduchý neorientovaný graf

Riadený graf: Graf s hranami so smerom sa nazýva orientovaný graf. Hrany tohto grafu znamenajú jednosmerný vzťah, v ktorom je možné každú hranu prejsť iba v jednom smere. Nasledujúci obrázok zobrazuje jednoduchý orientovaný graf so štyrmi uzlami a piatimi hranami.

Obrázok 4: Jednoduchý orientovaný graf

Absolútna dĺžka, poloha alebo orientácia hrán v ilustrácii grafu charakteristicky nemá význam. Inými slovami, ten istý graf môžeme vizualizovať rôznymi spôsobmi preskupením vrcholov alebo skreslením hrán, ak sa základná štruktúra grafu nezmení.

Čo sú vážené grafy?

O grafe sa hovorí, že je vážený, ak je každej hrane priradená „váha“. Hmotnosť hrany môže označovať vzdialenosť, čas alebo čokoľvek, čo modeluje „spojenie“ medzi dvojicou vrcholov, ktoré spája.

Napríklad na nasledujúcom obrázku váženého grafu môžeme vedľa každej hrany pozorovať modré číslo. Toto číslo sa používa na označenie hmotnosti zodpovedajúcej hrany.

Obrázok 5: Príklad váženého grafu

Úvod do Dijkstrovho algoritmu

Teraz, keď poznáme niektoré základné koncepty grafov, poďme sa ponoriť do pochopenia konceptu Dijkstrovho algoritmu.

Zaujímalo vás niekedy, ako Google Maps nájde najkratšiu a najrýchlejšiu trasu medzi dvoma miestami?

Nuž, odpoveď je Dijkstrov algoritmus . Dijkstrov algoritmus je grafový algoritmus ktorý nájde najkratšiu cestu zo zdrojového vrcholu do všetkých ostatných vrcholov v grafe (najkratšia cesta z jedného zdroja). Je to typ Greedy Algorithm, ktorý funguje iba na vážených grafoch s kladnými váhami. Časová zložitosť Dijkstrovho algoritmu je O(V²) pomocou maticového znázornenia grafu. Táto časová zložitosť sa dá zredukovať na O((V + E) log V) pomocou priľahlého zoznamu znázornenie grafu, kde V je počet vrcholov a A je počet hrán v grafe.

História Dijkstrovho algoritmu

Dijkstrov algoritmus navrhol a zverejnil DR. Edsger W. Dijkstra , holandský počítačový vedec, softvérový inžinier, programátor, vedecký esejista a systémový vedec.

Počas rozhovoru s Philipom L. Franom pre komunikáciu časopisu ACM v roku 2001 Dr. Edsger W. Dijkstra prezradil:

„Aká je vo všeobecnosti najkratšia cesta z Rotterdamu do Groningenu: z daného mesta do daného mesta? Je to algoritmus pre najkratšiu cestu, ktorý som navrhol za približne dvadsať minút. Jedného rána som bol so svojou mladou snúbenicou nakupovať v Amsterdame a unavení sme si sadli na terasu kaviarne, aby sme vypili šálku kávy a ja som len rozmýšľal, či by som to mohol urobiť, a potom som navrhol algoritmus pre najkratšiu cestu. . Ako som povedal, bol to dvadsaťminútový vynález. V skutočnosti to vyšlo v roku 59, o tri roky neskôr. Publikácia je stále čitateľná, v podstate je celkom pekná. Jedným z dôvodov, prečo je taký pekný, bolo, že som ho navrhol bez ceruzky a papiera. Neskôr som sa dozvedel, že jednou z výhod navrhovania bez ceruzky a papiera je, že ste takmer nútení vyhnúť sa všetkým komplikáciám, ktorým sa dá vyhnúť. Nakoniec sa tento algoritmus na moje veľké prekvapenie stal jedným zo základných kameňov mojej slávy.“

Dijkstra premýšľal o probléme s najkratšou cestou, keď pracoval ako programátor v Matematickom centre v Amsterdame v roku 1956, aby ilustroval možnosti nového počítača známeho ako ARMAC. Jeho cieľom bolo vybrať problém aj riešenie (vytvorené počítačom), ktoré by ľudia bez počítačového vzdelania dokázali pochopiť. Vyvinul algoritmus najkratšej cesty a neskôr ho vykonal pre ARMAC pre nejasne skrátenú dopravnú mapu 64 miest v Holandsku (64 miest, takže 6 bitov by stačilo na zakódovanie čísla mesta). O rok neskôr narazil na ďalší problém od hardvérových inžinierov prevádzkujúcich ďalší počítač inštitútu: Minimalizujte množstvo drôtu potrebného na pripojenie kolíkov na zadnom paneli stroja. Ako riešenie znovu objavil algoritmus s názvom Primov algoritmus minimálneho spanning tree a zverejnil ho v roku 1959.

Základy Dijkstrovho algoritmu

Nasledujú základné koncepty Dijkstrovho algoritmu:

1. Dijkstrov algoritmus začína v uzle, ktorý vyberieme (zdrojový uzol), a skúma graf, aby našiel najkratšiu cestu medzi týmto uzlom a všetkými ostatnými uzlami v grafe.
2. Algoritmus uchováva záznamy o aktuálne potvrdenej najkratšej vzdialenosti od každého uzla k zdrojovému uzlu a aktualizuje tieto hodnoty, ak nájde nejakú kratšiu cestu.
3. Keď algoritmus získa najkratšiu cestu medzi zdrojom a iným uzlom, tento uzol sa označí ako „navštívený“ a zahrnie sa do cesty.
4. Procedúra pokračuje, kým nie sú všetky uzly v grafe zahrnuté do cesty. Týmto spôsobom máme cestu spájajúcu zdrojový uzol so všetkými ostatnými uzlami po najkratšej možnej ceste na dosiahnutie každého uzla.

Pochopenie fungovania Dijkstrovho algoritmu

A graf a zdrojový vrchol sú požiadavky na Dijkstrov algoritmus. Tento algoritmus je založený na Greedy Approach a teda nájde lokálne optimálnu voľbu (v tomto prípade lokálne minimá) v každom kroku algoritmu.

Každý vrchol v tomto algoritme bude mať definované dve vlastnosti:

1. Navštívená nehnuteľnosť
2. Vlastnosť cesty

Poďme stručne pochopiť tieto vlastnosti.

Navštívená nehnuteľnosť:

1. Vlastnosť „navštívené“ označuje, či bol alebo nebol uzol navštívený.
2. Túto vlastnosť používame, aby sme znova nenavštívili žiadny uzol.
3. Uzol je označený ako navštívený iba vtedy, keď sa nájde najkratšia cesta.

Vlastnosť cesty:

1. Vlastnosť 'cesta' ukladá hodnotu aktuálnej minimálnej cesty k uzlu.
2. Aktuálna minimálna cesta znamená najkratšiu cestu, ktorou sme sa k tomuto uzlu doteraz dostali.
3. Táto vlastnosť sa reviduje pri návšteve ktoréhokoľvek suseda uzla.
4. Táto vlastnosť je dôležitá, pretože uloží konečnú odpoveď pre každý uzol.

Na začiatku označíme všetky vrcholy alebo uzly ako nenavštívené, pretože ich ešte treba navštíviť. Cesta ku všetkým uzlom je tiež nastavená na nekonečno okrem zdrojového uzla. Okrem toho je cesta k zdrojovému uzlu nastavená na nulu (0).

Následne vyberieme zdrojový uzol a označíme ho ako navštívený. Potom pristúpime ku všetkým susedným uzlom zdrojového uzla a vykonáme relaxáciu na každom uzle. Relaxácia je proces znižovania nákladov na dosiahnutie uzla pomocou iného uzla.

V procese relaxácie sa cesta každého uzla upraví na minimálnu hodnotu medzi aktuálnou cestou uzla, súčtom cesty k predchádzajúcemu uzlu a cestou z predchádzajúceho uzla do aktuálneho uzla.

Predpokladajme, že p[n] je hodnota aktuálnej cesty pre uzol n, p[m] je hodnota cesty po predtým navštívený uzol m a w je váha hrany medzi aktuálnym uzlom a predtým navštívená (váha hrany medzi n a m).

V matematickom zmysle môže byť relaxácia znázornená ako:

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

Potom označíme nenavštívený uzol s najnižšou cestou ako navštívený v každom nasledujúcom kroku a aktualizujeme cesty jeho suseda.

Tento postup opakujeme, kým nebudú všetky uzly v grafe označené ako navštívené.

Vždy, keď do navštívenej množiny pridáme uzol, zodpovedajúcim spôsobom sa zmení aj cesta ku všetkým jeho susedným uzlom.

Ak niektorý uzol zostane nedosiahnuteľný (odpojený komponent), jeho cesta zostane „nekonečná“. V prípade, že samotný zdroj je samostatný komponent, potom cesta ku všetkým ostatným uzlom zostáva „nekonečno“.

Pochopenie Dijkstrovho algoritmu na príklade

Nasleduje krok, ktorý budeme dodržiavať pri implementácii Dijkstrovho algoritmu:

Krok 1: Najprv označíme zdrojový uzol s aktuálnou vzdialenosťou 0 a zvyšok uzlov nastavíme na NEKONEČNO.

Krok 2: Potom nastavíme nenavštívený uzol s najmenšou aktuálnou vzdialenosťou ako aktuálny uzol, predpokladajme, že X.

programovacie vzory java

Krok 3: Pre každého suseda N aktuálneho uzla X: Potom pripočítame aktuálnu vzdialenosť X s hmotnosťou hrany spájajúcej X-N. Ak je menšia ako aktuálna vzdialenosť N, nastavte ju ako novú aktuálnu vzdialenosť N.

Krok 4: Potom označíme aktuálny uzol X ako navštívený.

Krok 5: Postup zopakujeme od 'Krok 2' ak v grafe zostane nejaký nenavštívený uzol.

Poďme teraz pochopiť implementáciu algoritmu pomocou príkladu:

Obrázok 6: Daný graf

1. Ako vstup použijeme vyššie uvedený graf s uzlom A ako zdroj.
2. Najprv označíme všetky uzly ako nenavštívené.
3. Cestu nastavíme na 0 v uzle A a NEKONEČNO pre všetky ostatné uzly.
4. Teraz označíme zdrojový uzol A ako navštívené a pristupovať k jeho susedným uzlom.
   Poznámka: Pristúpili sme len k susedným uzlom, nenavštívili sme ich.
5. Teraz aktualizujeme cestu k uzlu B podľa 4 s pomocou relaxácie, pretože cesta k uzlu A je 0 a cesta z uzla A do B je 4 , a minimum((0 + 4), NEKONEČNO) je 4 .
6. Aktualizujeme aj cestu k uzlu C podľa 5 s pomocou relaxácie, pretože cesta k uzlu A je 0 a cesta z uzla A do C je 5 , a minimum((0 + 5), NEKONEČNO) je 5 . Obaja susedia uzla A sú teraz uvoľnení; preto sa môžeme pohnúť vpred.
7. Teraz vyberieme ďalší nenavštívený uzol s najmenšou cestou a navštívime ho. Preto navštívime uzol B a vykonávať relax u svojich nenavštevovaných susedov. Po vykonaní relaxácie cesta k uzlu C zostane 5 , zatiaľ čo cesta k uzlu A bude jedenásť a cestu k uzlu D bude 13 .
8. Teraz navštívime uzol A a vykonávať relaxáciu na jeho susedných uzloch B, D , a F . Keďže jediný uzol F je nenavštevovaná, bude uvoľnená. Teda cesta k uzlu B zostane tak ako je, tj. 4 , cesta k uzlu D zostane tiež 13 a cestu k uzlu F bude 14 (8 + 6) .
9. Teraz navštívime uzol D , a iba uzol F bude uvoľnený. Avšak cesta k uzlu F zostane nezmenená, tj. 14 .
10. Keďže jediný uzol F zostáva, navštívime ho, ale nevykonáme žiadnu relaxáciu, pretože všetky jeho susedné uzly sú už navštívené.
11. Po navštívení všetkých uzlov grafov sa program ukončí.

Preto posledné cesty, ktoré sme uzavreli, sú:

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

Pseudokód pre Dijkstrov algoritmus

Teraz pochopíme pseudokód pre Dijkstrov algoritmus.

• Musíme udržiavať záznam o vzdialenosti cesty každého uzla. Preto môžeme uložiť dráhovú vzdialenosť každého uzla do poľa veľkosti n, kde n je celkový počet uzlov.
• Okrem toho chceme získať najkratšiu cestu spolu s dĺžkou tejto cesty. Na prekonanie tohto problému namapujeme každý uzol na uzol, ktorý naposledy aktualizoval svoju dĺžku cesty.
• Po dokončení algoritmu môžeme spätne sledovať cieľový uzol do zdrojového uzla, aby sme získali cestu.
• Môžeme použiť minimálnu prioritnú frontu na získanie uzla s najmenšou vzdialenosťou cesty efektívnym spôsobom.

Teraz implementujme pseudokód vyššie uvedenej ilustrácie:

Pseudokód:

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

Vysvetlenie:

Vo vyššie uvedenom úryvku kódu sme zahrnuli stdio.h hlavičkový súbor definoval dve konštantné hodnoty: INF = 9999 a MAX = 10 . Deklarovali sme prototypovanie funkcie a následne definovali funkciu pre Dijkstrov algoritmus ako DijkstraAlgorithm ktorý akceptuje tri argumenty – graf pozostávajúci z uzlov, počet uzlov v grafe a zdrojový uzol. V rámci tejto funkcie sme definovali niektoré dátové štruktúry, ako je 2D matica, ktorá bude fungovať ako prioritná fronta pre algoritmus, pole na udržiavanie vzdialenosti medzi uzlami, pole na udržiavanie záznamu predchádzajúcich uzlov, pole na ukladanie informácie o navštívených uzloch a niektoré celočíselné premenné na uloženie hodnoty minimálnej vzdialenosti, počítadla, hodnoty ďalšieho uzla a ďalšie. Potom sme použili a vnorené pre slučku iterovať cez uzly grafu a podľa toho ich pridať do fronty priorít. Opäť sme použili for-loop iterovať cez prvky v prioritnom fronte počnúc od zdrojového uzla a aktualizovať ich vzdialenosti. Mimo slučky máme nastavenú vzdialenosť zdrojového uzla ako 0 a označili ho ako navštívené v navštívené_uzly[] pole. Potom sme nastavili hodnotu počítadla ako jednu a použili sme zatiaľ čo opakovanie cyklu cez počet uzlov. Vo vnútri tejto slučky sme nastavili hodnotu minimálna_vzdialenosť ako INF a použil for-loop aktualizovať hodnotu minimálna_vzdialenosť premenná s minimálnou hodnotou z a vzdialenosť[] pole. Potom sme iterovali cez nenavštívené susedné uzly vybraného uzla pomocou for-loop a vykonali relaxáciu. Potom sme vytlačili výsledné údaje o vzdialenostiach vypočítaných pomocou Dijkstrovho algoritmu.

V Hlavná definovali a deklarovali sme premenné reprezentujúce graf, počet uzlov a zdrojový uzol. Nakoniec sme zavolali DijkstraAlgorithm() funkciu odovzdaním požadovaných parametrov.

V dôsledku toho sa používateľom vytlačia požadované najkratšie možné cesty pre každý uzol zo zdrojového uzla.

Kód pre Dijkstrov algoritmus v C++

Nasleduje implementácia Dijkstrovho algoritmu v programovacom jazyku C++:

Súbor: 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;>

Vysvetlenie:

Vo vyššie uvedenom úryvku kódu sme zahrnuli 'iostream' a 'vektor' hlavičkové súbory a definovali konštantnú hodnotu ako MAX_INT = 1 000 000 . Potom sme použili štandardný menný priestor a vytvorili prototyp DijkstraAlgorithm() funkciu. Potom sme definovali hlavnú funkciu programu, ktorú sme nazvali DijkstraAlgorithm() funkciu. Potom sme deklarovali niektoré triedy na vytváranie vrcholov a hrán. Tiež sme prototypovali viac funkcií na nájdenie najkratšej možnej cesty zo zdrojového vrcholu do cieľového vrcholu a vytvorili sme inštancie tried Vertex a Edge. Potom sme definovali obe triedy, aby sme vytvorili vrcholy a hrany grafu. Potom sme definovali DijkstraAlgorithm() funkcia na vytvorenie grafu a vykonávanie rôznych operácií. Vo vnútri tejto funkcie sme deklarovali niektoré vrcholy a hrany. Potom sme nastavili zdrojový vrchol grafu a zavolali ho Dijkstra() funkcia na nájdenie najkratšej možnej vzdialenosti a Print_Shortest_Route_To() funkcia na tlač najkratšej vzdialenosti od zdrojového vrcholu k vrcholu 'F' . Potom sme definovali Dijkstra() funkcia na výpočet najkratších možných vzdialeností všetkých vrcholov od zdrojového vrcholu. Definovali sme tiež niekoľko ďalších funkcií na nájdenie vrcholu s najkratšou vzdialenosťou, aby sme vrátili všetky vrcholy susediace so zvyšným vrcholom, vrátili vzdialenosť medzi dvoma spojenými vrcholmi, skontrolovali, či vybraný vrchol v grafe existuje, a vytlačili najkratšia možná cesta zo zdrojového vrcholu do cieľového vrcholu.

Výsledkom je požadovaná najkratšia cesta pre vrchol 'F' zo zdrojového uzla sa vytlačí pre používateľov.

Kód pre Dijkstrov algoritmus v Jave

Nasleduje implementácia Dijkstrovho algoritmu v programovacom jazyku Java:

Súbor: 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;>

Vysvetlenie:

Vo vyššie uvedenom úryvku kódu sme definovali verejnú triedu ako DijkstraAlgorithm() . V rámci tejto triedy sme definovali verejnú metódu ako dijkstraAlgorithm() nájsť najkratšiu vzdialenosť od zdrojového vrcholu k cieľovému vrcholu. V rámci tejto metódy sme definovali premennú na uloženie počtu uzlov. Potom sme definovali boolovské pole na ukladanie informácií o navštívených vrcholoch a celočíselné pole na ukladanie ich príslušných vzdialeností. Spočiatku sme deklarovali hodnoty v oboch poliach ako Nepravdivé a MAX_VALUE , resp. Tiež sme nastavili vzdialenosť zdrojového vrcholu na nulu a použili sme for-loop aktualizovať vzdialenosť medzi zdrojovým vrcholom a cieľovým vrcholom s minimálnou vzdialenosťou. Potom sme aktualizovali vzdialenosti susedných vrcholov vybraného vrcholu vykonaním relaxácie a vytlačili najkratšie vzdialenosti pre každý vrchol. Potom sme definovali metódu na nájdenie minimálnej vzdialenosti od zdrojového vrcholu k cieľovému vrcholu. Potom sme definovali hlavnú funkciu, kde sme deklarovali vrcholy grafu a vytvorili inštanciu DijkstraAlgorithm() trieda. Nakoniec sme zavolali dijkstraAlgorithm() metóda na nájdenie najkratšej vzdialenosti medzi zdrojovým vrcholom a cieľovým vrcholom.

V dôsledku toho sa používateľom vytlačia požadované najkratšie možné cesty pre každý uzol zo zdrojového uzla.

Kód pre Dijkstrov algoritmus v Pythone

Nasleduje implementácia Dijkstrovho algoritmu v programovacom jazyku Python:

Súbor: 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>

Výkon

 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 

Vysvetlenie:

Vo vyššie uvedenom úryvku kódu sme importovali sys modul a deklaroval zoznamy pozostávajúce z hodnôt pre uzly a hrany. Potom sme definovali funkciu ako toBeVisited() zistiť, ktorý uzol bude navštívený ako ďalší. Potom sme našli celkový počet uzlov v grafe a nastavili počiatočné vzdialenosti pre každý uzol. Potom sme vypočítali minimálnu vzdialenosť od zdrojového uzla k cieľovému uzlu, vykonali relaxáciu na susedných uzloch a aktualizovali vzdialenosti v zozname. Potom sme pre používateľov vytlačili tieto vzdialenosti zo zoznamu.

V dôsledku toho sa používateľom vytlačia požadované najkratšie možné cesty pre každý uzol zo zdrojového uzla.

Časová a priestorová zložitosť Dijkstrovho algoritmu

• Časová zložitosť Dijkstrovho algoritmu je O(E log V) , kde E je počet hrán a V je počet vrcholov.
• Priestorová zložitosť Dijkstrovho algoritmu je O(V), kde V je počet vrcholov.

Výhody a nevýhody Dijkstrovho algoritmu

Poďme diskutovať o niektorých výhodách Dijkstrovho algoritmu:

1. Jednou z hlavných výhod použitia Dijkstrovho algoritmu je, že má takmer lineárnu časovú a priestorovú zložitosť.
2. Tento algoritmus môžeme použiť na výpočet najkratšej cesty z jedného vrcholu do všetkých ostatných vrcholov a jedného zdrojového vrcholu do jedného cieľového vrcholu zastavením algoritmu, keď dostaneme najkratšiu vzdialenosť pre cieľový vrchol.
3. Tento algoritmus funguje iba pre orientované vážené grafy a všetky okraje tohto grafu by nemali byť záporné.

Napriek mnohým výhodám má Dijkstrov algoritmus aj niektoré nevýhody, ako napríklad:

1. Dijkstrov algoritmus vykonáva skrytý prieskum, ktorý počas procesu využíva veľa času.
2. Tento algoritmus nie je schopný zvládnuť negatívne hrany.
3. Keďže tento algoritmus smeruje k acyklickému grafu, nedokáže vypočítať presnú najkratšiu cestu.
4. Vyžaduje si tiež údržbu, aby sa zachoval záznam o navštívených vrcholoch.

Niektoré aplikácie Dijkstrovho algoritmu

Dijkstrov algoritmus má rôzne aplikácie v reálnom svete, z ktorých niektoré sú uvedené nižšie:

Digitálne mapové služby v Mapách Google:V rôznych situáciách sme sa pokúšali nájsť vzdialenosť v Mapách Google buď z našej polohy do najbližšieho preferovaného miesta, alebo z jedného mesta do druhého, čo zahŕňa viacero trás/trás, ktoré ich spájajú; aplikácia však musí zobraziť minimálnu vzdialenosť. Je to možné len preto, že Dijkstrov algoritmus pomáha aplikácii nájsť najkratšie miesto medzi dvoma danými miestami pozdĺž cesty. Uvažujme USA ako graf, v ktorom sú mestá/miesta reprezentované ako vrcholy a cesty medzi dvoma mestami/miestami sú reprezentované ako hrany. Potom pomocou Dijkstrovho algoritmu môžeme vypočítať najkratšie trasy medzi akýmikoľvek dvoma mestami/miestami.Aplikácie sociálnych sietí:V mnohých aplikáciách, ako je Facebook, Twitter, Instagram a ďalšie, si mnohí z nás mohli všimnúť, že tieto aplikácie navrhujú zoznam priateľov, ktorých môže konkrétny používateľ poznať. Ako mnohé spoločnosti v oblasti sociálnych médií implementujú tento typ funkcie efektívnym a efektívnym spôsobom, najmä keď má systém viac ako miliardu používateľov? Odpoveďou na túto otázku je Dijkstrov algoritmus. Štandardný Dijkstrov algoritmus sa vo všeobecnosti používa na odhadovanie najkratšej vzdialenosti medzi používateľmi meranej prostredníctvom spojení alebo vzájomnosti medzi nimi. Keď je sociálna sieť veľmi malá, používa okrem niektorých ďalších funkcií aj štandardný Dijkstrov algoritmus na určenie najkratších ciest. Ak je však graf oveľa väčší, počítanie štandardného algoritmu trvá niekoľko sekúnd, a preto sa ako alternatíva používajú niektoré pokročilé algoritmy.Telefónna sieť:Ako niektorí z nás možno vedia, v telefónnej sieti má každá prenosová linka šírku pásma „b“. Šírka pásma je najvyššia frekvencia, ktorú môže prenosová linka podporovať. Vo všeobecnosti platí, že ak je frekvencia signálu v určitom vedení vyššia, signál sa o toto vedenie zníži. Šírka pásma predstavuje množstvo informácií, ktoré môže linka preniesť. Uvažujme mesto ako graf, v ktorom sú spínacie stanice znázornené pomocou vrcholov, prenosové vedenia sú znázornené ako hrany a šírka pásma „b“ je znázornená pomocou hmotnosti hrán. Ako môžeme pozorovať, telefónna sieť môže spadať aj do kategórie problému s najkratšou vzdialenosťou a dá sa vyriešiť pomocou Dijkstrovho algoritmu.Letový program:Predpokladajme, že osoba potrebuje softvér na prípravu agendy letov pre zákazníkov. Agent má prístup k databáze so všetkými letmi a letiskami. Okrem čísla letu, východiskového letiska a destinácie majú lety aj časy odletov a príletov. Aby sme teda určili najskorší čas príletu do vybranej destinácie z pôvodného letiska a daného času začiatku, agenti využívajú Dijkstrov algoritmus.Smerovanie IP na vyhľadanie najprv otvorenej najkratšej cesty:Open Shortest Path First (skrátene OSPF) je smerovací protokol v stave spojenia, ktorý sa používa na nájdenie najlepšej cesty medzi zdrojovým a cieľovým smerovačom pomocou vlastnej Shortest Path First. Algoritmus Dijkstra sa vo veľkej miere využíva v smerovacích protokoloch požadovaných smerovačmi na aktualizáciu ich tabuľky presmerovania. Algoritmus poskytuje najkratšiu nákladovú cestu od zdrojového smerovača k ostatným smerovačom prítomným v sieti.Robotická cesta:V týchto dňoch vznikli drony a roboty, niektoré ovládané manuálne a iné automaticky. Drony a roboty, ktoré sú prevádzkované automaticky a používajú sa na doručenie balíkov na dané miesto alebo používané na akúkoľvek určitú úlohu, sú nakonfigurované pomocou modulu Dijkstra Algorithm tak, že vždy, keď je známy zdroj a cieľ, dron a robot sa budú pohybovať v objednanom smere. sledovaním najkratšej cesty s minimálnym časom potrebným na doručenie balíkov.Označte súborový server:Algoritmus Dijkstra sa tiež používa na označenie súborového servera v lokálnej sieti (LAN). Predpokladajme, že na prenos súborov z jedného počítača do druhého je potrebný nekonečný čas. Takže, aby sme minimalizovali počet „skokov“ zo súborového servera na každý druhý počítač v sieti, použijeme Dijkstrov algoritmus. Tento algoritmus vráti najkratšiu cestu medzi sieťami, čo má za následok minimálny počet skokov.

Záver

• Vo vyššie uvedenom návode sme po prvé pochopili základné pojmy Graph spolu s jeho typmi a aplikáciami.
• Potom sme sa dozvedeli o Dijkstrovom algoritme a jeho histórii.
• Pomocou príkladu sme tiež pochopili základné fungovanie Dijkstrovho algoritmu.
• Potom sme študovali, ako napísať kód pre Dijkstrov algoritmus pomocou Pseudokódu.
• Pozorovali sme jeho implementáciu v programovacích jazykoch ako C, C++, Java a Python so správnymi výstupmi a vysvetleniami.
• Tiež sme pochopili časovú a priestorovú zložitosť Dijkstrovho algoritmu.
• Nakoniec sme diskutovali o výhodách a nevýhodách Dijkstrovho algoritmu a niektorých jeho reálnych aplikáciách.