De volgende tutorial leert ons over het kortste padalgoritme van Dijkstra. We zullen de werking van Dijkstra's algoritme begrijpen met een stapsgewijze grafische uitleg.
We behandelen het volgende:
- Een kort overzicht van de fundamentele concepten van Graph
- Begrijp het gebruik van het algoritme van Dijkstra
- Begrijp de werking van het algoritme met een stapsgewijs voorbeeld
Dus laten we beginnen.
Een korte introductie tot grafieken
Grafieken zijn niet-lineaire datastructuren die de 'verbindingen' tussen de elementen vertegenwoordigen. Deze elementen staan bekend als de Hoekpunten , en de lijnen of bogen die twee willekeurige hoekpunten in de grafiek verbinden, staan bekend als de Randen . Formeel omvat een grafiek: een reeks hoekpunten (V) En een set randen (E) . De grafiek wordt aangegeven met G(V, E) .
Componenten van een grafiek
De volgende afbeelding toont een grafische weergave van een grafiek:
Figuur 1: Grafische weergave van een grafiek
In de bovenstaande afbeelding worden de hoekpunten/knooppunten aangegeven met gekleurde cirkels, en worden de randen aangegeven met de lijnen die de knooppunten verbinden.
Toepassingen van de grafieken
Grafieken worden gebruikt om veel problemen uit het echte leven op te lossen. Er wordt gebruik gemaakt van grafieken om de netwerken weer te geven. Deze netwerken kunnen telefoon- of circuitnetwerken of paden in een stad omvatten.
We zouden Grafieken bijvoorbeeld kunnen gebruiken om een transportnetwerkmodel te ontwerpen waarbij de hoekpunten de faciliteiten weergeven die de producten verzenden of ontvangen, en de randen wegen of paden vertegenwoordigen die ze verbinden. Het volgende is een grafische weergave hiervan:
Figuur 2: Grafische weergave van transportnetwerk
Grafieken worden ook gebruikt op verschillende sociale mediaplatforms zoals LinkedIn, Facebook, Twitter en meer. Platforms zoals Facebook gebruiken bijvoorbeeld grafieken om de gegevens van hun gebruikers op te slaan, waarbij elke persoon wordt aangegeven met een hoekpunt, en elk van hen is een structuur die informatie bevat zoals persoons-ID, naam, geslacht, adres, enz.
Soorten grafieken
De grafieken kunnen in twee typen worden onderverdeeld:
- Ongerichte grafiek
- Gerichte grafiek
Ongerichte grafiek: Een grafiek met randen die geen richting hebben, wordt een ongerichte grafiek genoemd. De randen van deze grafiek impliceren een tweerichtingsrelatie waarbij elke rand in beide richtingen kan worden doorlopen. De volgende afbeelding toont een eenvoudige, ongerichte grafiek met vier knooppunten en vijf randen.
Figuur 3: Een eenvoudige ongerichte grafiek
Gerichte grafiek: Een grafiek met randen met richting wordt een gerichte grafiek genoemd. De randen van deze grafiek impliceren een eenrichtingsrelatie waarbij elke rand slechts in één richting kan worden doorlopen. De volgende afbeelding toont een eenvoudige gerichte grafiek met vier knooppunten en vijf randen.
subtekenreeksfunctie java
Figuur 4: Een eenvoudig gerichte grafiek
De absolute lengte, positie of oriëntatie van de randen in een grafiekillustratie heeft doorgaans geen betekenis. Met andere woorden: we kunnen dezelfde grafiek op verschillende manieren visualiseren door de hoekpunten te herschikken of de randen te vervormen als de onderliggende structuur van de grafiek niet verandert.
Wat zijn gewogen grafieken?
Er wordt gezegd dat een grafiek gewogen is als aan elke rand een 'gewicht' wordt toegewezen. Het gewicht van een rand kan afstand, tijd of iets anders aanduiden dat de 'verbinding' tussen het paar hoekpunten die het verbindt, modelleert.
We kunnen bijvoorbeeld een blauw getal naast elke rand zien in de volgende afbeelding van de gewogen grafiek. Dit getal wordt gebruikt om het gewicht van de overeenkomstige rand aan te duiden.
Figuur 5: Een voorbeeld van een gewogen grafiek
Een inleiding tot het algoritme van Dijkstra
Nu we enkele basisconcepten van Graphs kennen, gaan we dieper in op het begrijpen van het concept van Dijkstra's algoritme.
Heeft u zich ooit afgevraagd hoe Google Maps de kortste en snelste route tussen twee plaatsen vindt?
Welnu, het antwoord is Het algoritme van Dijkstra . Het algoritme van Dijkstra is een Graph-algoritme die de kortste weg vindt van een bronhoekpunt naar alle andere hoekpunten in de grafiek (kortste pad van één bron). Het is een soort Greedy-algoritme dat alleen werkt op gewogen grafieken met positieve gewichten. De tijdscomplexiteit van Dijkstra's algoritme is O(V2) met behulp van de aangrenzende matrixweergave van de grafiek. Deze tijdcomplexiteit kan worden teruggebracht tot O((V + E) log V) met behulp van een aangrenzende lijstweergave van de grafiek, waar IN is het aantal hoekpunten en EN is het aantal randen in de grafiek.
Geschiedenis van Dijkstra's algoritme
Dijkstra's algoritme is ontworpen en uitgegeven door dr. Edsger W. Dijkstra , een Nederlandse computerwetenschapper, software-ingenieur, programmeur, wetenschapsessayist en systeemwetenschapper.
Tijdens een interview met Philip L. Frana voor de Communications of the ACM journal in 2001 onthulde Dr. Edsger W. Dijkstra:
'Wat is in het algemeen de kortste manier om van Rotterdam naar Groningen te reizen: van bepaalde stad naar bepaalde stad? Het is het algoritme voor het kortste pad, dat ik in ongeveer twintig minuten heb ontworpen. Op een ochtend was ik met mijn jonge verloofde aan het winkelen in Amsterdam, en moe gingen we op het caféterras zitten om een kop koffie te drinken en ik dacht er net over na of ik dit kon doen, en ik ontwierp toen het algoritme voor het kortste pad . Zoals ik al zei, het was een uitvinding van twintig minuten. Het werd zelfs in '59 gepubliceerd, drie jaar later. De publicatie is nog steeds leesbaar, ze is eigenlijk best aardig. Eén van de redenen dat het zo leuk is, is dat ik het zonder potlood en papier heb ontworpen. Later leerde ik dat een van de voordelen van ontwerpen zonder potlood en papier is dat je bijna alle vermijdbare complexiteiten moet vermijden. Uiteindelijk werd dat algoritme, tot mijn grote verbazing, een van de hoekstenen van mijn roem.'
Dijkstra dacht na over het kortste-padprobleem toen hij in 1956 als programmeur bij het Wiskundig Centrum in Amsterdam werkte om de mogelijkheden van een nieuwe computer, bekend als ARMAC, te illustreren. Zijn doel was om zowel een probleem als een oplossing (door de computer geproduceerd) te selecteren die mensen zonder computerachtergrond konden begrijpen. Hij ontwikkelde het kortste pad-algoritme en voerde dit later uit voor ARMAC voor een vaag verkorte transportkaart van 64 steden in Nederland (64 steden, dus 6 bits zouden voldoende zijn om het stadsnummer te coderen). Een jaar later kwam hij een ander probleem tegen van hardware-ingenieurs die de volgende computer van het instituut bedienden: minimaliseer de hoeveelheid draad die nodig is om de pinnen op het achterpaneel van de machine aan te sluiten. Als oplossing herontdekte hij het algoritme dat Prim's minimal spanning tree-algoritme werd genoemd en publiceerde het in 1959.
Grondbeginselen van Dijkstra's algoritme
Hieronder volgen de basisconcepten van Dijkstra's algoritme:
- Het algoritme van Dijkstra begint bij het knooppunt dat we selecteren (het bronknooppunt) en onderzoekt de grafiek om het kortste pad te vinden tussen dat knooppunt en alle andere knooppunten in de grafiek.
- Het algoritme houdt gegevens bij van de momenteel erkende kortste afstand van elk knooppunt tot het bronknooppunt, en werkt deze waarden bij als het een korter pad vindt.
- Zodra het algoritme het kortste pad tussen de bron en een ander knooppunt heeft gevonden, wordt dat knooppunt gemarkeerd als 'bezocht' en opgenomen in het pad.
- De procedure gaat door totdat alle knooppunten in de grafiek in het pad zijn opgenomen. Op deze manier hebben we een pad dat het bronknooppunt verbindt met alle andere knooppunten, waarbij we het kortst mogelijke pad volgen om elk knooppunt te bereiken.
De werking van het algoritme van Dijkstra begrijpen
A grafiek En bron hoekpunt zijn vereisten voor het algoritme van Dijkstra. Dit algoritme is gebaseerd op de Greedy Approach en vindt dus bij elke stap van het algoritme de lokaal optimale keuze (in dit geval lokale minima).
Python __dict__
Voor elk hoekpunt in dit algoritme zijn twee eigenschappen gedefinieerd:
- Bezocht pand
- Padeigenschap
Laten we deze eigenschappen in het kort begrijpen.
Bezocht pand:
- De eigenschap 'visited' geeft aan of het knooppunt al dan niet is bezocht.
- We gebruiken deze eigenschap zodat we geen enkel knooppunt opnieuw bezoeken.
- Een knooppunt wordt pas als bezocht gemarkeerd als het kortste pad is gevonden.
Padeigenschap:
- De eigenschap 'path' slaat de waarde op van het huidige minimale pad naar het knooppunt.
- Het huidige minimumpad impliceert de kortste manier waarop we dit knooppunt tot nu toe hebben bereikt.
- Deze eigenschap wordt herzien wanneer een buur van het knooppunt wordt bezocht.
- Deze eigenschap is belangrijk omdat hierdoor het definitieve antwoord voor elk knooppunt wordt opgeslagen.
In eerste instantie markeren we alle hoekpunten of knooppunten als niet bezocht, omdat ze nog moeten worden bezocht. Het pad naar alle knooppunten is ook ingesteld op oneindig, afgezien van het bronknooppunt. Bovendien wordt het pad naar het bronknooppunt ingesteld op nul (0).
Vervolgens selecteren we het bronknooppunt en markeren het als bezocht. Daarna hebben we toegang tot alle aangrenzende knooppunten van het bronknooppunt en voeren we ontspanning uit op elk knooppunt. Ontspanning is het proces waarbij de kosten voor het bereiken van een knooppunt worden verlaagd met behulp van een ander knooppunt.
Tijdens het ontspanningsproces wordt het pad van elk knooppunt herzien naar de minimumwaarde van het huidige pad van het knooppunt, de som van het pad naar het vorige knooppunt en het pad van het vorige knooppunt naar het huidige knooppunt.
Laten we veronderstellen dat p[n] de waarde is van het huidige pad voor knooppunt n, p[m] de waarde is van het pad naar het eerder bezochte knooppunt m, en w het gewicht is van de rand tussen het huidige knooppunt en eerder bezochte (randgewicht tussen n en m).
In wiskundige zin kan ontspanning worden geïllustreerd als:
p[n] = minimum(p[n], p[m] + w)
Vervolgens markeren we een niet-bezocht knooppunt met het minste pad zoals bezocht in elke volgende stap en werken we de paden van zijn buren bij.
We herhalen deze procedure totdat alle knooppunten in de grafiek als bezocht zijn gemarkeerd.
Telkens wanneer we een knooppunt aan de bezochte set toevoegen, verandert het pad naar alle aangrenzende knooppunten dienovereenkomstig.
Als een knooppunt onbereikbaar blijft (losgekoppelde component), blijft zijn pad 'oneindig'. Als de bron zelf een afzonderlijk onderdeel is, blijft het pad naar alle andere knooppunten 'oneindig'.
Het algoritme van Dijkstra begrijpen met een voorbeeld
Het volgende is de stap die we zullen volgen om het algoritme van Dijkstra te implementeren:
Stap 1: Eerst markeren we het bronknooppunt met een huidige afstand van 0 en stellen we de rest van de knooppunten in op INFINITY.
Stap 2: We zullen dan het niet-bezochte knooppunt met de kleinste huidige afstand instellen als het huidige knooppunt, stel dat X.
Stap 3: Voor elke buur N van het huidige knooppunt X: We zullen dan de huidige afstand van X optellen bij het gewicht van de rand die X-N verbindt. Als deze kleiner is dan de huidige afstand van N, stelt u deze in als de nieuwe huidige afstand van N.
succes
Stap 4: Vervolgens markeren we het huidige knooppunt X als bezocht.
Stap 5: We zullen het proces herhalen vanaf 'Stap 2' als er een knooppunt in de grafiek nog niet bezocht is.
Laten we nu de implementatie van het algoritme begrijpen met behulp van een voorbeeld:
Figuur 6: De gegeven grafiek
niet gelijk aan mysql
- We zullen de bovenstaande grafiek als invoer gebruiken, met node A als bron.
- Eerst zullen we alle knooppunten als niet-bezocht markeren.
- Wij zullen het pad bepalen 0 bij knooppunt A En ONEINDIGHEID voor alle andere knooppunten.
- We zullen nu het bronknooppunt markeren A zoals bezocht en toegang krijgen tot de aangrenzende knooppunten.
Opmerking: We hebben alleen toegang gekregen tot de aangrenzende knooppunten, niet bezocht. - We zullen nu het pad naar het knooppunt bijwerken B door 4 met behulp van ontspanning omdat het pad naar het knooppunt gaat A is 0 en het pad vanaf het knooppunt A naar B is 4 , en de minimum((0 + 4), ONEINDIGHEID) is 4 .
- We zullen ook het pad naar het knooppunt bijwerken C door 5 met behulp van ontspanning omdat het pad naar het knooppunt gaat A is 0 en het pad vanaf het knooppunt A naar C is 5 , en de minimum((0 + 5), ONEINDIGHEID) is 5 . Beide buren van knooppunt A zijn nu ontspannen; daarom kunnen we verder.
- We zullen nu het volgende niet-bezochte knooppunt met het minste pad selecteren en dit bezoeken. Daarom zullen we knooppunt bezoeken B en ontspanning uitvoeren op zijn onbezochte buren. Na het uitvoeren van ontspanning, het pad naar het knooppunt C zal blijven 5 , terwijl het pad naar node EN zal worden elf en het pad naar het knooppunt D zal worden 13 .
- We gaan nu naar node EN en ontspanning uitvoeren op de aangrenzende knooppunten B, D , En F . Aangezien alleen knooppunt F onbezocht is, zal het ontspannen zijn. Dus het pad naar het knooppunt B zal blijven zoals het is, d.w.z. 4 , het pad naar het knooppunt D zal ook blijven 13 en het pad naar het knooppunt F zal worden 14 (8 + 6) .
- Nu gaan we node bezoeken D , en alleen knooppunt F zal ontspannen zijn. Het pad naar node F zal onveranderd blijven, d.w.z. 14 .
- Aangezien alleen knooppunt F overblijft, zullen we het bezoeken, maar geen enkele ontspanning uitvoeren omdat alle aangrenzende knooppunten al zijn bezocht.
- Zodra alle knooppunten van de grafieken zijn bezocht, eindigt het programma.
Daarom zijn de uiteindelijke paden die we hebben geconcludeerd:
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)
Pseudocode voor Dijkstra's algoritme
We zullen nu een pseudocode voor Dijkstra's algoritme begrijpen.
- We moeten de padafstand van elk knooppunt bijhouden. Daarom kunnen we de padafstand van elk knooppunt opslaan in een array van grootte n, waarbij n het totale aantal knooppunten is.
- Bovendien willen we het kortste pad en de lengte van dat pad achterhalen. Om dit probleem te verhelpen, zullen we elk knooppunt toewijzen aan het knooppunt waarvan de padlengte het laatst is bijgewerkt.
- Zodra het algoritme voltooid is, kunnen we het bestemmingsknooppunt terugvoeren naar het bronknooppunt om het pad op te halen.
- We kunnen een minimale prioriteitswachtrij gebruiken om op een efficiënte manier het knooppunt met de kleinste padafstand op te halen.
Laten we nu een pseudocode van de bovenstaande illustratie implementeren:
Pseudocode:
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's Algorithm in Different Programming Languages</h2> <p>Now that we have successfully understood the pseudocode of Dijkstra's Algorithm, it is time to see its implementation in different programming languages like C, C++, Java, and Python.</p> <h3>Code for Dijkstra's Algorithm in C</h3> <p>The following is the implementation of Dijkstra's Algorithm in the C Programming Language:</p> <p> <strong>File: DijkstraAlgorithm.c</strong> </p> <pre> // Implementation of Dijkstra'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'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'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'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's Algorithm in C++</h3> <p>The following is the implementation of Dijkstra's Algorithm in the C++ Programming Language:</p> <p> <strong>File: DijkstraAlgorithm.cpp</strong> </p> <pre> // Implementation of Dijkstra'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& vertices); int Distance(Vertex* vertexOne, Vertex* vertexTwo); bool Contains(vector& 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('A'); Vertex* vertex_b = new Vertex('B'); Vertex* vertex_c = new Vertex('C'); Vertex* vertex_d = new Vertex('D'); Vertex* vertex_e = new Vertex('E'); Vertex* vertex_f = new Vertex('F'); Vertex* vertex_g = new Vertex('G'); // 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 -> 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's Algorithm void Dijkstra() { while (vertices.size() > 0) { Vertex* smallest = Extract_Smallest(vertices); vector* adjacent_nodes = Adjacent_Remaining_Nodes(smallest); const int size = adjacent_nodes -> size(); for (int i = 0; i at(i); int distance = Distance(smallest, adjacent) + smallest -> distance_from_start; if (distance distance_from_start) { adjacent -> distance_from_start = distance; adjacent -> 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& 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 'vertex' which are still in the 'vertices' 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 -> vertexTwo; } else if (edge -> vertexTwo == vertex) { adjacent = edge -> vertexOne; } if (adjacent && Contains(vertices, adjacent)) { adjacent_nodes -> 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 -> distance; } } return -1; // should never happen } // defining the function to check if the 'vertices' vector contains 'vertex' bool Contains(vector& 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>'iostream'</strong> and <strong>'vector'</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>'F'</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>'F'</strong> from the source node is printed for the users.</p> <h3>Code for Dijkstra's Algorithm in Java</h3> <p>The following is the implementation of Dijkstra's Algorithm in the Java Programming Language:</p> <p> <strong>File: DijkstraAlgorithm.java</strong> </p> <pre> // Implementation of Dijkstra's Algorithm in Java // defining the public class for Dijkstra's Algorithm public class DijkstraAlgorithm { // defining the method to implement Dijkstra'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's Algorithm in Python</h3> <p>The following is the implementation of Dijkstra's Algorithm in the Python Programming Language:</p> <p> <strong>File: DikstraAlgorithm.py</strong> </p> <pre> # Implementation of Dijkstra'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('Distance of', chr(ord('A') + i), 'from source node:', 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's Algorithm</h2> <ul> <li>The Time Complexity of Dijkstra'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's Algorithm is O(V), where V is the number of vertices.</li> </ul> <h2>Advantages and Disadvantages of Dijkstra's Algorithm</h2> <p> <strong>Let us discuss some advantages of Dijkstra's Algorithm:</strong> </p> <ol class="points"> <li>One primary advantage of using Dijkstra'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's algorithm has some disadvantages also, such as:</strong> </p> <ol class="points"> <li>Dijkstra'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's Algorithm</h2> <p> <strong>Dijkstra'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'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'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's Algorithm. The standard Dijkstra'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'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, 'b'. 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, 'b', 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'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'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'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'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'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 'hops' from the file server to every other computer on the network, we will use Dijkstra'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's Algorithm and its history.</li> <li>We have also understood the fundamental working of Dijkstra's Algorithm with the help of an example.</li> <li>After that, we studied how to write code for Dijkstra'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's Algorithm.</li> <li>Finally, we have discussed the advantages and disadvantages of Dijkstra's algorithm and some of its real-life applications.</li> </ul> <hr></nodes;></pre></size;></pre></size;></pre></distance[n]> Uitleg:
In het bovenstaande codefragment hebben we de stdio.h header-bestand definieerde twee constante waarden: INF = 9999 En MAX = 10 . We hebben de prototyping van de functie verklaard en vervolgens de functie voor Dijkstra's algoritme gedefinieerd als DijkstraAlgorithm die drie argumenten accepteert: de grafiek bestaande uit de knooppunten, het aantal knooppunten in de grafiek en het bronknooppunt. Binnen deze functie hebben we enkele datastructuren gedefinieerd, zoals een 2D-matrix die zal werken als de Prioriteitswachtrij voor het algoritme, een array om de afstand tussen de knooppunten te bepalen, een array om het record van eerdere knooppunten bij te houden, een array om op te slaan de bezochte knooppuntinformatie en enkele gehele variabelen om de minimale afstandswaarde, teller, volgende knooppuntwaarde en meer op te slaan. Wij hebben toen gebruik gemaakt van een geneste for-lus om de knooppunten van de grafiek te doorlopen en ze dienovereenkomstig aan de prioriteitswachtrij toe te voegen. We hebben opnieuw gebruik gemaakt van de for loop om de elementen in de prioriteitswachtrij te doorlopen, beginnend bij het bronknooppunt, en hun afstanden bij te werken. Buiten de lus hebben we de afstand van het bronknooppunt ingesteld op 0 en markeerde het als bezocht in de bezochte_nodes[] reeks. Vervolgens hebben we de tellerwaarde ingesteld op één en de terwijl lus itereert door het aantal knooppunten. Binnen deze lus hebben we de waarde van ingesteld minimale_afstand als INF en gebruikte de for loop om de waarde van de bij te werken minimale_afstand variabele met de minimumwaarde van a afstand[] reeks. Vervolgens hebben we de niet-bezochte aangrenzende knooppunten van het geselecteerde knooppunt doorlopen met behulp van de for loop en ontspanning uitgevoerd. Vervolgens hebben we de resulterende gegevens van de afstanden afgedrukt die zijn berekend met behulp van het algoritme van Dijkstra.
In de voornaamst functie hebben we de variabelen gedefinieerd en gedeclareerd die de grafiek, het aantal knooppunten en het bronknooppunt vertegenwoordigen. Eindelijk hebben we gebeld met de DijkstraAlgorithm() functioneren door de vereiste parameters door te geven.
Hierdoor worden voor elk knooppunt vanaf het bronknooppunt de vereiste kortst mogelijke paden voor de gebruikers afgedrukt.
Code voor het algoritme van Dijkstra in C++
Het volgende is de implementatie van het algoritme van Dijkstra in de programmeertaal C++:
Bestand: DijkstraAlgorithm.cpp
// Implementation of Dijkstra'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& vertices); int Distance(Vertex* vertexOne, Vertex* vertexTwo); bool Contains(vector& 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('A'); Vertex* vertex_b = new Vertex('B'); Vertex* vertex_c = new Vertex('C'); Vertex* vertex_d = new Vertex('D'); Vertex* vertex_e = new Vertex('E'); Vertex* vertex_f = new Vertex('F'); Vertex* vertex_g = new Vertex('G'); // 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 -> 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's Algorithm void Dijkstra() { while (vertices.size() > 0) { Vertex* smallest = Extract_Smallest(vertices); vector* adjacent_nodes = Adjacent_Remaining_Nodes(smallest); const int size = adjacent_nodes -> size(); for (int i = 0; i at(i); int distance = Distance(smallest, adjacent) + smallest -> distance_from_start; if (distance distance_from_start) { adjacent -> distance_from_start = distance; adjacent -> 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& 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 'vertex' which are still in the 'vertices' 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 -> vertexTwo; } else if (edge -> vertexTwo == vertex) { adjacent = edge -> vertexOne; } if (adjacent && Contains(vertices, adjacent)) { adjacent_nodes -> 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 -> distance; } } return -1; // should never happen } // defining the function to check if the 'vertices' vector contains 'vertex' bool Contains(vector& 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>'iostream'</strong> and <strong>'vector'</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>'F'</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>'F'</strong> from the source node is printed for the users.</p> <h3>Code for Dijkstra's Algorithm in Java</h3> <p>The following is the implementation of Dijkstra's Algorithm in the Java Programming Language:</p> <p> <strong>File: DijkstraAlgorithm.java</strong> </p> <pre> // Implementation of Dijkstra's Algorithm in Java // defining the public class for Dijkstra's Algorithm public class DijkstraAlgorithm { // defining the method to implement Dijkstra'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's Algorithm in Python</h3> <p>The following is the implementation of Dijkstra's Algorithm in the Python Programming Language:</p> <p> <strong>File: DikstraAlgorithm.py</strong> </p> <pre> # Implementation of Dijkstra'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('Distance of', chr(ord('A') + i), 'from source node:', 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's Algorithm</h2> <ul> <li>The Time Complexity of Dijkstra'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's Algorithm is O(V), where V is the number of vertices.</li> </ul> <h2>Advantages and Disadvantages of Dijkstra's Algorithm</h2> <p> <strong>Let us discuss some advantages of Dijkstra's Algorithm:</strong> </p> <ol class="points"> <li>One primary advantage of using Dijkstra'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's algorithm has some disadvantages also, such as:</strong> </p> <ol class="points"> <li>Dijkstra'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's Algorithm</h2> <p> <strong>Dijkstra'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'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'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's Algorithm. The standard Dijkstra'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'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, 'b'. 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, 'b', 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'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'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'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'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'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 'hops' from the file server to every other computer on the network, we will use Dijkstra'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's Algorithm and its history.</li> <li>We have also understood the fundamental working of Dijkstra's Algorithm with the help of an example.</li> <li>After that, we studied how to write code for Dijkstra'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's Algorithm.</li> <li>Finally, we have discussed the advantages and disadvantages of Dijkstra's algorithm and some of its real-life applications.</li> </ul> <hr></nodes;></pre></size;> Uitleg:
In het bovenstaande codefragment hebben we de 'iostream' En 'vector' header-bestanden en definieerde een constante waarde als MAX_INT = 10000000 . Vervolgens hebben we de standaardnaamruimte gebruikt en een prototype gemaakt van de DijkstraAlgorithm() functie. Vervolgens hebben we de hoofdfunctie van het programma gedefinieerd, die we de DijkstraAlgorithm() functie. Daarna hebben we enkele klassen gedeclareerd om hoekpunten en randen te maken. We hebben ook meer functies geprototypeerd om het kortst mogelijke pad van het bronpunt naar het bestemmingspunt te vinden en de klassen Vertex en Edge geïnstantieerd. Vervolgens hebben we beide klassen gedefinieerd om de hoekpunten en randen van de grafiek te creëren. Vervolgens hebben we de definitie gedefinieerd DijkstraAlgorithm() functie om een grafiek te maken en verschillende bewerkingen uit te voeren. Binnen deze functie hebben we enkele hoekpunten en randen gedeclareerd. Vervolgens hebben we het bronpunt van de grafiek ingesteld en de Dijkstra() functie om de kortst mogelijke afstand te vinden en Print_Shortest_Route_To() functie om de kortste afstand van het bronpunt tot het hoekpunt af te drukken 'F' . Vervolgens hebben we de definitie gedefinieerd Dijkstra() functie om de kortst mogelijke afstanden van alle hoekpunten tot het bronpunt te berekenen. We hebben ook nog enkele functies gedefinieerd om het hoekpunt met de kortste afstand te vinden, om alle hoekpunten te retourneren die aan het resterende hoekpunt grenzen, om de afstand tussen twee verbonden hoekpunten terug te geven, om te controleren of het geselecteerde hoekpunt in de grafiek voorkomt, en om de het kortst mogelijke pad van het bronpunt naar het doelpunt.
Het resultaat is het vereiste kortste pad voor het hoekpunt 'F' van het bronknooppunt wordt afgedrukt voor de gebruikers.
Code voor het algoritme van Dijkstra in Java
Het volgende is de implementatie van Dijkstra's algoritme in de Java-programmeertaal:
Bestand: DijkstraAlgorithm.java
// Implementation of Dijkstra's Algorithm in Java // defining the public class for Dijkstra's Algorithm public class DijkstraAlgorithm { // defining the method to implement Dijkstra'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's Algorithm in Python</h3> <p>The following is the implementation of Dijkstra's Algorithm in the Python Programming Language:</p> <p> <strong>File: DikstraAlgorithm.py</strong> </p> <pre> # Implementation of Dijkstra'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('Distance of', chr(ord('A') + i), 'from source node:', 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's Algorithm</h2> <ul> <li>The Time Complexity of Dijkstra'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's Algorithm is O(V), where V is the number of vertices.</li> </ul> <h2>Advantages and Disadvantages of Dijkstra's Algorithm</h2> <p> <strong>Let us discuss some advantages of Dijkstra's Algorithm:</strong> </p> <ol class="points"> <li>One primary advantage of using Dijkstra'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's algorithm has some disadvantages also, such as:</strong> </p> <ol class="points"> <li>Dijkstra'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's Algorithm</h2> <p> <strong>Dijkstra'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'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'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's Algorithm. The standard Dijkstra'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'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, 'b'. 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, 'b', 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'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'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'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'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'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 'hops' from the file server to every other computer on the network, we will use Dijkstra'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's Algorithm and its history.</li> <li>We have also understood the fundamental working of Dijkstra's Algorithm with the help of an example.</li> <li>After that, we studied how to write code for Dijkstra'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's Algorithm.</li> <li>Finally, we have discussed the advantages and disadvantages of Dijkstra's algorithm and some of its real-life applications.</li> </ul> <hr></nodes;> Uitleg:
In het bovenstaande codefragment hebben we een openbare klasse gedefinieerd als DijkstraAlgorithm() . Binnen deze klasse hebben we een openbare methode gedefinieerd als dijkstraAlgorithm() om de kortste afstand van het bronpunt tot het bestemmingspunt te vinden. Binnen deze methode hebben we een variabele gedefinieerd om het aantal knooppunten op te slaan. Vervolgens hebben we een Booleaanse array gedefinieerd om de informatie over de bezochte hoekpunten op te slaan en een integer-array om hun respectievelijke afstanden op te slaan. In eerste instantie hebben we de waarden in zowel de arrays als Vals En MAXIMUM WAARDE respectievelijk. We hebben ook de afstand van het bronpunt op nul gezet en de for loop om de afstand tussen het bronhoekpunt en de bestemmingshoekpunten bij te werken met de minimale afstand. Vervolgens hebben we de afstanden van de aangrenzende hoekpunten van het geselecteerde hoekpunt bijgewerkt door relaxatie uit te voeren en de kortste afstanden voor elk hoekpunt afgedrukt. Vervolgens hebben we een methode gedefinieerd om de minimale afstand van het bronpunt tot het bestemmingspunt te vinden. Vervolgens hebben we de hoofdfunctie gedefinieerd, waarbij we de hoekpunten van de grafiek hebben gedeclareerd en de DijkstraAlgorithm() klas. Tenslotte hebben wij gebeld met de dijkstraAlgorithm() methode om de kortste afstand tussen het bronpunt en de bestemmingshoekpunten te vinden.
Hierdoor worden voor elk knooppunt vanaf het bronknooppunt de vereiste kortst mogelijke paden voor de gebruikers afgedrukt.
dynamisch programmeren
Code voor het algoritme van Dijkstra in Python
Het volgende is de implementatie van Dijkstra's algoritme in de programmeertaal Python:
Bestand: DikstraAlgorithm.py
# Implementation of Dijkstra'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('Distance of', chr(ord('A') + i), 'from source node:', distance[1]) i = i + 1 </0>
Uitvoer
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
Uitleg:
In het bovenstaande codefragment hebben we de sys module en verklaarde de lijsten bestaande uit de waarden voor de knooppunten en randen. We hebben vervolgens een functie gedefinieerd als bezocht worden() om te zien welk knooppunt als volgende wordt bezocht. Vervolgens hebben we het totale aantal knooppunten in de grafiek gevonden en de initiële afstanden voor elk knooppunt ingesteld. Vervolgens hebben we de minimale afstand van het bronknooppunt tot het bestemmingsknooppunt berekend, relaxatie uitgevoerd op aangrenzende knooppunten en de afstanden in de lijst bijgewerkt. Vervolgens hebben we die afstanden uit de lijst afgedrukt voor de gebruikers.
Hierdoor worden voor elk knooppunt vanaf het bronknooppunt de vereiste kortst mogelijke paden voor de gebruikers afgedrukt.
Tijd- en ruimtecomplexiteit van Dijkstra's algoritme
- De tijdscomplexiteit van Dijkstra's algoritme is O(E log V) , waarbij E het aantal randen is en V het aantal hoekpunten.
- De ruimtecomplexiteit van Dijkstra's algoritme is O(V), waarbij V het aantal hoekpunten is.
Voor- en nadelen van het algoritme van Dijkstra
Laten we enkele voordelen van Dijkstra's algoritme bespreken:
- Een belangrijk voordeel van het gebruik van Dijkstra's algoritme is dat het een bijna lineaire tijd- en ruimtecomplexiteit heeft.
- We kunnen dit algoritme gebruiken om het kortste pad te berekenen van een enkel hoekpunt naar alle andere hoekpunten en van een enkel bronpunt naar een enkel bestemmingspunt door het algoritme te stoppen zodra we de kortste afstand voor het bestemmingspunt hebben bereikt.
- Dit algoritme werkt alleen voor gerichte gewogen grafieken, en alle randen van deze grafiek mogen niet-negatief zijn.
Ondanks dat het meerdere voordelen heeft, heeft het algoritme van Dijkstra ook enkele nadelen, zoals:
- Het algoritme van Dijkstra voert een verborgen verkenning uit die tijdens het proces veel tijd in beslag neemt.
- Dit algoritme is niet in staat om negatieve randen te verwerken.
- Omdat dit algoritme naar de acyclische grafiek gaat, kan het niet het exacte kortste pad berekenen.
- Er is ook onderhoud nodig om de bezochte hoekpunten bij te houden.
Enkele toepassingen van het algoritme van Dijkstra
Het algoritme van Dijkstra heeft verschillende toepassingen in de echte wereld, waarvan er enkele hieronder worden vermeld:
De conclusie
- In de bovenstaande tutorial hebben we eerst de basisconcepten van Graph begrepen, samen met de typen en toepassingen ervan.
- Vervolgens leerden we over het algoritme van Dijkstra en de geschiedenis ervan.
- We hebben de fundamentele werking van Dijkstra's algoritme ook begrepen met behulp van een voorbeeld.
- Daarna hebben we bestudeerd hoe je met behulp van Pseudocode code kunt schrijven voor Dijkstra's algoritme.
- We hebben de implementatie ervan waargenomen in programmeertalen zoals C, C++, Java en Python met de juiste uitvoer en uitleg.
- We hebben ook de tijd- en ruimtecomplexiteit van Dijkstra's algoritme begrepen.
- Ten slotte hebben we de voor- en nadelen van Dijkstra's algoritme en enkele van de praktische toepassingen ervan besproken.