DIJKSTRA TRUMPIAUSIO KELIO ALGORITMAS SU PAVYZDŽIAIS

Ši pamoka išmokys mus apie Dijkstra trumpiausio kelio algoritmą. Dijkstros algoritmo veikimą suprasime laipsnišku grafiniu paaiškinimu.

Mes apimsime šiuos dalykus:

Trumpa pagrindinių grafiko sąvokų apžvalga
Suprasti Dijkstra algoritmo naudojimą
Supraskite algoritmo veikimą naudodami nuoseklų pavyzdį

Taigi, pradėkime.

Trumpas grafikų įvadas

Grafikai yra nelinijinės duomenų struktūros, vaizduojančios elementų „ryšius“. Šie elementai yra žinomi kaip Viršūnės , o linijos arba lankai, jungiantys bet kurias dvi grafiko viršūnes, yra žinomi kaip Kraštai . Kalbant formaliau, grafiką sudaro viršūnių rinkinys (V) ir briaunų rinkinys (E) . Grafikas žymimas G(V, E) .

Grafiko komponentai

Viršūnės:Viršūnės yra pagrindiniai grafiko vienetai, naudojami realiems objektams, asmenims ar subjektams vaizduoti. Kartais viršūnės taip pat žinomos kaip mazgai.Kraštai:Briaunos braižomos arba naudojamos sujungti dvi grafo viršūnes. Kartais kraštai taip pat žinomi kaip lankai.

Toliau pateiktame paveikslėlyje parodytas grafinis grafiko vaizdas:

java poeilutės pavyzdys

Figūra 1: Grafinis grafiko vaizdavimas

Aukščiau pateiktame paveikslėlyje viršūnės/mazgai žymimi spalvotais apskritimais, o kraštai – mazgus jungiančiomis linijomis.

Grafikų programos

Grafikai naudojami daugeliui realaus gyvenimo problemų išspręsti. Grafikai naudojami tinklams pavaizduoti. Šie tinklai gali apimti telefono ar grandyninius tinklus arba kelius mieste.

Pavyzdžiui, galėtume naudoti grafikus, kad sukurtume transporto tinklo modelį, kurio viršūnėse būtų rodomos įrenginius, kurie siunčia arba gauna produktus, o kraštai žymi juos jungiančius kelius arba takus. Toliau pateikiamas vaizdinis to paties vaizdas:

2 pav. Transporto tinklo vaizdavimas

Grafikai taip pat naudojami įvairiose socialinės žiniasklaidos platformose, tokiose kaip „LinkedIn“, „Facebook“, „Twitter“ ir kt. Pavyzdžiui, tokios platformos kaip „Facebook“ naudoja grafikus, kad saugotų savo vartotojų duomenis, kur kiekvienas asmuo yra pažymėtas viršūne, o kiekviena iš jų yra struktūra, kurioje yra tokia informacija kaip asmens ID, vardas, lytis, adresas ir kt.

Grafikų tipai

Grafikus galima suskirstyti į du tipus:

Nenukreiptas grafikas
Režisuotas grafikas

Nenukreiptas grafikas: Grafikas su briaunomis, kurios neturi krypties, vadinamas nenukreiptu grafiku. Šio grafiko kraštai reiškia dvipusį ryšį, kai kiekvieną briauną galima kirsti abiem kryptimis. Toliau pateiktame paveikslėlyje parodytas paprastas neorientuotas grafikas su keturiais mazgais ir penkiomis briaunomis.

3 pav. Paprastas neorientuotas grafikas

Režisuotas grafikas: Grafikas su briaunomis su kryptimis vadinamas nukreiptu grafiku. Šio grafiko kraštai reiškia vienpusį ryšį, kai kiekvieną briauną galima kirsti tik viena kryptimi. Toliau pateiktame paveikslėlyje parodytas paprastas nukreiptas grafikas su keturiais mazgais ir penkiomis briaunomis.

4 pav. Paprastas nukreiptas grafikas

Absoliutus kraštinių ilgis, padėtis arba orientacija grafiko iliustracijoje paprastai neturi reikšmės. Kitaip tariant, tą patį grafą galime vizualizuoti skirtingais būdais, pertvarkydami viršūnes arba iškraipydami briaunas, jei nesikeičia pagrindinė grafo struktūra.

Kas yra svertiniai grafikai?

Grafikas laikomas svertiniu, jei kiekvienai briaunai priskiriamas „svoris“. Krašto svoris gali reikšti atstumą, laiką ar bet ką, kas modeliuoja „ryšį“ tarp viršūnių poros, kurią ji jungia.

Pavyzdžiui, mes galime stebėti mėlyną skaičių šalia kiekvieno krašto kitame svertinio grafiko paveiksle. Šis skaičius naudojamas atitinkamo krašto svoriui reikšti.

5 pav. Svertinio grafiko pavyzdys

Dijkstros algoritmo įvadas

Dabar, kai žinome kai kurias pagrindines grafikų sąvokas, pasinerkime į Dijkstros algoritmo koncepcijos supratimą.

Ar kada susimąstėte, kaip „Google Maps“ randa trumpiausią ir greičiausią maršrutą tarp dviejų vietų?

Na, atsakymas yra Dijkstros algoritmas . Dijkstros algoritmas yra grafiko algoritmas kad randa trumpiausią kelią iš šaltinio viršūnės į visas kitas grafiko viršūnes (vieno šaltinio trumpiausias kelias). Tai godaus algoritmo tipas, kuris veikia tik svertiniuose grafikuose, turinčiuose teigiamą svorį. Dijkstros algoritmo sudėtingumas laike yra O(V²) grafo gretimų matricos vaizdavimo pagalba. Šio laiko sudėtingumą galima sumažinti iki O((V + E) log V) gretimų sąrašo grafo atvaizdavimo pagalba, kur IN yra viršūnių skaičius ir IR yra grafiko briaunų skaičius.

Dijkstros algoritmo istorija

Dijkstros algoritmą sukūrė ir išleido Dr. Edsgeris W. Dijkstra , olandų kompiuterių mokslininkas, programinės įrangos inžinierius, programuotojas, mokslo eseistas ir sistemų mokslininkas.

kas yra abėcėlės skaičius

2001 m. duodamas interviu su Philipu L. Frana, skirtą ACM žurnalo komunikacijai, daktaras Edsgeris W. Dijkstra atskleidė:

„Koks trumpiausias kelias iš Roterdamo į Groningeną apskritai: iš nurodyto miesto į konkretų miestą? Tai trumpiausio kelio algoritmas, kurį sukūriau maždaug per dvidešimt minučių. Vieną rytą apsipirkinėjau Amsterdame su savo jauna sužadėtine ir pavargę atsisėdome kavinės terasoje išgerti puodelio kavos ir aš tik galvojau, ar galėčiau tai padaryti, o tada sukūriau trumpiausio kelio algoritmą. . Kaip sakiau, tai buvo dvidešimties minučių išradimas. Tiesą sakant, jis buvo paskelbtas 59 m., po trejų metų. Leidinys vis dar skaitomas, tiesą sakant, visai gražus. Viena iš priežasčių, kodėl jis toks gražus, buvo tai, kad sukūriau jį be pieštuko ir popieriaus. Vėliau sužinojau, kad vienas iš dizaino be pieštuko ir popieriaus privalumų yra tai, kad esate beveik priversti vengti visų išvengiamų sunkumų. Ilgainiui tas algoritmas mano didžiulei nuostabai tapo vienu iš kertinių mano šlovės akmenų.

Dirbdamas programuotoju Matematikos centre 1956 m., Dijkstra galvojo apie trumpiausio kelio problemą, kad parodytų naujo kompiuterio, žinomo kaip ARMAC, galimybes. Jo tikslas buvo pasirinkti ir problemą, ir sprendimą (kurį sukuria kompiuteris), kuriuos žmonės, neturintys kompiuterinio pagrindo, galėtų suprasti. Jis sukūrė trumpiausio kelio algoritmą ir vėliau jį įgyvendino ARMAC, kad būtų sukurtas neaiškiai sutrumpintas 64 Nyderlandų miestų transporto žemėlapis (64 miestai, todėl miesto numeriui užkoduoti pakaktų 6 bitų). Po metų jis susidūrė su kita problema, kurią iškėlė aparatūros inžinieriai, valdantys kitą instituto kompiuterį: Sumažinkite laidų kiekį, reikalingą mašinos galiniame skydelyje esantiems kaiščiams prijungti. Kaip sprendimą jis iš naujo atrado algoritmą, vadinamą Prim minimalaus apimančio medžio algoritmu, ir paskelbė jį 1959 m.

Dijkstros algoritmo pagrindai

Toliau pateikiamos pagrindinės Dijkstros algoritmo sąvokos:

Dijkstra algoritmas prasideda nuo mūsų pasirinkto mazgo (šaltinio mazgo) ir tiria grafiką, kad surastų trumpiausią kelią tarp to mazgo ir visų kitų grafiko mazgų.
Algoritmas saugo šiuo metu patvirtinto trumpiausio atstumo nuo kiekvieno mazgo iki šaltinio mazgo įrašus ir atnaujina šias reikšmes, jei randa trumpesnį kelią.
Kai Algoritmas nuskaito trumpiausią kelią tarp šaltinio ir kito mazgo, tas mazgas pažymimas kaip „aplankytas“ ir įtraukiamas į kelią.
Procedūra tęsiama tol, kol visi grafiko mazgai bus įtraukti į kelią. Tokiu būdu mes turime kelią, jungiantį šaltinio mazgą su visais kitais mazgais, einant trumpiausiu įmanomu keliu pasiekti kiekvieną mazgą.

Dijkstros algoritmo veikimo supratimas

A grafiką ir šaltinio viršūnė yra Dijkstros algoritmo reikalavimai. Šis algoritmas yra nustatytas taikant Greedy Approach, todėl kiekviename algoritmo žingsnyje suranda lokaliai optimalų pasirinkimą (šiuo atveju vietinius minimumus).

Kiekviena šio algoritmo viršūnė turės dvi jai apibrėžtas savybes:

Aplankytas turtas
Kelio nuosavybė

Supraskime šias savybes trumpai.

Aplankytas turtas:

Ypatybė „aplankyta“ nurodo, ar mazgas buvo aplankytas, ar ne.
Naudojame šią nuosavybę, kad nereikėtų pakartotinai apsilankyti jokiame mazge.
Mazgas pažymimas aplankytas tik tada, kai randamas trumpiausias kelias.

Kelio ypatybė:

Ypatybė „kelias“ saugo dabartinio minimalaus kelio į mazgą vertę.
Dabartinis minimalus kelias reiškia trumpiausią kelią, kuriuo iki šiol pasiekėme šį mazgą.
Ši savybė peržiūrima, kai aplankomas bet kuris mazgo kaimynas.
Ši savybė svarbi, nes joje bus saugomas galutinis kiekvieno mazgo atsakymas.

Iš pradžių visas viršūnes arba mazgus pažymime neaplankytas, nes jos dar turi būti aplankytos. Kelias į visus mazgus taip pat nustatytas iki begalybės, išskyrus šaltinio mazgą. Be to, kelias į šaltinio mazgą yra nustatytas į nulį (0).

Tada pasirenkame šaltinio mazgą ir pažymime jį kaip aplankytą. Po to pasiekiame visus gretimus šaltinio mazgo mazgus ir kiekviename mazge atliekame atsipalaidavimą. Atsipalaidavimas yra procesas, kurio metu sumažinamos sąnaudos norint pasiekti mazgą naudojant kitą mazgą.

Atsipalaidavimo procese kiekvieno mazgo kelias peržiūrimas iki minimalios vertės tarp mazgo dabartinio kelio, kelio iki ankstesnio mazgo ir kelio nuo ankstesnio mazgo iki dabartinio mazgo sumos.

Tarkime, kad p[n] yra dabartinio mazgo n kelio reikšmė, p[m] yra kelio iki anksčiau aplankyto mazgo m reikšmė, o w yra krašto tarp dabartinio mazgo ir anksčiau aplankytas vienas (krašto svoris tarp n ir m).

Matematine prasme atsipalaidavimą galima iliustruoti kaip:

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

Tada kiekviename tolesniame žingsnyje pažymime neaplankytą mazgą, kurio kelias yra mažiausiai aplankytas, ir atnaujiname jo kaimyno kelius.

Kartojame šią procedūrą tol, kol visi grafiko mazgai bus pažymėti kaip aplankyti.

Kai į aplankytą rinkinį įtraukiame mazgą, kelias į visus gretimus mazgus taip pat atitinkamai pasikeičia.

10 iš 100,00

Jei kuris nors mazgas paliekamas nepasiekiamas (atjungtas komponentas), jo kelias lieka „begalybė“. Jei pats šaltinis yra atskiras komponentas, kelias į visus kitus mazgus lieka „begalybė“.

Dijkstros algoritmo supratimas su pavyzdžiu

Toliau pateikiamas žingsnis, kurį atliksime įgyvendindami Dijkstra algoritmą:

1 žingsnis: Pirmiausia pažymėsime šaltinio mazgą, kurio srovės atstumas yra 0, o likusius mazgus nustatysime į INFINITY.

2 žingsnis: Tada nustatysime nelankytą mazgą su mažiausiu dabartiniu atstumu kaip dabartinį mazgą, tarkime, X.

3 veiksmas: Kiekvienam dabartinio mazgo X kaimynui N: tada pridėsime dabartinį atstumą X su krašto, jungiančio X-N, svoriu. Jei jis yra mažesnis už dabartinį N atstumą, nustatykite jį kaip naują dabartinį N atstumą.

4 veiksmas: Tada pažymėsime dabartinį mazgą X kaip aplankytą.

5 veiksmas: Procedūrą kartosime nuo '2 žingsnis' jei grafike liko neaplankytas mazgas.

Dabar supraskime algoritmo įgyvendinimą naudodamiesi pavyzdžiu:

6 pav. Duotas grafikas

Aukščiau pateiktą grafiką naudosime kaip įvestį su mazgu A kaip šaltinis.
Pirmiausia pažymėsime visus mazgus kaip nelankytus.
Mes nustatysime kelią į 0 mazge A ir BEGALINĖ visiems kitiems mazgams.
Dabar pažymėsime šaltinio mazgą A kaip aplankytas ir pasiekti gretimus mazgus.
Pastaba: Mes tik priėjome prie gretimų mazgų, juose neaplankėme.
Dabar mes atnaujinsime kelią į mazgą B pateikė 4 atsipalaidavimo pagalba, nes kelias į mazgą A yra 0 ir kelias nuo mazgo A į B yra 4 , ir minimumas ((0 + 4), BEGALIS) yra 4 .
Taip pat atnaujinsime kelią į mazgą C pateikė 5 atsipalaidavimo pagalba, nes kelias į mazgą A yra 0 ir kelias nuo mazgo A į C yra 5 , ir minimumas ((0 + 5), BEGALIS) yra 5 . Abu mazgo kaimynai A dabar atsipalaidavę; todėl galime judėti į priekį.
Dabar pasirinksime kitą nelankytą mazgą, turintį mažiausiai kelią, ir aplankysime jį. Taigi mes aplankysime mazgą B ir atlikti atsipalaidavimą savo nelankomiems kaimynams. Atlikus atsipalaidavimą, kelias į mazgą C išliks 5 , o kelias į mazgą IR taps vienuolika , ir kelias į mazgą D taps 13 .
Dabar aplankysime mazgą IR ir atpalaiduoti kaimyninius mazgus B, D , ir F . Kadangi tik mazgas F yra nelankyta, ji bus atsipalaidavusi. Taigi kelias į mazgą B liks toks, koks yra, t.y. 4 , kelias į mazgą D taip pat liks 13 , ir kelias į mazgą F taps 14 (8 + 6) .
Dabar aplankysime mazgą D , ir tik mazgas F bus atsipalaidavęs. Tačiau kelias į mazgą F išliks nepakitęs, t.y. 14 .
Kadangi tik mazgas F Liko, mes jį aplankysime, bet neatliksime jokio atsipalaidavimo, nes visi kaimyniniai mazgai jau aplankyti.
Kai aplankysite visus grafikų mazgus, programa baigsis.

Taigi, galutiniai keliai, kuriuos padarėme, yra:

 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)

Dijkstros algoritmo pseudokodas

Dabar suprasime Dijkstros algoritmo pseudokodą.

Turime registruoti kiekvieno mazgo kelio atstumą. Todėl kiekvieno mazgo kelio atstumą galime saugoti n dydžio masyve, kur n yra bendras mazgų skaičius.
Be to, norime gauti trumpiausią kelią kartu su to kelio ilgiu. Norėdami išspręsti šią problemą, kiekvieną mazgą susiesime su mazgu, kuris paskutinį kartą atnaujino savo kelio ilgį.
Kai algoritmas bus baigtas, galime nukreipti paskirties mazgą į šaltinio mazgą, kad gautume kelią.
Galime naudoti minimalią prioritetų eilę, kad efektyviai gautume mazgą su mažiausiu kelio atstumu.

Dabar įgyvendinkime aukščiau pateiktos iliustracijos pseudokodą:

Pseudokodas:

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

Paaiškinimas:

Į aukščiau pateiktą kodo fragmentą įtraukėme stdio.h antraštės failas apibrėžė dvi pastovias reikšmes: INF = 9999 ir MAX = 10 . Mes paskelbėme funkcijos prototipą ir tada apibrėžėme Dijkstros algoritmo funkciją kaip DijkstraAlgoritmas kuri priima tris argumentus – grafiką, kurį sudaro mazgai, mazgų skaičių diagramoje ir šaltinio mazgą. Šioje funkcijoje apibrėžėme kai kurias duomenų struktūras, tokias kaip 2D matrica, kuri veiks kaip algoritmo prioritetų eilė, masyvas, skirtas atstumui tarp mazgų nustatyti, masyvas, skirtas išsaugoti ankstesnių mazgų įrašus, masyvas saugoti. aplankytų mazgų informacija ir kai kurie sveikieji kintamieji, skirti saugoti mažiausio atstumo reikšmę, skaitiklį, kito mazgo vertę ir kt. Tada mes panaudojome a įdėtas for-kilpas kartoti Grafo mazgus ir atitinkamai įtraukti juos į prioritetinę eilę. Mes vėl panaudojome for-kilpa kartoti prioritetinės eilės elementus, pradedant nuo šaltinio mazgo, ir atnaujinti jų atstumus. Už ciklo ribų mes nustatėme šaltinio mazgo atstumą kaip 0 ir pažymėjo kaip aplankytą lankomi_mazgai[] masyvas. Tada nustatėme skaitiklio vertę kaip vieną ir panaudojome kol ciklo iteracija per mazgų skaičių. Šios kilpos viduje nustatėme reikšmę minimalus_atstumas kaip INF ir naudojo for-kilpa norėdami atnaujinti vertę minimalus_atstumas kintamasis su mažiausia reikšme nuo a atstumas[] masyvas. Tada perėjome per neaplankytus gretimus pasirinkto mazgo mazgus, naudodami for-kilpa ir atliko relaksaciją. Tada atspausdinome gautus atstumų duomenis, apskaičiuotus naudojant Dijkstros algoritmą.

Viduje pagrindinis funkciją, apibrėžėme ir deklaravome kintamuosius, vaizduojančius grafiką, mazgų skaičių ir šaltinio mazgą. Pagaliau mes paskambinome į DijkstraAlgoritm() funkcija perduodant reikiamus parametrus.

Dėl to vartotojams išspausdinami reikalingi trumpiausi kiekvieno mazgo keliai iš šaltinio mazgo.

Dijkstra algoritmo kodas C++

Toliau pateikiamas Dijkstra algoritmo įgyvendinimas C++ programavimo kalba:

Failas: DijkstraAlgorithm.cpp

latekso teksto dydis

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

Paaiškinimas:

Į aukščiau pateiktą kodo fragmentą įtraukėme 'iostream' ir 'vektorius' antraštės failus ir apibrėžė pastovią reikšmę kaip MAX_INT = 10000000 . Tada panaudojome standartinę vardų erdvę ir sukūrėme prototipą DijkstraAlgoritm() funkcija. Tada apibrėžėme pagrindinę programos funkciją, kurią pavadinome DijkstraAlgoritm() funkcija. Po to mes paskelbėme kai kurias klases, kad sukurtume viršūnes ir briaunas. Taip pat sukūrėme daugiau funkcijų, kad rastume trumpiausią įmanomą kelią nuo šaltinio viršūnės iki paskirties viršūnės, ir sukūrėme Vertex ir Edge klases. Tada apibrėžėme abi klases, kad sukurtume grafiko viršūnes ir briaunas. Tada mes apibrėžėme DijkstraAlgoritm() funkcija sukurti grafiką ir atlikti įvairias operacijas. Šioje funkcijoje mes paskelbėme kai kurias viršūnes ir briaunas. Tada nustatome grafiko šaltinio viršūnę ir vadiname Dijkstra () funkcija rasti trumpiausią įmanomą atstumą ir Spausdinti_Trumpiausias_Maršrutas_Į() funkcija spausdinti trumpiausią atstumą nuo šaltinio viršūnės iki viršūnės 'F' . Tada mes apibrėžėme Dijkstra () funkcija, skirta apskaičiuoti trumpiausius įmanomus atstumus tarp visų viršūnių nuo šaltinio viršūnės. Taip pat apibrėžėme dar keletą funkcijų, leidžiančių rasti trumpiausią atstumą turinčią viršūnę, grąžinti visas viršūnes, esančias šalia likusios viršūnės, grąžinti atstumą tarp dviejų sujungtų viršūnių, patikrinti, ar pasirinkta viršūnė yra grafe, ir atspausdinti trumpiausias įmanomas kelias nuo šaltinio viršūnės iki paskirties viršūnės.

Dėl to viršūnei reikalingas trumpiausias kelias 'F' iš šaltinio mazgo išspausdinamas vartotojams.

Dijkstra algoritmo kodas Java

Toliau pateikiamas Dijkstra algoritmo įgyvendinimas Java programavimo kalboje:

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

Paaiškinimas:

Aukščiau pateiktame kodo fragmente viešąją klasę apibrėžėme kaip DijkstraAlgoritm() . Šioje klasėje viešąjį metodą apibrėžėme kaip dijkstraAlgoritmas() Norėdami rasti trumpiausią atstumą nuo šaltinio viršūnės iki paskirties viršūnės. Šio metodo viduje apibrėžėme kintamąjį mazgų skaičiui saugoti. Tada apibrėžėme Būlio masyvą, skirtą informacijai apie aplankytas viršūnes saugoti, ir sveikųjų skaičių masyvą atitinkamiems jų atstumams saugoti. Iš pradžių abiejų masyvų reikšmes paskelbėme kaip Netiesa ir MAX_VALUE , atitinkamai. Mes taip pat nustatėme atstumą nuo šaltinio viršūnės kaip nulį ir panaudojome for-kilpa atnaujinti atstumą tarp šaltinio viršūnių ir paskirties viršūnių su minimaliu atstumu. Tada atnaujinome pasirinktos viršūnės gretimų viršūnių atstumus atlikdami relaksaciją ir atspausdinome trumpiausius atstumus kiekvienai viršūnei. Tada apibrėžėme metodą, kaip rasti mažiausią atstumą nuo šaltinio viršūnės iki paskirties viršūnės. Tada apibrėžėme pagrindinę funkciją, kurioje deklaravome grafiko viršūnes ir suformulavome DijkstraAlgoritm() klasė. Galiausiai paskambinome į dijkstraAlgoritmas() būdas rasti trumpiausią atstumą tarp šaltinio viršūnės ir paskirties viršūnių.

Dėl to vartotojams išspausdinami reikalingi trumpiausi kiekvieno mazgo keliai iš šaltinio mazgo.

java versija linux

Dijkstros algoritmo kodas Python

Toliau pateikiamas Dijkstra algoritmo įgyvendinimas Python programavimo kalboje:

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

Išvestis

 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

Paaiškinimas:

Aukščiau pateiktame kodo fragmente importavome sys modulį ir paskelbė sąrašus, sudarytus iš mazgų ir kraštų reikšmių. Tada apibrėžėme funkciją kaip būti Lankytam () norėdami sužinoti, kuris mazgas bus aplankytas toliau. Tada grafike radome bendrą mazgų skaičių ir nustatėme kiekvieno mazgo pradinius atstumus. Tada apskaičiavome mažiausią atstumą nuo šaltinio mazgo iki paskirties mazgo, atlikome gretimų mazgų atsipalaidavimą ir atnaujinome atstumus sąraše. Tada mes atspausdinome tuos atstumus iš sąrašo vartotojams.

Dėl to vartotojams išspausdinami reikalingi trumpiausi kiekvieno mazgo keliai iš šaltinio mazgo.

Dijkstros algoritmo laiko ir erdvės sudėtingumas

Dijkstros algoritmo laiko sudėtingumas yra O (E log V) , kur E yra briaunų skaičius, o V yra viršūnių skaičius.
Dijkstros algoritmo erdvės sudėtingumas yra O(V), kur V yra viršūnių skaičius.

Dijkstros algoritmo privalumai ir trūkumai

Pakalbėkime apie kai kuriuos Dijkstra algoritmo pranašumus:

Vienas iš pagrindinių Dijkstra algoritmo pranašumų yra tai, kad jis turi beveik linijinį laiko ir erdvės sudėtingumą.
Šį algoritmą galime naudoti norėdami apskaičiuoti trumpiausią kelią nuo vienos viršūnės iki visų kitų viršūnių ir vienos šaltinio viršūnės iki vienos paskirties viršūnės, sustabdydami algoritmą, kai tik gauname trumpiausią atstumą iki paskirties viršūnės.
Šis algoritmas veikia tik nukreiptuose svertiniuose grafikuose, o visos šio grafiko briaunos turi būti neneigiamos.

Nepaisant daugybės pranašumų, Dijkstra algoritmas turi ir trūkumų, tokių kaip:

Dijkstra algoritmas atlieka paslėptą tyrinėjimą, kuris proceso metu sunaudoja daug laiko.
Šis algoritmas neveikia neigiamų kraštų.
Kadangi šis algoritmas nukreipiamas į aciklinį grafiką, jis negali apskaičiuoti tikslaus trumpiausio kelio.
Taip pat reikalinga priežiūra, kad būtų galima registruoti aplankytas viršūnes.

Kai kurios Dijkstros algoritmo programos

Dijkstra algoritmas turi įvairių realaus pasaulio programų, kai kurios iš jų nurodytos toliau:

Skaitmeninių žemėlapių paslaugos „Google“ žemėlapiuose:Kartais Google žemėlapiuose bandėme rasti atstumą nuo savo vietos iki artimiausios pageidaujamos vietos arba nuo vieno miesto iki kito, kurį sudaro keli juos jungiantys maršrutai/takai; tačiau programoje turi būti rodomas minimalus atstumas. Tai įmanoma tik todėl, kad Dijkstra algoritmas padeda programai rasti trumpiausią tarp dviejų nurodytų vietų kelyje. Panagrinėkime JAV kaip grafiką, kuriame miestai/vietos vaizduojami kaip viršūnės, o maršrutai tarp dviejų miestų/vietos – kaip briaunos. Tada naudodamiesi Dijkstra algoritmu galime apskaičiuoti trumpiausius maršrutus tarp bet kurių dviejų miestų / vietų.Socialinių tinklų programos:Daugelyje programų, pvz., „Facebook“, „Twitter“, „Instagram“ ir kt., daugelis iš mūsų galėjo pastebėti, kad šios programos siūlo draugų, kuriuos gali žinoti konkretus vartotojas, sąrašą. Kaip daugelis socialinės žiniasklaidos įmonių efektyviai ir efektyviai įdiegia tokio tipo funkcijas, ypač kai sistemoje yra daugiau nei milijardas vartotojų? Atsakymas į šį klausimą yra Dijkstros algoritmas. Standartinis Dijkstra algoritmas paprastai naudojamas įvertinti trumpiausią atstumą tarp vartotojų, išmatuotą per ryšius arba tarpusavio tarpusavio ryšį. Kai socialinis tinklas yra labai mažas, jis naudoja standartinį Dijkstra algoritmą, be kai kurių kitų funkcijų, kad nustatytų trumpiausius kelius. Tačiau, kai grafikas yra daug didesnis, standartiniam algoritmui suskaičiuoti reikia kelių sekundžių, todėl kai kurie pažangūs algoritmai naudojami kaip alternatyva.Telefono tinklas:Kaip kai kurie iš mūsų gali žinoti, telefono tinkle kiekviena perdavimo linija turi pralaidumą „b“. Pralaidumas yra didžiausias dažnis, kurį perdavimo linija gali palaikyti. Apskritai, jei signalo dažnis yra didesnis konkrečioje linijoje, signalas ta linija sumažinamas. Pralaidumas reiškia informacijos kiekį, kurį linija gali perduoti. Panagrinėkime miestą grafu, kuriame perjungimo stotys vaizduojamos naudojant viršūnes, perdavimo linijos vaizduojamos kaip briaunos, o pralaidumas „b“ yra pavaizduotas naudojant briaunų svorį. Taigi, kaip matome, telefono tinklas taip pat gali patekti į trumpiausio atstumo problemos kategoriją ir gali būti išspręstas naudojant Dijkstra algoritmą.Skrydžio programa:Tarkime, kad žmogui reikalinga programinė įranga, kad galėtų parengti klientų skrydžių darbotvarkę. Agentas turi prieigą prie visų skrydžių ir oro uostų duomenų bazės. Be skrydžio numerio, pradinio oro uosto ir paskirties vietos, skrydžiai taip pat turi išvykimo ir atvykimo laiką. Taigi, norėdami nustatyti anksčiausią atvykimo laiką į pasirinktą paskirties vietą iš pradinio oro uosto ir nurodytą pradžios laiką, agentai naudojasi Dijkstra algoritmu.IP maršruto parinkimas, kad pirmiausia būtų galima rasti atvirą trumpiausią kelią:Open Shortest Path First (sutrumpintai kaip OSPF) yra nuorodos būsenos maršruto parinkimo protokolas, naudojamas rasti geriausią kelią tarp šaltinio ir paskirties maršruto parinktuvo, naudojant savo trumpiausią kelią pirmiausia. Dijkstra algoritmas plačiai naudojamas maršruto parinkimo protokoluose, kurių reikalauja maršrutizatoriai, siekiant atnaujinti jų persiuntimo lentelę. Algoritmas pateikia trumpiausią sąnaudų kelią nuo šaltinio maršrutizatoriaus iki kitų tinkle esančių maršrutizatorių.Robotų kelias:Šiomis dienomis atsirado dronai ir robotai, kai kurie valdomi rankiniu būdu, o kiti automatiškai. Bepiločiai orlaiviai ir robotai, kurie yra valdomi automatiškai ir naudojami siuntoms pristatyti į nurodytą vietą arba naudojami bet kokiai užduočiai atlikti, yra sukonfigūruoti Dijkstra algoritmo modulyje, kad, kai tik žinomas šaltinis ir paskirties vieta, dronas ir robotas judėtų nurodyta kryptimi. trumpiausiu keliu, sutrumpindami siuntų pristatymo laiką.Nurodykite failų serverį:Dijkstra algoritmas taip pat naudojamas failų serveriui vietiniame tinkle (LAN) priskirti. Tarkime, kad failams perduoti iš vieno kompiuterio į kitą reikia begalinio laiko. Taigi, norėdami sumažinti „perėjimų“ skaičių iš failų serverio į kiekvieną kitą tinklo kompiuterį, naudosime Dijkstra algoritmą. Šis algoritmas grąžins trumpiausią kelią tarp tinklų, todėl bus pasiektas minimalus apynių skaičius.

Išvada

Aukščiau pateiktoje pamokoje, pirma, supratome pagrindines „Graph“ sąvokas, jo tipus ir programas.
Tada sužinojome apie Dijkstros algoritmą ir jo istoriją.
Mes taip pat supratome pagrindinį Dijkstros algoritmo veikimą naudodami pavyzdį.
Po to mes ištyrėme, kaip parašyti Dijkstra algoritmo kodą naudojant pseudokodą.
Stebėjome jo įgyvendinimą programavimo kalbose, tokiose kaip C, C++, Java ir Python, su tinkamais išėjimais ir paaiškinimais.
Taip pat supratome Dijkstros algoritmo laiko ir erdvės sudėtingumą.
Galiausiai aptarėme Dijkstra algoritmo ir kai kurių jo taikomųjų programų privalumus ir trūkumus.