logo

TechCodeview

Dijkstras algoritms

Šī apmācība mums mācīs par Dijkstra īsākā ceļa algoritmu. Mēs sapratīsim Dijkstra algoritma darbību ar pakāpenisku grafisku skaidrojumu.

Mēs aptversim sekojošo:

  • Īss pārskats par grafa pamatjēdzieniem
  • Izprotiet Dijkstras algoritma izmantošanu
  • Izprotiet algoritma darbību, izmantojot soli pa solim piemēru

Tātad, sāksim.

Īss ievads grafikos

Grafiki ir nelineāras datu struktūras, kas attēlo “savienojumus” starp elementiem. Šie elementi ir pazīstami kā Virsotnes , un līnijas vai loki, kas savieno jebkuras divas grafa virsotnes, ir zināmas kā Malas . Formālāk grafiks ietver Virsotņu kopa (V) un malu komplekts (E) . Grafiku apzīmē ar G(V, E) .

Grafika sastāvdaļas

    Virsotnes:Virsotnes ir diagrammas pamatvienības, ko izmanto, lai attēlotu reālās dzīves objektus, personas vai entītijas. Dažreiz virsotnes sauc arī par mezgliem.Malas:Malas tiek uzzīmētas vai izmantotas, lai savienotu divas grafa virsotnes. Dažreiz malas sauc arī par lokiem.

Nākamajā attēlā parādīts diagrammas grafiskais attēlojums:

Dijkstra

1. attēls: Grafika grafiskais attēlojums

Iepriekš redzamajā attēlā virsotnes/mezgli ir apzīmēti ar krāsainiem apļiem, bet malas – ar līnijām, kas savieno mezglus.

Grafiku pielietojumi

Grafikus izmanto, lai atrisinātu daudzas reālās dzīves problēmas. Tīklu attēlošanai tiek izmantoti grafiki. Šie tīkli var ietvert telefona vai ķēdes tīklus vai ceļus pilsētā.

Piemēram, mēs varētu izmantot grafikus, lai izstrādātu transporta tīkla modeli, kurā virsotnēs ir attēlotas iekārtas, kas nosūta vai saņem produktus, un malas attēlo ceļus vai ceļus, kas tos savieno. Tālāk ir attēlots tas pats attēls:

Dijkstra

2. attēls: Transporta tīkla attēlu attēlojums

Grafikus izmanto arī dažādās sociālo mediju platformās, piemēram, LinkedIn, Facebook, Twitter un citās. Piemēram, tādas platformas kā Facebook izmanto grafikus, lai saglabātu savu lietotāju datus, kur katra persona ir norādīta ar virsotni, un katra no tām ir struktūra, kas satur tādu informāciju kā personas ID, vārds, dzimums, adrese utt.

java kaudze

Grafiku veidi

Grafikus var iedalīt divos veidos:

  1. Nevirzīts grafiks
  2. Režisēts grafiks

Nevirzīts grafiks: Grafiku ar malām, kurām nav virziena, sauc par nevirzītu grafiku. Šī grafika malas nozīmē divvirzienu attiecības, kurās katru malu var šķērsot abos virzienos. Nākamajā attēlā ir parādīts vienkāršs nevirzīts grafiks ar četriem mezgliem un piecām malām.

Dijkstra

3. attēls: Vienkāršs nevirzīts grafiks

Režisēts grafiks: Grafiku ar malām ar virzienu sauc par virzītu grafiku. Šī grafika malas norāda uz vienvirziena attiecību, kurā katru malu var šķērsot tikai vienā virzienā. Nākamajā attēlā ir parādīts vienkāršs virzīts grafiks ar četriem mezgliem un piecām malām.

Dijkstra

4. attēls: Vienkāršs virzīts grafiks

Grafika ilustrācijas malu absolūtajam garumam, novietojumam vai orientācijai raksturīgi nav nozīmes. Citiem vārdiem sakot, mēs varam vizualizēt vienu un to pašu grafiku dažādos veidos, pārkārtojot virsotnes vai izkropļojot malas, ja grafa pamatā esošā struktūra nemainās.

Kas ir svērtie grafiki?

Tiek uzskatīts, ka diagramma ir svērta, ja katrai malai ir piešķirts 'svars'. Malas svars var apzīmēt attālumu, laiku vai jebko, kas modelē “savienojumu” starp virsotņu pāriem, ko tā savieno.

Piemēram, mēs varam novērot zilu skaitli blakus katrai malai nākamajā svērtā grafika attēlā. Šis skaitlis tiek izmantots, lai apzīmētu atbilstošās malas svaru.

Dijkstra

5. attēls: Svērtā grafika piemērs

Ievads Dijkstras algoritmā

Tagad, kad mēs zinām dažus grafiku pamatjēdzienus, pievērsīsimies Dijkstras algoritma koncepcijas izpratnei.

Vai esat kādreiz domājis, kā Google Maps atrod īsāko un ātrāko maršrutu starp divām vietām?

Nu, atbilde ir Dijkstras algoritms . Dijkstras algoritms ir Graph algoritms kas atrod īsāko ceļu no avota virsotnes uz visām pārējām Graph virsotnēm (viena avota īsākais ceļš). Tas ir mantkārīgā algoritma veids, kas darbojas tikai svērtajos grafikos ar pozitīvu svaru. Dijkstras algoritma laika sarežģītība ir O(V2) ar grafa blakusesības matricas attēlojuma palīdzību. Šo laika sarežģītību var samazināt līdz O((V +E) log V) ar blakusesības saraksta palīdzību grafa attēlojums, kur IN ir virsotņu skaits un UN ir grafa malu skaits.

Dijkstras algoritma vēsture

Dijkstras algoritmu izstrādāja un publicēja Dr. Edsgers V. Dijkstra , Nīderlandes datorzinātnieks, programmatūras inženieris, programmētājs, zinātnes esejists un sistēmu zinātnieks.

Intervijas laikā ar Filipu L. Franu žurnāla ACM komunikācijām 2001. gadā Dr. Edsger W. Dijkstra atklāja:

'Kāds vispār ir īsākais ceļš, lai ceļotu no Roterdamas uz Groningenu: no dotās pilsētas uz doto pilsētu? Tas ir īsākā ceļa algoritms, kuru es izstrādāju apmēram divdesmit minūtēs. Kādu rītu es ar savu jauno līgavu iepirkos Amsterdamā un noguruši mēs apsēdāmies uz kafejnīcas terases, lai iedzertu tasi kafijas, un es tikai domāju, vai es to varētu izdarīt, un tad es izstrādāju algoritmu īsākajam ceļam. . Kā jau teicu, tas bija divdesmit minūšu izgudrojums. Faktiski tas tika publicēts '59, trīs gadus vēlāk. Izdevums joprojām ir lasāms, patiesībā tas ir diezgan jauki. Viens no iemesliem, kāpēc tas ir tik jauki, bija tas, ka es to izstrādāju bez zīmuļa un papīra. Vēlāk es uzzināju, ka viena no priekšrocībām, veidojot dizainu bez zīmuļa un papīra, ir tā, ka esat gandrīz spiests izvairīties no visām sarežģītībām, no kurām var izvairīties. Galu galā šis algoritms man par lielu izbrīnu kļuva par vienu no manas slavas stūrakmeņiem.

Dijkstra domāja par īsākā ceļa problēmu, strādājot par programmētāju matemātikas centrā Amsterdamā 1956. gadā, lai ilustrētu jauna datora, kas pazīstams kā ARMAC, iespējas. Viņa mērķis bija izvēlēties gan problēmu, gan risinājumu (ko rada dators), ko cilvēki bez datora fona varētu saprast. Viņš izstrādāja īsākā ceļa algoritmu un vēlāk to izpildīja ARMAC, lai iegūtu neskaidri saīsinātu 64 Nīderlandes pilsētu transporta karti (64 pilsētas, tāpēc pilsētas numura kodēšanai pietiktu ar 6 bitiem). Gadu vēlāk viņš saskārās ar citu problēmu, ko radīja aparatūras inženieri, kas apkalpo nākamo institūta datoru: samaziniet vadu daudzumu, kas nepieciešams, lai savienotu tapas iekārtas aizmugurējā panelī. Kā risinājumu viņš atkārtoti atklāja algoritmu, ko sauc par Prima minimālā aptverošā koka algoritmu, un publicēja to 1959. gadā.

Dijkstras algoritma pamati

Tālāk ir norādīti Dijkstras algoritma pamatjēdzieni:

  1. Dijkstras algoritms sākas mūsu izvēlētajā mezglā (avota mezglā), un tas pārbauda grafiku, lai atrastu īsāko ceļu starp šo mezglu un visiem pārējiem diagrammas mezgliem.
  2. Algoritms glabā ierakstus par pašlaik atzīto īsāko attālumu no katra mezgla līdz avota mezglam un atjaunina šīs vērtības, ja atrod kādu īsāku ceļu.
  3. Kad algoritms ir izguvis īsāko ceļu starp avotu un citu mezglu, šis mezgls tiek atzīmēts kā “apmeklēts” un iekļauts ceļā.
  4. Procedūra turpinās, līdz visi diagrammas mezgli ir iekļauti ceļā. Tādā veidā mums ir ceļš, kas savieno avota mezglu ar visiem pārējiem mezgliem, izmantojot īsāko iespējamo ceļu, lai sasniegtu katru mezglu.

Izpratne par Dijkstras algoritma darbību

A grafikā un avota virsotne ir prasības Dijkstra algoritmam. Šis algoritms ir izveidots, izmantojot alkatīgo pieeju, un tādējādi katrā algoritma solī atrod lokāli optimālo izvēli (šajā gadījumā lokālos minimumus).

Katrai virsotnei šajā algoritmā būs definētas divas īpašības:

  1. Apmeklēts īpašums
  2. Ceļa īpašums

Ļaujiet mums īsi izprast šīs īpašības.

Apmeklētais īpašums:

  1. Rekvizīts “apmeklēts” norāda, vai mezgls ir vai nav apmeklēts.
  2. Mēs izmantojam šo īpašumu, lai mēs atkārtoti neapmeklētu nevienu mezglu.
  3. Mezgls tiek atzīmēts kā apmeklēts tikai tad, kad ir atrasts īsākais ceļš.

Ceļa īpašums:

  1. Rekvizīts “Ceļš” saglabā pašreizējā minimālā ceļa vērtību uz mezglu.
  2. Pašreizējais minimālais ceļš nozīmē īsāko ceļu, pa kuru līdz šim esam sasnieguši šo mezglu.
  3. Šis rekvizīts tiek pārskatīts, kad tiek apmeklēts kāds mezgla kaimiņš.
  4. Šis īpašums ir nozīmīgs, jo tajā tiks saglabāta katra mezgla galīgā atbilde.

Sākotnēji mēs atzīmējam visas virsotnes jeb mezglus kā neapmeklētus, jo tie vēl ir jāapmeklē. Ceļš uz visiem mezgliem arī ir iestatīts uz bezgalību neatkarīgi no avota mezgla. Turklāt ceļš uz avota mezglu ir iestatīts uz nulli (0).

Pēc tam mēs atlasām avota mezglu un atzīmējam to kā apmeklētu. Pēc tam mēs piekļūstam visiem blakus esošajiem avota mezgla mezgliem un veicam relaksāciju katrā mezglā. Relaksācija ir process, kurā tiek samazinātas izmaksas par mezgla sasniegšanu ar cita mezgla palīdzību.

Relaksācijas procesā katra mezgla ceļš tiek pārskatīts līdz minimālajai vērtībai starp mezgla pašreizējo ceļu, ceļa summu uz iepriekšējo mezglu un ceļu no iepriekšējā mezgla uz pašreizējo mezglu.

Pieņemsim, ka p[n] ir pašreizējā ceļa vērtība mezglam n, p[m] ir ceļa vērtība līdz iepriekš apmeklētajam mezglam m, un w ir malas svars starp pašreizējo mezglu un iepriekš apmeklēts (malas svars starp n un m).

Matemātiskā nozīmē relaksāciju var raksturot kā:

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

Pēc tam katrā nākamajā darbībā atzīmējam neapmeklētu mezglu ar vismazāko ceļu kā apmeklētu un atjauninām tā kaimiņa ceļus.

Mēs atkārtojam šo procedūru, līdz visi diagrammas mezgli ir atzīmēti kā apmeklēti.

Ikreiz, kad mēs pievienojam mezglu apmeklētajai kopai, attiecīgi mainās arī ceļš uz visiem blakus esošajiem mezgliem.

Ja kāds mezgls tiek atstāts nesasniedzams (atvienots komponents), tā ceļš paliek “bezgalība”. Ja pats avots ir atsevišķs komponents, tad ceļš uz visiem pārējiem mezgliem paliek “bezgalība”.

Izpratne par Dijkstras algoritmu ar piemēru

Tālāk ir norādīts solis, ko mēs izpildīsim, lai ieviestu Dijkstra algoritmu:

1. darbība: Pirmkārt, mēs atzīmēsim avota mezglu ar pašreizējo attālumu 0 un iestatīsim pārējos mezglus uz BEIGUS.

2. darbība: Pēc tam mēs iestatīsim neapmeklēto mezglu ar mazāko pašreizējo attālumu kā pašreizējo mezglu, pieņemsim, ka X.

3. darbība: Katram pašreizējā mezgla X kaimiņam N: mēs pievienosim pašreizējo attālumu X ar malas svaru, kas savieno X-N. Ja tas ir mazāks par pašreizējo attālumu N, iestatiet to kā jauno pašreizējo attālumu N.

4. darbība: Pēc tam mēs atzīmēsim pašreizējo mezglu X kā apmeklētu.

5. darbība: Mēs atkārtosim procesu no “2. darbība” ja grafikā ir palicis kāds neapmeklēts mezgls.

Tagad sapratīsim algoritma ieviešanu, izmantojot piemēru:

Dijkstra

6. attēls: Dotais grafiks

  1. Mēs izmantosim iepriekš minēto grafiku kā ievadi ar mezglu A kā avots.
  2. Pirmkārt, mēs atzīmēsim visus mezglus kā neapmeklētus.
  3. Mēs noteiksim ceļu uz 0 mezglā A un BEZGALĪBA visiem pārējiem mezgliem.
  4. Tagad mēs atzīmēsim avota mezglu A kā apmeklēts un piekļūt blakus esošajiem mezgliem.
    Piezīme: Mēs esam tikai piekļuvuši blakus esošajiem mezgliem, nevis tos apmeklējuši.
  5. Tagad mēs atjaunināsim ceļu uz mezglu B autors 4 ar relaksācijas palīdzību, jo ceļš uz mezglu A ir 0 un ceļš no mezgla A uz B ir 4 , un minimums ((0 + 4), BEZGALĪBAS) ir 4 .
  6. Mēs arī atjaunināsim ceļu uz mezglu C autors 5 ar relaksācijas palīdzību, jo ceļš uz mezglu A ir 0 un ceļš no mezgla A uz C ir 5 , un minimums ((0 + 5), BEZGALĪBAS) ir 5 . Abi mezgla kaimiņi A tagad ir atviegloti; tāpēc mēs varam virzīties uz priekšu.
  7. Tagad mēs atlasīsim nākamo neapmeklēto mezglu ar vismazāko ceļu un apmeklēsim to. Tāpēc mēs apmeklēsim mezglu B un veic relaksāciju saviem neapmeklētajiem kaimiņiem. Pēc relaksācijas veikšanas ceļš uz mezglu C paliks 5 , savukārt ceļš uz mezglu UN kļūs vienpadsmit un ceļš uz mezglu D kļūs 13 .
  8. Tagad mēs apmeklēsim mezglu UN un veic relaksāciju blakus esošajos mezglos B, D , un F . Tā kā tikai mezgls F ir neapmeklēts, tas būs atvieglots. Tādējādi ceļš uz mezglu B paliks kā ir, t.i., 4 , ceļš uz mezglu D arī paliks 13 un ceļš uz mezglu F kļūs 14 (8 + 6) .
  9. Tagad mēs apmeklēsim mezglu D , un vienīgais mezgls F būs atslābināts. Tomēr ceļš uz mezglu F paliks nemainīgs, t.i., 14 .
  10. Tā kā tikai mezgls F ir palicis, mēs to apmeklēsim, bet neveicam nekādu relaksāciju, jo visi blakus esošie mezgli jau ir apmeklēti.
  11. Kad visi diagrammu mezgli ir apmeklēti, programma beigsies.

Līdz ar to pēdējie ceļi, ko nonācām, ir: 

 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)

Dijkstras algoritma pseidokods

Tagad mēs sapratīsim Dijkstras algoritma pseidokodu.

  • Mums ir jāsaglabā katra mezgla ceļa attāluma ieraksts. Tāpēc mēs varam saglabāt katra mezgla ceļa attālumu n izmēra masīvā, kur n ir kopējais mezglu skaits.
  • Turklāt mēs vēlamies izgūt īsāko ceļu kopā ar šī ceļa garumu. Lai novērstu šo problēmu, mēs kartēsim katru mezglu ar mezglu, kas pēdējo reizi atjaunināja tā ceļa garumu.
  • Kad algoritms ir pabeigts, mēs varam novirzīt galamērķa mezglu uz avota mezglu, lai izgūtu ceļu.
  • Mēs varam izmantot minimālo prioritātes rindu, lai efektīvi izgūtu mezglu ar vismazāko ceļa attālumu.

Tagad ieviesīsim iepriekš minētās ilustrācijas pseidokodu:

Pseidokods: 

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

Paskaidrojums:

Iepriekš minētajā koda fragmentā esam iekļāvuši stdio.h galvenes fails definēja divas nemainīgas vērtības: INF = 9999 un MAX = 10 . Mēs esam deklarējuši funkcijas prototipu un pēc tam definējuši funkciju Dijkstras algoritmam kā DijkstraAlgoritms kas pieņem trīs argumentus — grafiku, kas sastāv no mezgliem, mezglu skaitu diagrammā un avota mezglu. Šajā funkcijā mēs esam definējuši dažas datu struktūras, piemēram, 2D matricu, kas darbosies kā algoritma prioritārā rinda, masīvu, kas nosaka attālumu starp mezgliem, masīvu iepriekšējo mezglu ieraksta uzturēšanai, masīvu saglabāšanai. informāciju par apmeklētajiem mezgliem un dažus veselus mainīgos lielumus, lai saglabātu minimālā attāluma vērtību, skaitītāju, nākamā mezgla vērtību un daudz ko citu. Pēc tam mēs izmantojām a ligzdots for-cilpa lai atkārtotu diagrammas mezglus un attiecīgi pievienotu tos prioritārajai rindai. Mēs atkal esam izmantojuši for-cilpa lai atkārtotu prioritārās rindas elementus, sākot no avota mezgla, un atjauninātu to attālumus. Ārpus cilpas esam iestatījuši avota mezgla attālumu kā 0 un atzīmēja to kā apmeklētu apmeklētie_mezgli[] masīvs. Pēc tam mēs iestatījām skaitītāja vērtību kā vienu un izmantojām kamēr cilpa atkārtojas, izmantojot mezglu skaitu. Šajā cilpā mēs esam iestatījuši vērtību minimālais_attālums kā INF un izmantoja for-cilpa lai atjauninātu vērtību minimālais_attālums mainīgais ar minimālo vērtību no a attālums[] masīvs. Pēc tam mēs atkārtojām atlasītā mezgla neapmeklētos blakus esošos mezglus, izmantojot for-cilpa un veica relaksāciju. Pēc tam mēs izdrukājām iegūtos attālumu datus, kas aprēķināti, izmantojot Dijkstra algoritmu.

Iekš galvenais funkciju, mēs esam definējuši un deklarējuši mainīgos lielumus, kas attēlo grafiku, mezglu skaitu un avota mezglu. Beidzot mēs esam piezvanījuši DijkstraAlgoritm() funkciju, nododot nepieciešamos parametrus.

Rezultātā lietotājiem tiek izdrukāti nepieciešamie īsākie iespējamie ceļi katram mezglam no avota mezgla.

Dijkstras algoritma kods C++ valodā

Tālāk ir norādīta Dijkstra algoritma ieviešana C++ programmēšanas valodā:

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

Paskaidrojums:

Iepriekš minētajā koda fragmentā mēs iekļāvām 'iostream' un 'vektors' galvenes failus un definēja konstantu vērtību kā MAX_INT = 10000000 . Pēc tam mēs izmantojām standarta nosaukumvietu un izveidojām prototipu DijkstraAlgoritm() funkciju. Pēc tam mēs definējām programmas galveno funkciju, ko mēs nosaucām par DijkstraAlgoritm() funkciju. Pēc tam mēs deklarējām dažas klases, lai izveidotu virsotnes un malas. Mēs esam arī izveidojuši vairāk funkciju prototipu, lai atrastu īsāko iespējamo ceļu no avota virsotnes līdz galamērķa virsotnei, kā arī iemiesojuši Vertex un Edge klases. Pēc tam mēs definējām abas klases, lai izveidotu grafika virsotnes un malas. Pēc tam mēs esam definējuši DijkstraAlgoritm() funkcija, lai izveidotu grafiku un veiktu dažādas darbības. Šīs funkcijas ietvaros mēs esam deklarējuši dažas virsotnes un malas. Pēc tam mēs iestatījām grafika avota virsotni un saucam par Dijkstra () funkcija, lai atrastu īsāko iespējamo attālumu un Drukāt_īsākais_maršruts_uz() funkcija, lai izdrukātu īsāko attālumu no avota virsotnes līdz virsotnei 'F' . Pēc tam mēs esam definējuši Dijkstra () funkcija, lai aprēķinātu visu virsotņu īsākos iespējamos attālumus no avota virsotnes. Mēs esam arī definējuši vēl dažas funkcijas, lai atrastu virsotni ar mazāko attālumu, lai atgrieztu visas virsotnes, kas atrodas blakus atlikušajai virsotnei, lai atgrieztu attālumu starp divām savienotām virsotnēm, pārbaudītu, vai izvēlētā virsotne pastāv grafikā, un izdrukātu īsākais iespējamais ceļš no avota virsotnes līdz galamērķa virsotnei.

Rezultātā virsotnei nepieciešamais īsākais ceļš 'F' no avota mezgla tiek izdrukāts lietotājiem.

Kods Dijkstra algoritmam Java valodā

Tālāk ir norādīta Dijkstra algoritma ieviešana Java programmēšanas valodā:

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

Paskaidrojums:

Iepriekš minētajā koda fragmentā mēs esam definējuši publisko klasi kā DijkstraAlgoritm() . Šajā klasē mēs esam definējuši publisko metodi kā dijkstraAlgoritm() lai atrastu īsāko attālumu no avota virsotnes līdz galamērķa virsotnei. Šīs metodes ietvaros mēs esam definējuši mainīgo, lai saglabātu mezglu skaitu. Pēc tam esam definējuši Būla masīvu, lai saglabātu informāciju par apmeklētajām virsotnēm, un veselu skaitļu masīvu, lai saglabātu to attiecīgos attālumus. Sākotnēji mēs deklarējām vērtības abos masīvos kā Nepatiesi un MAX_VALUE , attiecīgi. Mēs arī esam iestatījuši avota virsotnes attālumu uz nulli un izmantojām for-cilpa lai atjauninātu attālumu starp avota virsotnēm un galamērķa virsotnēm ar minimālo attālumu. Pēc tam mēs esam atjauninājuši atlasītās virsotnes blakus esošo virsotņu attālumus, veicot relaksāciju, un izdrukājām katras virsotnes īsākos attālumus. Pēc tam esam definējuši metodi, lai atrastu minimālo attālumu no avota virsotnes līdz galamērķa virsotnei. Pēc tam mēs definējām galveno funkciju, kurā mēs deklarējām grafa virsotnes un instantifikējām DijkstraAlgoritm() klasē. Visbeidzot, mēs esam piezvanījuši dijkstraAlgoritm() metode, lai atrastu īsāko attālumu starp avota virsotni un galamērķa virsotnēm.

Rezultātā lietotājiem tiek izdrukāti nepieciešamie īsākie iespējamie ceļi katram mezglam no avota mezgla.

Dijkstras algoritma kods Python

Tālāk ir norādīta Dijkstra algoritma ieviešana Python programmēšanas valodā:

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

Izvade 

 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

Paskaidrojums:

Iepriekš minētajā koda fragmentā mēs esam importējuši sys moduli un deklarēja sarakstus, kas sastāv no mezglu un malu vērtībām. Pēc tam mēs esam definējuši funkciju kā apmeklēt() lai atrastu, kurš mezgls tiks apmeklēts nākamais. Pēc tam mēs atradām kopējo mezglu skaitu grafikā un iestatījām sākotnējos attālumus katram mezglam. Pēc tam esam aprēķinājuši minimālo attālumu no avota mezgla līdz galamērķa mezglam, veikuši relaksāciju blakus esošajiem mezgliem un atjauninājuši attālumus sarakstā. Pēc tam mēs izdrukājām šos attālumus no saraksta lietotājiem.

Rezultātā lietotājiem tiek izdrukāti nepieciešamie īsākie iespējamie ceļi katram mezglam no avota mezgla.

Dijkstras algoritma laika un telpas sarežģītība

  • Dijkstras algoritma laika sarežģītība ir O(E log V) , kur E ir šķautņu skaits un V ir virsotņu skaits.
  • Dijkstras algoritma telpas sarežģītība ir O(V), kur V ir virsotņu skaits.

Dijkstras algoritma priekšrocības un trūkumi

Apspriedīsim dažas Dijkstras algoritma priekšrocības:

  1. Viena no galvenajām Dijkstra algoritma izmantošanas priekšrocībām ir tā, ka tam ir gandrīz lineāra laika un telpas sarežģītība.
  2. Mēs varam izmantot šo algoritmu, lai aprēķinātu īsāko ceļu no vienas virsotnes uz visām pārējām virsotnēm un vienu avota virsotni uz vienu galamērķa virsotni, apturot algoritmu, tiklīdz mēs iegūstam galamērķa virsotnes īsāko attālumu.
  3. Šis algoritms darbojas tikai virzītiem svērtiem grafikiem, un visām šī grafika malām jābūt nenegatīvām.

Lai gan Dijkstra algoritmam ir vairākas priekšrocības, tam ir arī daži trūkumi, piemēram:

  1. Dijkstras algoritms veic slēptu izpēti, kas procesa laikā patērē daudz laika.
  2. Šis algoritms nav spējīgs apstrādāt negatīvās malas.
  3. Tā kā šis algoritms virzās uz aciklisko grafiku, tas nevar aprēķināt precīzu īsāko ceļu.
  4. Tam nepieciešama arī apkope, lai reģistrētu apmeklētās virsotnes.

Daži Dijkstras algoritma pielietojumi

Dijkstras algoritmam ir dažādas reālās pasaules lietojumprogrammas, dažas no kurām ir norādītas tālāk:

    Digitālās kartēšanas pakalpojumi pakalpojumā Google Maps:Ir dažādi gadījumi, kad Google Maps esam mēģinājuši atrast attālumu vai nu no mūsu atrašanās vietas līdz tuvākajai vēlamajai vietai, vai no vienas pilsētas līdz citai, kurā ir vairāki maršruti/ceļi, kas tos savieno; tomēr lietojumprogrammā ir jāparāda minimālais attālums. Tas ir iespējams tikai tāpēc, ka Dijkstra algoritms palīdz lietojumprogrammai atrast īsāko starp divām norādītajām vietām ceļā. Apskatīsim ASV kā grafiku, kurā pilsētas/vietas ir attēlotas kā virsotnes, bet maršruti starp divām pilsētām/vietām ir attēloti kā malas. Pēc tam ar Dijkstra algoritma palīdzību mēs varam aprēķināt īsākos maršrutus starp jebkurām divām pilsētām/vietām.Sociālo tīklu lietojumprogrammas:Daudzās lietojumprogrammās, piemēram, Facebook, Twitter, Instagram un citās, daudzi no mums, iespējams, ir pamanījuši, ka šīs lietotnes piedāvā draugu sarakstu, kurus konkrēts lietotājs var zināt. Kā daudzi sociālo mediju uzņēmumi ievieš šāda veida funkcijas efektīvā un iedarbīgā veidā, jo īpaši, ja sistēmai ir vairāk nekā miljards lietotāju? Atbilde uz šo jautājumu ir Dijkstra algoritms. Standarta Dijkstra algoritms parasti tiek izmantots, lai novērtētu īsāko attālumu starp lietotājiem, ko mēra, izmantojot savienojumus vai savstarpējo savstarpējo attiecību starp lietotājiem. Ja sociālais tīkls ir ļoti mazs, tas izmanto standarta Dijkstra algoritmu papildus dažām citām funkcijām, lai noteiktu īsākos ceļus. Tomēr, ja grafiks ir daudz lielāks, standarta algoritma skaitīšana aizņem vairākas sekundes, un tādējādi kā alternatīva tiek izmantoti daži uzlaboti algoritmi.Tālruņa tīkls:Kā daži no mums varētu zināt, telefona tīklā katrai pārvades līnijai ir joslas platums “b”. Joslas platums ir augstākā frekvence, ko pārvades līnija var atbalstīt. Parasti, ja signāla frekvence ir augstāka noteiktā līnijā, signāls tiek samazināts par šo līniju. Joslas platums ir informācijas apjoms, ko var pārsūtīt pa līniju. Aplūkosim pilsētu kā grafiku, kurā komutācijas stacijas ir attēlotas, izmantojot virsotnes, pārvades līnijas ir attēlotas kā malas, un joslas platums 'b' ir attēlots, izmantojot malu svaru. Tādējādi, kā mēs varam novērot, tālruņu tīkls var ietilpt arī īsākā attāluma problēmas kategorijā un to var atrisināt, izmantojot Dijkstra algoritmu.Lidojuma programma:Pieņemsim, ka personai ir nepieciešama programmatūra, lai sagatavotu klientiem lidojumu dienas kārtību. Aģentam ir piekļuve datu bāzei ar visiem lidojumiem un lidostām. Papildus lidojuma numuram, sākuma lidostai un galamērķim lidojumiem ir arī izlidošanas un ielidošanas laiki. Tātad, lai noteiktu agrāko ierašanās laiku izvēlētajam galamērķim no sākotnējās lidostas un doto sākuma laiku, aģenti izmanto Dijkstra algoritmu.IP maršrutēšana, lai vispirms atrastu atvērto īsāko ceļu:Open Shortest Path First (saīsināti kā OSPF) ir saites stāvokļa maršrutēšanas protokols, ko izmanto, lai atrastu labāko ceļu starp avota un mērķa maršrutētāju, izmantojot savu Shortest Path First. Dijkstra algoritms tiek plaši izmantots maršrutēšanas protokolos, kas nepieciešami maršrutētājiem, lai atjauninātu to pārsūtīšanas tabulu. Algoritms nodrošina īsāko izmaksu ceļu no avota maršrutētāja līdz citiem tīklā esošajiem maršrutētājiem.Robotu ceļš:Mūsdienās ir radušies droni un roboti, daži darbojas manuāli un daži automātiski. Bezpilota lidaparāti un roboti, kas tiek darbināti automātiski un tiek izmantoti paku nogādāšanai noteiktā vietā vai tiek izmantoti jebkuram noteiktam uzdevumam, ir konfigurēti Dijkstra algoritma modulī tā, lai ikreiz, kad ir zināms avots un galamērķis, drons un robots pārvietotos pasūtītajā virzienā. ejot pa īsāko ceļu, līdz minimumam samazinot paku piegādes laiku.Norādiet failu serveri:Dijkstra algoritms tiek izmantots arī, lai norādītu failu serveri lokālajā tīklā (LAN). Pieņemsim, ka failu pārsūtīšanai no viena datora uz citu ir nepieciešams bezgalīgs laika periods. Tātad, lai samazinātu “apiņu” skaitu no failu servera uz katru otro tīkla datoru, mēs izmantosim Dijkstra algoritmu. Šis algoritms atgriezīs īsāko ceļu starp tīkliem, tādējādi nodrošinot minimālo apiņu skaitu.

Secinājums

  • Iepriekš minētajā apmācībā, pirmkārt, mēs esam sapratuši Graph pamatjēdzienus, kā arī tā veidus un lietojumus.
  • Pēc tam mēs uzzinājām par Dijkstras algoritmu un tā vēsturi.
  • Ar piemēra palīdzību esam sapratuši arī Dijkstras algoritma darbības pamatprincipus.
  • Pēc tam mēs pētījām, kā ar pseidokoda palīdzību uzrakstīt kodu Dijkstra algoritmam.
  • Mēs novērojām tā ieviešanu tādās programmēšanas valodās kā C, C++, Java un Python ar atbilstošiem rezultātiem un paskaidrojumiem.
  • Mēs esam sapratuši arī Dijkstras algoritma laika un telpas sarežģītību.
  • Visbeidzot, mēs esam apsprieduši Dijkstra algoritma priekšrocības un trūkumus un dažus tā reālās dzīves lietojumus.