Seuraava opetusohjelma opettaa meille Dijkstran lyhimmän polun algoritmin. Ymmärrämme Dijkstran algoritmin toiminnan vaiheittaisella graafisella selityksellä.

Käsittelemme seuraavat asiat:

• Lyhyt katsaus graafin peruskäsitteisiin
• Ymmärrä Dijkstran algoritmin käyttö
• Ymmärrä algoritmin toiminta vaiheittaisen esimerkin avulla

Joten aloitetaan.

Lyhyt johdatus kaavioihin

Kaaviot ovat epälineaarisia tietorakenteita, jotka edustavat elementtien välisiä 'yhteyksiä'. Nämä elementit tunnetaan nimellä Vertices , ja kaavion mitkä tahansa kaksi kärkeä yhdistäviä viivoja tai kaaria kutsutaan nimellä reunat . Muodollisemmin Graph sisältää joukko pisteitä (V) ja joukko reunoja (E) . Grafiikka on merkitty G(V, E) .

Graafin komponentit

Vertices:Vertices ovat graafin perusyksiköitä, joita käytetään edustamaan tosielämän kohteita, henkilöitä tai kokonaisuuksia. Joskus kärkipisteitä kutsutaan myös solmuiksi.Reunat:Reunat piirretään tai niitä käytetään yhdistämään graafin kaksi kärkeä. Joskus reunat tunnetaan myös kaareina.

Seuraavassa kuvassa on graafinen esitys graafista:

Kuvio 1: Graafinen esitys graafista

Yllä olevassa kuvassa kärjet/solmut on merkitty värillisillä ympyröillä ja reunat solmuja yhdistävillä viivoilla.

Graafisten sovellukset

Kaavioita käytetään ratkaisemaan monia tosielämän ongelmia. Graafeja käytetään edustamaan verkkoja. Nämä verkot voivat sisältää puhelin- tai piiriverkkoja tai polkuja kaupungissa.

Voisimme esimerkiksi käyttää Grapheja suunnitellaksesi liikenneverkkomallin, jossa kärjet näyttävät tuotteita lähettävät tai vastaanottavat tilat ja reunat edustavat niitä yhdistäviä teitä tai polkuja. Seuraava on kuvallinen esitys samasta:

Kuva 2: Liikenneverkoston kuvallinen esitys

Kaavioita käytetään myös erilaisissa sosiaalisen median alustoissa, kuten LinkedIn, Facebook, Twitter ja monet muut. Esimerkiksi Facebookin kaltaiset alustat tallentavat käyttäjiensä tiedot Grapheihin, joissa jokainen henkilö on merkitty kärjellä, ja jokainen niistä on rakenne, joka sisältää tietoja, kuten henkilötunnus, nimi, sukupuoli, osoite jne.

Graafisten tyypit

Graafit voidaan luokitella kahteen tyyppiin:

1. Ohjaamaton kaavio
2. Ohjattu graafi

Ohjaamaton kaavio: Graafia, jossa on reunoja, joilla ei ole suuntaa, kutsutaan suuntaamattomaksi kuvaajaksi. Tämän graafin reunat tarkoittavat kaksisuuntaista suhdetta, jossa jokainen reuna voidaan kulkea molempiin suuntiin. Seuraavassa kuvassa on yksinkertainen suuntaamaton graafi, jossa on neljä solmua ja viisi reunaa.

Kuva 3: Yksinkertainen ohjaamaton kaavio

Ohjattu graafi: Graafia, jonka reunat on suunnattu, kutsutaan suunnatuksi kuvaajaksi. Tämän graafin reunat tarkoittavat yksisuuntaista suhdetta, jossa jokainen reuna voidaan kulkea vain yhteen suuntaan. Seuraava kuva näyttää yksinkertaisen suunnatun graafin, jossa on neljä solmua ja viisi reunaa.

Kuva 4: Yksinkertainen ohjattu kaavio

Reunojen absoluuttisella pituudella, sijainnilla tai suunnalla kaaviokuvassa ei tyypillisesti ole merkitystä. Toisin sanoen, voimme visualisoida saman graafin eri tavoin järjestämällä kärjet uudelleen tai vääristämällä reunoja, jos graafin taustalla oleva rakenne ei muutu.

Mitä painotetut kaaviot ovat?

Graafin sanotaan olevan painotettu, jos jokaiselle reunalle on määritetty 'paino'. Reunan paino voi merkitä etäisyyttä, aikaa tai mitä tahansa, mikä mallintaa 'yhteyttä' sen yhdistämien huippupisteiden välillä.

Voimme esimerkiksi havaita sinisen numeron kunkin reunan vieressä painotetun kaavion seuraavassa kuvassa. Tätä numeroa käytetään merkitsemään vastaavan reunan painoa.

Kuva 5: Esimerkki painotetusta kaaviosta

Johdatus Dijkstran algoritmiin

Nyt kun tiedämme joitain Graphin peruskäsitteitä, sukeltakaamme ymmärtämään Dijkstran algoritmin käsitettä.

Oletko koskaan miettinyt, kuinka Google Maps löytää lyhimmän ja nopeimman reitin kahden paikan välillä?

No, vastaus on Dijkstran algoritmi . Dijkstran algoritmi on Graafi-algoritmi joka löytää lyhimmän polun lähdepisteestä kaikkiin muihin graafin kärkipisteisiin (yhden lähteen lyhin polku). Se on eräänlainen Greedy Algorithm, joka toimii vain painotetuissa kaavioissa, joilla on positiivinen paino. Dijkstran algoritmin aikamonimutkaisuus on O(V²) graafin vierekkäisyysmatriisiesityksen avulla. Tämän ajan monimutkaisuus voidaan vähentää O((V + E) log V) graafin vierekkäisyysluetteloesityksen avulla, jossa SISÄÄN on kärkien lukumäärä ja JA on graafin reunojen lukumäärä.

Dijkstran algoritmin historia

Dijkstran algoritmin suunnitteli ja julkaisi DR. Edsger W. Dijkstra , hollantilainen tietojenkäsittelytieteilijä, ohjelmistosuunnittelija, ohjelmoija, tiedeesseisti ja järjestelmätutkija.

Haastattelussa Philip L. Franan kanssa ACM-lehden viestinnässä vuonna 2001, tohtori Edsger W. Dijkstra paljasti:

'Mikä on lyhin tapa matkustaa Rotterdamista Groningeniin yleensä: annetusta kaupungista tiettyyn kaupunkiin? Se on lyhimmän polun algoritmi, jonka suunnittelin noin kahdessakymmenessä minuutissa. Eräänä aamuna olin ostoksilla Amsterdamissa nuoren morsiameni kanssa ja väsyneenä istuimme kahvilan terassille juomaan kupin kahvia ja mietin vain, voisinko tehdä tämän, ja sitten suunnittelin algoritmin lyhimmälle polulle. . Kuten sanoin, se oli kahdenkymmenen minuutin keksintö. Itse asiassa se julkaistiin vuonna 59, kolme vuotta myöhemmin. Julkaisu on edelleen luettavissa, se on itse asiassa aika mukava. Yksi syy siihen, että se on niin kiva, oli se, että suunnittelin sen ilman kynää ja paperia. Opin myöhemmin, että yksi ilman kynää ja paperia suunnittelun eduista on se, että joudut melkein välttämään kaikki vältettävissä olevat monimutkaisuudet. Lopulta tuosta algoritmista tuli suureksi hämmästykseksi yksi maineeni kulmakivistä.

Dijkstra pohti lyhimmän polun ongelmaa työskennellessään ohjelmoijana Mathematical Centerissä Amsterdamissa vuonna 1956 havainnollistaakseen uuden ARMAC-nimisen tietokoneen ominaisuuksia. Hänen tavoitteenaan oli valita sekä ongelma että ratkaisu (tietokoneen tuottama), joita ihmiset, joilla ei ole tietokonetaustaa, voisivat ymmärtää. Hän kehitti lyhimmän polun algoritmin ja suoritti sen myöhemmin ARMACille epämääräisesti lyhennetylle 64 Alankomaiden kaupungin kuljetuskartalle (64 kaupunkia, joten 6 bittiä riittäisi kaupungin numeron koodaamiseen). Vuotta myöhemmin hän törmäsi toiseen ongelmaan laitoksen seuraavaa tietokonetta käyttävillä laitteistoinsinööreillä: Minimoi koneen takapaneelin nastojen liittämiseen tarvittavan johdon määrä. Ratkaisuna hän löysi uudelleen Primin minimaalisen virittävän puun algoritmin ja julkaisi sen vuonna 1959.

Dijkstran algoritmin perusteet

Seuraavat ovat Dijkstran algoritmin peruskäsitteet:

1. Dijkstran algoritmi alkaa valitsemastamme solmusta (lähdesolmusta), ja se tutkii kaaviota löytääkseen lyhimmän polun kyseisen solmun ja kaavion kaikkien muiden solmujen välillä.
2. Algoritmi tallentaa tällä hetkellä kuitatun lyhimmän etäisyyden kustakin solmusta lähdesolmuun ja päivittää nämä arvot, jos se löytää lyhyemmän polun.
3. Kun algoritmi on hakenut lyhimmän polun lähteen ja toisen solmun välillä, kyseinen solmu merkitään 'vieraillut' ja sisällytetään polkuun.
4. Toimenpide jatkuu, kunnes kaikki kaavion solmut on sisällytetty polkuun. Tällä tavalla meillä on polku, joka yhdistää lähdesolmun kaikkiin muihin solmuihin noudattaen lyhintä mahdollista polkua kunkin solmun saavuttamiseksi.

Dijkstran algoritmin toiminnan ymmärtäminen

A kaavio ja lähdevertex ovat vaatimuksia Dijkstran algoritmille. Tämä algoritmi on perustettu Greedy Approachille ja löytää siten paikallisesti optimaalisen valinnan (tässä tapauksessa paikalliset minimit) algoritmin jokaisessa vaiheessa.

Jokaisella tämän algoritmin pisteellä on kaksi ominaisuutta sille määritettynä:

1. Vieraillut kiinteistössä
2. Polun omaisuus

Ymmärrämme nämä ominaisuudet lyhyesti.

Vierailtu kiinteistö:

1. Vierailtu-ominaisuus ilmaisee, onko solmussa käyty vai ei.
2. Käytämme tätä ominaisuutta, jotta emme käy uudelleen missään solmussa.
3. Solmu merkitään vierailluksi vasta, kun lyhin polku on löydetty.

Polun ominaisuus:

1. Ominaisuus 'polku' tallentaa nykyisen vähimmäispolun arvon solmuun.
2. Nykyinen vähimmäispolku tarkoittaa lyhimmän tien, jolla olemme saavuttaneet tämän solmun tähän mennessä.
3. Tämä ominaisuus tarkistetaan, kun missä tahansa solmun naapurissa käydään.
4. Tämä ominaisuus on tärkeä, koska se tallentaa lopullisen vastauksen jokaiselle solmulle.

Aluksi merkitsemme kaikki kärjet eli solmut vierailemattomiksi, koska niissä on vielä vierailematta. Polku kaikkiin solmuihin on myös asetettu äärettömyyteen lähdesolmun lisäksi. Lisäksi polku lähdesolmuun asetetaan nollaan (0).

Valitsemme sitten lähdesolmun ja merkitsemme sen käydyksi. Tämän jälkeen pääsemme kaikkiin lähdesolmun viereisiin solmuihin ja suoritamme rentoutumisen jokaisessa solmussa. Rentoutuminen on prosessi, jossa alennetaan solmun saavuttamisen kustannuksia toisen solmun avulla.

Relaksaatioprosessissa kunkin solmun polku tarkistetaan minimiarvoon solmun nykyisen polun, edellisen solmun polun ja edellisen solmun polun nykyiseen solmuun joukossa.

Oletetaan, että p[n] on solmun n nykyisen polun arvo, p[m] on polun arvo aiemmin vierailtuun solmuun m ja w on nykyisen solmun ja solmun välisen reunan paino. aiemmin vieraillut (reunapaino välillä n ja m).

Matemaattisessa mielessä rentoutumista voidaan kuvata seuraavasti:

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

Merkitsemme sitten jokaisessa seuraavassa vaiheessa vieraillun solmun, jolla on vähiten polku, käydyksi ja päivitämme sen naapurin polut.

Toistamme tätä menettelyä, kunnes kaikki kaavion solmut on merkitty vierailluiksi.

Aina kun lisäämme solmun vierailtuun joukkoon, polku kaikkiin sen viereisiin solmuihin muuttuu myös vastaavasti.

Jos jokin solmu jätetään tavoittamattomaksi (irrotettu komponentti), sen polku pysyy äärettömänä. Jos lähde itsessään on erillinen komponentti, polku kaikkiin muihin solmuihin pysyy 'äärettömänä'.

Dijkstran algoritmin ymmärtäminen esimerkin avulla

Seuraava on vaihe, jota noudatamme Dijkstran algoritmin toteuttamiseksi:

Vaihe 1: Ensin merkitsemme lähdesolmun nykyisellä etäisyydellä 0 ja asetamme loput solmut arvoon INFINITY.

Vaihe 2: Tämän jälkeen asetamme nykyiseksi solmuksi vierailemattoman solmun, jolla on pienin nykyinen etäisyys, oletetaan X.

Vaihe 3: Nykyisen solmun X kullekin naapurille N: Lisäämme sitten X:n nykyisen etäisyyden X-N:ää yhdistävän reunan painoon. Jos se on pienempi kuin N:n nykyinen etäisyys, aseta se uudeksi nykyiseksi etäisyydeksi N.

Vaihe 4: Merkitsemme sitten nykyisen solmun X käydyksi.

Vaihe 5: Toistamme prosessin alkaen 'Vaihe 2' jos kaaviossa on vierailematon solmu.

Ymmärretään nyt algoritmin toteutus esimerkin avulla:

Kuva 6: Annettu kaavio

1. Käytämme syötteenä yllä olevaa kuvaajaa solmun kanssa A lähteenä.
2. Ensin merkitään kaikki solmut vierailemattomiksi.
3. Asetamme polun 0 solmussa A ja INFINITY kaikille muille solmuille.
4. Merkitsemme nyt lähdesolmun A vieraillut ja käyttää sen viereisiä solmuja.
   Huomautus: Olemme käyttäneet vain viereisiä solmuja, emme käyneet niissä.
5. Päivitämme nyt polun solmuun B kirjoittaja 4 avulla rentoutumista, koska polku solmuun A On 0 ja polku solmusta A to B On 4 , ja minimi((0 + 4), INFINITY) On 4 .
6. Päivitämme myös polun solmuun C kirjoittaja 5 avulla rentoutumista, koska polku solmuun A On 0 ja polku solmusta A to C On 5 , ja minimi((0 + 5), INFINITY) On 5 . Molemmat solmun naapurit A ovat nyt rentoutuneet; siksi voimme mennä eteenpäin.
7. Valitsemme nyt seuraavan vierailemattoman solmun, jolla on pienin polku, ja vierailemme siinä. Siksi vierailemme solmussa B ja rentoutua vierailemattomille naapureilleen. Rentoutumisen jälkeen polku solmuun C jää 5 , kun taas polku solmuun JA tulee yksitoista , ja polku solmuun D tulee 13 .
8. Vierailemme nyt solmussa JA ja rentouttaa sen naapurisolmuja B, D , ja F . Koska vain solmu F on vierailematon, se on rento. Näin ollen polku solmuun B pysyy sellaisena kuin on, ts. 4 , polku solmuun D jää myös 13 , ja polku solmuun F tulee 14 (8 + 6) .
9. Nyt vierailemme solmussa D , ja ainoa solmu F tulee olemaan rento. Kuitenkin polku solmuun F säilyy ennallaan, ts. 14 .
10. Koska vain solmu F on jäljellä, vierailemme siinä, mutta emme suorita rentoutumista, koska kaikki sen viereiset solmut ovat jo käyty.
11. Kun kaikki kaavioiden solmut on käyty, ohjelma päättyy.

Näin ollen lopulliset polut, jotka päätimme, ovat:

 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) 

Pseudokoodi Dijkstran algoritmille

Ymmärrämme nyt pseudokoodin Dijkstran algoritmille.

• Meidän on pidettävä kirjaa jokaisen solmun polun etäisyydestä. Siksi voimme tallentaa kunkin solmun polun etäisyyden n-koon taulukkoon, jossa n on solmujen kokonaismäärä.
• Lisäksi haluamme noutaa lyhimmän polun ja sen pituuden. Tämän ongelman ratkaisemiseksi kartoitamme jokaisen solmun siihen solmuun, joka viimeksi päivitti polun pituuden.
• Kun algoritmi on valmis, voimme palauttaa kohdesolmun lähdesolmuun polun hakemiseksi.
• Voimme käyttää vähimmäisprioriteettijonoa hakeaksemme solmun, jolla on pienin polkuetäisyys, tehokkaasti.

Toteutetaan nyt yllä olevan kuvan pseudokoodi:

java-taulukko lajiteltu

Pseudokoodi:

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

Selitys:

Yllä olevaan koodinpätkään olemme sisällyttäneet stdio.h otsikkotiedosto määritteli kaksi vakioarvoa: INF = 9999 ja MAX = 10 . Olemme ilmoittaneet funktion prototyypin ja määritelleet sitten funktion Dijkstran algoritmille DijkstraAlgoritmi joka hyväksyy kolme argumenttia - solmuista koostuvan Graafin, kaavion solmujen lukumäärän ja lähdesolmun. Tämän toiminnon sisällä olemme määrittäneet joitain tietorakenteita, kuten 2D-matriisin, joka toimii algoritmin prioriteettijonona, taulukon solmujen välisen etäisyyden ylläpitämiseksi, taulukon edellisten solmujen tietueen ylläpitämiseksi, taulukon tallennettavaksi. vierailtujen solmujen tiedot ja jotkin kokonaislukumuuttujat minimietäisyyden arvon, laskurin, seuraavan solmun arvon ja muiden tallentamiseen. Käytimme sitten a sisäkkäinen for-silmukka iteroidaksesi Grafin solmujen läpi ja lisätäksesi ne prioriteettijonoon vastaavasti. Olemme jälleen käyttäneet for-silmukka iteroida läpi prioriteettijonon elementit lähdesolmusta alkaen ja päivittää niiden etäisyydet. Silmukan ulkopuolella olemme asettaneet lähdesolmun etäisyydeksi 0 ja merkitsi sen käydyksi vieraili_solmut[] joukko. Asetimme sitten laskurin arvon yhdeksi ja käytimme sillä aikaa silmukan iterointi solmujen lukumäärän läpi. Tämän silmukan sisällä olemme asettaneet arvon minimi_etäisyys kuten INF ja käytti for-silmukka päivittääksesi arvon minimi_etäisyys muuttuja, jonka vähimmäisarvo on alkaen a etäisyys[] joukko. Sitten iteroimme valitun solmun vierailemattomien naapurisolmujen läpi käyttämällä for-silmukka ja suoritti rentoutumista. Tulostimme sitten saadut tiedot Dijkstran algoritmilla lasketuista etäisyyksistä.

Vuonna pää Olemme määrittäneet ja ilmoittaneet kuvaajaa edustavat muuttujat, solmujen lukumäärän ja lähdesolmun. Viimeinkin olemme soittaneet DijkstraAlgoritmi() toimintoa välittämällä vaaditut parametrit.

Tämän seurauksena käyttäjille tulostetaan vaaditut lyhyimmat mahdolliset polut lähdesolmusta jokaiselle solmulle.

Dijkstran algoritmin koodi C++:ssa

Seuraava on Dijkstran algoritmin toteutus C++-ohjelmointikielellä:

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

Selitys:

Yllä olevaan koodinpätkään sisällytimme 'iostream' ja 'vektori' otsikkotiedostot ja määrittänyt vakioarvon muodossa MAX_INT = 10000000 . Käytimme sitten standardinimiavaruutta ja loimme prototyypin DijkstraAlgoritmi() toiminto. Sitten määritimme ohjelman päätoiminnon, jota olemme kutsuneet nimellä DijkstraAlgoritmi() toiminto. Sen jälkeen julistimme joitain luokkia pisteiden ja reunojen luomiseksi. Olemme myös prototyyppienneet lisää toimintoja löytääksemme lyhimmän mahdollisen polun lähdepisteestä kohdepisteeseen ja instantoineet Vertex- ja Edge-luokat. Sitten määritimme molemmat luokat luodaksemme graafin kärjet ja reunat. Olemme sitten määritelleet DijkstraAlgoritmi() toiminto luoda kaavio ja suorittaa erilaisia ​​toimintoja. Tämän funktion sisällä olemme ilmoittaneet joitain huippuja ja kulmia. Sitten asetimme graafin lähdepisteen ja kutsumme Dijkstra () toiminto löytää lyhimmän mahdollisen etäisyyden ja Tulosta_lyhyin_reitti_() toiminto tulostaa lyhimmän etäisyyden lähdepisteestä kärkeen 'F' . Olemme sitten määritelleet Dijkstra () funktio laskea kaikkien kärkien lyhyimmat mahdolliset etäisyydet lähdepisteestä. Olemme myös määrittäneet joitain muita funktioita, joilla etsitään lyhyimmän etäisyyden omaava kärkipiste, joka palauttaa kaikki jäljellä olevan kärjen vieressä olevat kärjet, palauttaa kahden yhdistetyn kärjen välisen etäisyyden, tarkistaa, onko valittu kärki graafissa, ja tulostaa lyhin mahdollinen polku lähdepisteestä kohdepisteeseen.

Tuloksena vaadittu lyhin polku kärjelle 'F' lähdesolmusta tulostetaan käyttäjille.

Dijkstran algoritmin koodi Javassa

Seuraava on Dijkstran algoritmin toteutus Java-ohjelmointikielellä:

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

Selitys:

Yllä olevassa koodinpätkässä olemme määritelleet julkisen luokan muodossa DijkstraAlgoritmi() . Tämän luokan sisällä olemme määrittäneet julkisen menetelmän muodossa dijkstraAlgoritmi() löytääksesi lyhimmän etäisyyden lähdepisteestä kohdepisteeseen. Tämän menetelmän sisällä olemme määrittäneet muuttujan solmujen määrän tallentamiseksi. Tämän jälkeen olemme määrittäneet Boolen taulukon vierailtuja pisteitä koskevien tietojen tallentamiseen ja kokonaislukutaulukon niiden vastaavien etäisyyksien tallentamiseen. Aluksi määritimme arvot molemmissa taulukoissa nimellä Väärä ja MAX_VALUE , vastaavasti. Olemme myös asettaneet lähdepisteen etäisyyden nollaksi ja käyttäneet for-silmukka päivittääksesi lähdepisteen ja kohdepisteiden välisen etäisyyden minimietäisyydellä. Tämän jälkeen olemme päivittäneet valitun kärjen naapuripisteiden etäisyydet relaksaatiolla ja tulostaneet jokaiselle kärkipisteelle lyhyimmät etäisyydet. Olemme sitten määritelleet menetelmän, jolla löydetään pienin etäisyys lähdepisteestä kohdepisteeseen. Sitten määritimme pääfunktion, jossa määritimme graafin kärjet ja instantoimme graafin DijkstraAlgoritmi() luokkaa. Lopuksi olemme soittaneet dijkstraAlgoritmi() menetelmä löytääksesi lyhimmän etäisyyden lähdepisteen ja kohdepisteiden välillä.

Tämän seurauksena käyttäjille tulostetaan vaaditut lyhyimmat mahdolliset polut lähdesolmusta jokaiselle solmulle.

Dijkstran algoritmin koodi Pythonissa

Seuraava on Dijkstran algoritmin toteutus Python-ohjelmointikielessä:

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

Lähtö

 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 

Selitys:

Yllä olevassa koodinpätkässä olemme tuoneet sys moduuli ja ilmoitti solmujen ja reunojen arvoista koostuvat listat. Olemme sitten määritelleet funktion muodossa vierailla() löytääksesi, missä solmussa käydään seuraavaksi. Löysimme sitten kaavion solmujen kokonaismäärän ja asetimme jokaisen solmun alkuetäisyydet. Tämän jälkeen olemme laskeneet vähimmäisetäisyyden lähdesolmusta kohdesolmuun, suorittaneet rentoutumisen naapurisolmuille ja päivittäneet luettelon etäisyydet. Sitten tulostimme nämä etäisyydet luettelosta käyttäjille.

Tämän seurauksena käyttäjille tulostetaan vaaditut lyhyimmat mahdolliset polut lähdesolmusta jokaiselle solmulle.

Dijkstran algoritmin aika ja tila monimutkaisuus

• Dijkstran algoritmin aika monimutkaisuus on O(E log V) , jossa E on reunojen lukumäärä ja V on kärkien lukumäärä.
• Dijkstran algoritmin avaruuskompleksisuus on O(V), missä V on pisteiden lukumäärä.

Dijkstran algoritmin edut ja haitat

Keskustelemme Dijkstran algoritmin eduista:

1. Yksi Dijkstran algoritmin käytön ensisijaisista eduista on, että sillä on lähes lineaarinen aika ja tila monimutkaisuus.
2. Voimme käyttää tätä algoritmia laskeaksemme lyhimmän polun yhdestä kärjestä kaikkiin muihin kärkipisteisiin ja yhdestä lähdepisteestä yhteen kohdepisteeseen pysäyttämällä algoritmin, kun saamme kohdepisteen lyhimmän etäisyyden.
3. Tämä algoritmi toimii vain suunnatuissa painotetuissa kaavioissa, ja tämän kaavion kaikkien reunojen ei tulisi olla negatiivisia.

Vaikka Dijkstran algoritmilla on useita etuja, sillä on myös joitain haittoja, kuten:

1. Dijkstran algoritmi suorittaa piilotutkimuksen, joka käyttää paljon aikaa prosessin aikana.
2. Tämä algoritmi on kyvytön käsittelemään negatiivisia reunoja.
3. Koska tämä algoritmi suuntaa asykliseen kuvaajaan, se ei voi laskea tarkkaa lyhintä polkua.
4. Se vaatii myös ylläpitoa pitääkseen kirjaa pisteistä, joissa on vieraillut.

Jotkut Dijkstran algoritmin sovellukset

Dijkstran algoritmissa on useita reaalimaailman sovelluksia, joista osa on mainittu alla:

Google Mapsin digitaaliset karttapalvelut:Olemme useaan otteeseen yrittäneet löytää etäisyyden Google Mapsista joko sijainnistamme lähimpään ensisijaiseen sijaintiin tai kaupungista toiseen, joka sisältää useita ne yhdistäviä reittejä/polkuja; sovelluksen on kuitenkin näytettävä vähimmäisetäisyys. Tämä on mahdollista vain, koska Dijkstran algoritmi auttaa sovellusta löytämään lyhimmän kahden tietyn sijainnin välillä polulla. Tarkastellaan USA:ta graafina, jossa kaupungit/paikat on esitetty pisteinä ja kahden kaupungin/paikan väliset reitit reunoina. Sitten Dijkstran algoritmin avulla voimme laskea lyhimmät reitit minkä tahansa kahden kaupungin/paikan välillä.Sosiaalisen verkostoitumisen sovellukset:Monissa sovelluksissa, kuten Facebookissa, Twitterissä, Instagramissa ja muissa, monet meistä ovat saattaneet huomata, että nämä sovellukset ehdottavat ystäväluetteloa, jonka tietty käyttäjä saattaa tuntea. Kuinka monet sosiaalisen median yritykset ottavat tämän tyyppisen ominaisuuden käyttöön tehokkaasti, erityisesti kun järjestelmällä on yli miljardi käyttäjää? Vastaus tähän kysymykseen on Dijkstran algoritmi. Dijkstran standardialgoritmia käytetään yleensä arvioimaan lyhin etäisyys käyttäjien välillä mitattuna yhteyksien tai keskinäisyyden kautta. Kun sosiaalinen verkostoituminen on hyvin pientä, se käyttää tavallista Dijkstran algoritmia joidenkin muiden ominaisuuksien lisäksi määrittääkseen lyhimmät polut. Kuitenkin, kun kuvaaja on paljon suurempi, standardialgoritmilla kestää useita sekunteja laskea, joten vaihtoehtona käytetään joitain kehittyneitä algoritmeja.Puhelinverkko:Kuten jotkut meistä saattavat tietää, puhelinverkossa jokaisella siirtolinjalla on kaistanleveys 'b'. Kaistanleveys on suurin taajuus, jota siirtolinja voi tukea. Yleensä, jos signaalin taajuus on korkeampi tietyllä linjalla, signaali pienenee kyseisellä linjalla. Kaistanleveys edustaa tiedon määrää, jonka linja voi lähettää. Tarkastellaan kaupunkia graafia, jossa kytkentäasemat on esitetty pisteillä, siirtolinjat reunoilla ja kaistanleveys 'b' on esitetty reunojen painolla. Siten, kuten voimme havaita, puhelinverkko voi myös kuulua lyhimmän matkan ongelman kategoriaan ja se voidaan ratkaista Dijkstran algoritmilla.Lento-ohjelma:Oletetaan, että henkilö tarvitsee ohjelmiston lennon aikataulun laatimiseen asiakkaille. Agentilla on pääsy tietokantaan, joka sisältää kaikki lennot ja lentokentät. Lennon numeron, lähtölentokentän ja määränpään lisäksi lennoilla on myös lähtö- ja saapumisajat. Siten agentit käyttävät Dijkstran algoritmia määrittääkseen aikaisimman saapumisajan valitulle kohteelle alkuperäiseltä lentokentältä ja annetun aloitusajan.IP-reititys avoimen lyhimmän polun löytämiseksi ensin:Open Shortest Path First (lyhennettynä OSPF) on linkkitilan reititysprotokolla, jota käytetään löytämään paras polku lähde- ja kohdereitittimen välillä oman Shortest Path First -protokollansa avulla. Dijkstran algoritmia hyödynnetään laajasti reitittimien vaatimissa reititysprotokollissa välitystaulukon päivittämiseksi. Algoritmi antaa lyhimmän kustannuspolun lähdereitittimestä muihin verkossa oleviin reitittimiin.Robottipolku:Nykyään on syntynyt droneja ja robotteja, joista osa toimii manuaalisesti ja osa automaattisesti. Automaattisesti toimivat droonit ja robotit, joita käytetään pakettien toimittamiseen tiettyyn paikkaan tai tiettyyn tehtävään, on konfiguroitu Dijkstran Algorithm-moduulilla siten, että aina kun lähde ja määränpää tiedetään, drooni ja robotti liikkuvat määrättyyn suuntaan. seuraamalla lyhintä reittiä pitäen pakettien toimittamiseen kuluvan ajan mahdollisimman pienenä.Nimeä tiedostopalvelin:Dijkstran algoritmia käytetään myös tiedostopalvelimen määrittämiseen lähiverkossa (LAN). Oletetaan, että tiedostojen siirtämiseen tietokoneelta toiselle tarvitaan ääretön aika. Käytämme Dijkstran algoritmia, jotta minimoidaan 'hyppyjen' määrä tiedostopalvelimelta jokaiseen toiseen verkon tietokoneeseen. Tämä algoritmi palauttaa lyhimmän polun verkkojen välillä, mikä johtaa minimimäärään hyppyjä.

Johtopäätös

• Yllä olevassa opetusohjelmassa olemme ensinnäkin ymmärtäneet Graphin peruskäsitteet sekä sen tyypit ja sovellukset.
• Sitten opimme Dijkstran algoritmista ja sen historiasta.
• Olemme myös ymmärtäneet Dijkstran algoritmin perustoiminnan esimerkin avulla.
• Sen jälkeen opimme kirjoittamaan koodia Dijkstran algoritmille Pseudocoden avulla.
• Tarkastelimme sen toteutusta ohjelmointikielillä, kuten C, C++, Java ja Python oikeilla tulosteilla ja selityksillä.
• Olemme myös ymmärtäneet Dijkstran algoritmin aika- ja avaruusmonimutkaisuuden.
• Lopuksi olemme keskustelleet Dijkstran algoritmin ja joidenkin sen tosielämän sovellusten eduista ja haitoista.