Následující tutoriál nás naučí o Dijkstrově algoritmu nejkratší cesty. Fungování Dijkstrova algoritmu pochopíme pomocí postupného grafického vysvětlení.
Budeme pokrývat následující:
- Stručný přehled základních pojmů grafu
- Pochopte použití Dijkstrova algoritmu
- Pochopte fungování algoritmu pomocí příkladu krok za krokem
Takže, pojďme začít.
Stručný úvod do grafů
Grafy jsou nelineární datové struktury představující „spojení“ mezi prvky. Tyto prvky jsou známé jako Vrcholy , a čáry nebo oblouky, které spojují libovolné dva vrcholy v grafu, jsou známé jako Hrany . Formálněji graf obsahuje sada vrcholů (V) a sada hran (E) . Graf je označen G(V, E) .
Komponenty grafu
Následující obrázek ukazuje grafické znázornění grafu:
nedeterministické konečné automaty
Obrázek 1: Grafické znázornění grafu
Na obrázku výše jsou vrcholy/uzly označeny barevnými kruhy a hrany jsou označeny čarami spojujícími uzly.
Aplikace grafů
Grafy se používají k řešení mnoha reálných problémů. Pro znázornění sítí se používají grafy. Tyto sítě mohou zahrnovat telefonní nebo okruhové sítě nebo cesty ve městě.
Například bychom mohli použít grafy k návrhu modelu dopravní sítě, kde vrcholy zobrazují zařízení, která odesílají nebo přijímají produkty, a okraje představují silnice nebo cesty, které je spojují. Následuje obrázkové znázornění téhož:
Obrázek 2: Obrazové znázornění dopravní sítě
Grafy se také používají na různých platformách sociálních médií, jako je LinkedIn, Facebook, Twitter a další. Například platformy jako Facebook používají grafy k ukládání dat svých uživatelů, kde je každá osoba označena vrcholem a každá z nich je strukturou obsahující informace jako ID osoby, jméno, pohlaví, adresa atd.
Typy grafů
Grafy lze rozdělit do dvou typů:
- Neorientovaný graf
- Režírovaný graf
Neorientovaný graf: Graf s hranami, které nemají směr, se nazývá neorientovaný graf. Hrany tohoto grafu znamenají obousměrný vztah, ve kterém lze každou hranou procházet v obou směrech. Následující obrázek zobrazuje jednoduchý neorientovaný graf se čtyřmi uzly a pěti hranami.
Obrázek 3: Jednoduchý neorientovaný graf
Režie grafu: Graf s hranami se směrem se nazývá směrovaný graf. Hrany tohoto grafu znamenají jednosměrný vztah, ve kterém lze každou hranou procházet pouze v jednom směru. Následující obrázek zobrazuje jednoduchý orientovaný graf se čtyřmi uzly a pěti hranami.
Obrázek 4: Jednoduchý řízený graf
Absolutní délka, poloha nebo orientace hran v grafu nemá charakteristický význam. Jinými slovy, stejný graf můžeme vizualizovat různými způsoby přeskupením vrcholů nebo zkreslením hran, pokud se základní struktura grafu nezmění.
Co jsou vážené grafy?
O grafu se říká, že je vážený, pokud je každé hraně přiřazena 'váha'. Váha hrany může označovat vzdálenost, čas nebo cokoliv, co modeluje „spojení“ mezi párem vrcholů, které spojuje.
Například na následujícím obrázku váženého grafu můžeme vedle každé hrany pozorovat modré číslo. Toto číslo se používá k označení hmotnosti odpovídající hrany.
Obrázek 5: Příklad váženého grafu
Úvod do Dijkstrova algoritmu
Nyní, když známe některé základní koncepty grafů, pojďme se ponořit do pochopení konceptu Dijkstrova algoritmu.
Přemýšleli jste někdy nad tím, jak Mapy Google najdou nejkratší a nejrychlejší trasu mezi dvěma místy?
No, odpověď je Dijkstrův algoritmus . Dijkstrův algoritmus je grafový algoritmus který najde nejkratší cestu ze zdrojového vrcholu do všech ostatních vrcholů v grafu (nejkratší cesta z jednoho zdroje). Je to typ Greedy Algorithm, který funguje pouze na vážených grafech s kladnými váhami. Časová složitost Dijkstrova algoritmu je O(V2) pomocí matice sousednosti znázornění grafu. Tuto časovou složitost lze snížit na O((V + E) log V) pomocí přilehlého seznamu znázornění grafu, kde V je počet vrcholů a A je počet hran v grafu.
Historie Dijkstrova algoritmu
Dijkstrův algoritmus navrhl a publikoval Dr. Edsger W. Dijkstra , holandský počítačový vědec, softwarový inženýr, programátor, vědecký esejista a systémový vědec.
odstranit poslední znak z řetězce
Během rozhovoru s Philipem L. Franou pro komunikaci časopisu ACM v roce 2001 Dr. Edsger W. Dijkstra prozradil:
„Jaká je obecně nejkratší cesta z Rotterdamu do Groningenu: z daného města do daného města? Je to algoritmus pro nejkratší cestu, který jsem navrhl asi za dvacet minut. Jednoho rána jsem byl se svou mladou snoubenkou nakupovat v Amsterdamu a unaveni jsme si sedli na terasu kavárny, abychom vypili šálek kávy a já jen přemýšlel, jestli to zvládnu, a pak jsem navrhl algoritmus pro nejkratší cestu. . Jak jsem řekl, byl to dvacetiminutový vynález. Ve skutečnosti to vyšlo v roce 59, o tři roky později. Publikace je stále čtivá, vlastně je docela pěkná. Jedním z důvodů, proč je tak pěkný, bylo, že jsem ho navrhl bez tužky a papíru. Později jsem se dozvěděl, že jednou z výhod navrhování bez tužky a papíru je, že jste téměř nuceni vyhýbat se všem složitostem, kterým se lze vyhnout. Nakonec se tento algoritmus stal k mému velkému úžasu jedním ze základních kamenů mé slávy.“
Dijkstra přemýšlel o problému nejkratší cesty, když pracoval jako programátor v Matematickém centru v Amsterdamu v roce 1956, aby ilustroval možnosti nového počítače známého jako ARMAC. Jeho cílem bylo vybrat problém i řešení (vytvořené počítačem), kterým by lidé bez počítačového vzdělání mohli porozumět. Vyvinul algoritmus nejkratší cesty a později jej provedl pro ARMAC pro vágně zkrácenou dopravní mapu 64 měst v Nizozemsku (64 měst, takže 6 bitů by stačilo k zakódování čísla města). O rok později narazil na další problém od hardwarových inženýrů provozujících další počítač ústavu: Minimalizujte množství drátu potřebného k připojení kolíků na zadním panelu stroje. Jako řešení znovu objevil algoritmus nazvaný Primův algoritmus minimálního spanning tree a publikoval jej v roce 1959.
Základy Dijkstrova algoritmu
Níže jsou uvedeny základní koncepty Dijkstrova algoritmu:
- Dijkstrův algoritmus začíná v uzlu, který vybereme (zdrojový uzel), a zkoumá graf, aby našel nejkratší cestu mezi tímto uzlem a všemi ostatními uzly v grafu.
- Algoritmus uchovává záznamy o aktuálně potvrzené nejkratší vzdálenosti od každého uzlu ke zdrojovému uzlu a aktualizuje tyto hodnoty, pokud najde nějakou kratší cestu.
- Jakmile algoritmus načte nejkratší cestu mezi zdrojem a jiným uzlem, je tento uzel označen jako „navštívený“ a zahrnut do cesty.
- Postup pokračuje, dokud nejsou všechny uzly v grafu zahrnuty do cesty. Tímto způsobem máme cestu spojující zdrojový uzel se všemi ostatními uzly po nejkratší možné cestě k dosažení každého uzlu.
Pochopení fungování Dijkstrova algoritmu
A graf a zdrojový vrchol jsou požadavky na Dijkstrův algoritmus. Tento Algoritmus je založen na Greedy Approach a tak najde lokálně optimální volbu (v tomto případě lokální minima) v každém kroku Algoritmu.
Každý vrchol v tomto algoritmu bude mít definované dvě vlastnosti:
- Navštívená nemovitost
- Vlastnost cesty
Pojďme si tyto vlastnosti ve stručnosti porozumět.
Navštívená nemovitost:
- Vlastnost 'navštíveno' označuje, zda byl uzel navštíven či nikoli.
- Tuto vlastnost používáme, abychom znovu nenavštívili žádný uzel.
- Uzel je označen jako navštívený pouze tehdy, když byla nalezena nejkratší cesta.
Vlastnost cesty:
- Vlastnost 'cesta' ukládá hodnotu aktuální minimální cesty k uzlu.
- Aktuální minimální cesta implikuje nejkratší cestu, kterou jsme tohoto uzlu dosud dosáhli.
- Tato vlastnost je revidována při návštěvě kteréhokoli souseda uzlu.
- Tato vlastnost je významná, protože uloží konečnou odpověď pro každý uzel.
Zpočátku označíme všechny vrcholy nebo uzly jako nenavštívené, protože ještě nebyly navštíveny. Cesta ke všem uzlům je také nastavena na nekonečno kromě zdrojového uzlu. Navíc je cesta ke zdrojovému uzlu nastavena na nulu (0).
Poté vybereme zdrojový uzel a označíme jej jako navštívený. Poté přistoupíme ke všem sousedním uzlům zdrojového uzlu a provedeme relaxaci na každém uzlu. Relaxace je proces snižování nákladů na dosažení uzlu pomocí jiného uzlu.
V procesu relaxace je cesta každého uzlu revidována na minimální hodnotu mezi aktuální cestou uzlu, součtem cesty k předchozímu uzlu a cestou z předchozího uzlu do aktuálního uzlu.
Předpokládejme, že p[n] je hodnota aktuální cesty pro uzel n, p[m] je hodnota cesty až do dříve navštíveného uzlu m a w je váha hrany mezi aktuálním uzlem a dříve navštívená (váha hrany mezi n a m).
V matematickém smyslu může být relaxace příkladem:
p[n] = minimum(p[n], p[m] + w)
V každém následujícím kroku pak označíme nenavštívený uzel s nejmenší cestou jako navštívený a aktualizujeme cesty jeho souseda.
Tento postup opakujeme, dokud nejsou všechny uzly v grafu označeny jako navštívené.
Kdykoli přidáme uzel do navštívené množiny, příslušně se změní i cesta ke všem jejím sousedním uzlům.
if else v java
Pokud je některý uzel ponechán nedosažitelný (odpojená součást), jeho cesta zůstává 'nekonečno'. V případě, že samotný zdroj je samostatnou komponentou, pak cesta ke všem ostatním uzlům zůstává 'nekonečno'.
Pochopení Dijkstrova algoritmu na příkladu
Následuje krok, který budeme dodržovat při implementaci Dijkstrova algoritmu:
Krok 1: Nejprve označíme zdrojový uzel s aktuální vzdáleností 0 a zbytek uzlů nastavíme na NEKONEČNO.
Krok 2: Poté nastavíme nenavštívený uzel s nejmenší aktuální vzdáleností jako aktuální uzel, předpokládejme, že X.
Krok 3: Pro každého souseda N aktuálního uzlu X: Potom sečteme aktuální vzdálenost X s váhou spojující hrany X-N. Pokud je menší než aktuální vzdálenost N, nastavte ji jako novou aktuální vzdálenost N.
Krok 4: Aktuální uzel X pak označíme jako navštívený.
Krok 5: Postup zopakujeme od 'Krok 2' pokud v grafu zůstal nějaký nenavštívený uzel.
Pojďme nyní pochopit implementaci algoritmu pomocí příkladu:
Obrázek 6: Daný graf
- Jako vstup použijeme výše uvedený graf s uzlem A jako zdroj.
- Nejprve označíme všechny uzly jako nenavštívené.
- Nastavíme cestu na 0 v uzlu A a NEKONEČNO pro všechny ostatní uzly.
- Nyní označíme zdrojový uzel A jako navštívené a přistupovat k jeho sousedním uzlům.
Poznámka: Přistoupili jsme pouze k sousedním uzlům, nenavštívili jsme je. - Nyní aktualizujeme cestu k uzlu B podle 4 s pomocí relaxace, protože cesta k uzlu A je 0 a cesta z uzlu A na B je 4 a minimum((0 + 4), NEKONEČNO) je 4 .
- Aktualizujeme také cestu k uzlu C podle 5 s pomocí relaxace, protože cesta k uzlu A je 0 a cesta z uzlu A na C je 5 a minimum((0 + 5), NEKONEČNO) je 5 . Oba sousedé uzlu A jsou nyní uvolněni; proto se můžeme posunout vpřed.
- Nyní vybereme další nenavštívený uzel s nejmenší cestou a navštívíme jej. Proto navštívíme uzel B a provádět relaxaci u svých nenavštěvovaných sousedů. Po provedení relaxace cesta k uzlu C zůstane 5 , zatímco cesta k uzlu A bude jedenáct a cestu k uzlu D bude 13 .
- Nyní navštívíme uzel A a provádět relaxaci na jeho sousedních uzlech B, D , a F . Protože jediný uzel F je nenavštíven, bude uvolněný. Tedy cesta k uzlu B zůstane tak, jak je, tj. 4 , cesta k uzlu D také zůstane 13 a cestu k uzlu F bude 14 (8 + 6) .
- Nyní navštívíme uzel D a pouze uzel F bude uvolněná. Nicméně cesta k uzlu F zůstane beze změny, tj. 14 .
- Protože jediný uzel F zbývá, navštívíme ho, ale neprovedeme žádnou relaxaci, protože všechny jeho sousední uzly jsou již navštíveny.
- Jakmile navštívíte všechny uzly grafů, program se ukončí.
Konečné cesty, ke kterým jsme dospěli, jsou tedy:
A = 0 B = 4 (A -> B) C = 5 (A -> C) D = 4 + 9 = 13 (A -> B -> D) E = 5 + 3 = 8 (A -> C -> E) F = 5 + 3 + 6 = 14 (A -> C -> E -> F)
Pseudokód pro Dijkstrův algoritmus
Nyní porozumíme pseudokódu pro Dijkstrův algoritmus.
- Musíme udržovat záznam o vzdálenosti cesty každého uzlu. Můžeme tedy uložit dráhovou vzdálenost každého uzlu do pole o velikosti n, kde n je celkový počet uzlů.
- Navíc chceme získat nejkratší cestu spolu s délkou této cesty. Abychom tento problém vyřešili, namapujeme každý uzel na uzel, který naposledy aktualizoval svou délku cesty.
- Jakmile je algoritmus dokončen, můžeme zpětně sledovat cílový uzel ke zdrojovému uzlu, abychom získali cestu.
- Můžeme použít minimální prioritní frontu k načtení uzlu s nejmenší vzdáleností cesty efektivním způsobem.
Pojďme nyní implementovat pseudokód výše uvedené ilustrace:
Pseudo kód:
function Dijkstra_Algorithm(Graph, source_node) // iterating through the nodes in Graph and set their distances to INFINITY for each node N in Graph: distance[N] = INFINITY previous[N] = NULL If N != source_node, add N to Priority Queue G // setting the distance of the source node of the Graph to 0 distance[source_node] = 0 // iterating until the Priority Queue G is not empty while G is NOT empty: // selecting a node Q having the least distance and marking it as visited Q = node in G with the least distance[] mark Q visited // iterating through the unvisited neighboring nodes of the node Q and performing relaxation accordingly for each unvisited neighbor node N of Q: temporary_distance = distance[Q] + distance_between(Q, N) // if the temporary distance is less than the given distance of the path to the Node, updating the resultant distance with the minimum value if temporary_distance <distance[n] distance[n] :="temporary_distance" previous[n] returning the final list of distance return distance[], previous[] < pre> <p> <strong>Explanation:</strong> </p> <p>In the above pseudocode, we have defined a function that accepts multiple parameters - the Graph consisting of the nodes and the source node. Inside this function, we have iterated through each node in the Graph, set their initial distance to <strong>INFINITY</strong> , and set the previous node value to <strong>NULL</strong> . We have also checked whether any selected node is not a source node and added the same into the Priority Queue. Moreover, we have set the distance of the source node to <strong>0</strong> . We then iterated through the nodes in the priority queue, selected the node with the least distance, and marked it as visited. We then iterated through the unvisited neighboring nodes of the selected node and performed relaxation accordingly. At last, we have compared both the distances (original and temporary distance) between the source node and the destination node, updated the resultant distance with the minimum value and previous node information, and returned the final list of distances with their previous node information.</p> <h2>Implementation of Dijkstra'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]> Vysvětlení:
Ve výše uvedeném úryvku kódu jsme zahrnuli stdio.h hlavičkový soubor definoval dvě konstantní hodnoty: INF = 9999 a MAX = 10 . Deklarovali jsme prototypování funkce a poté definovali funkci pro Dijkstrův algoritmus jako DijkstraAlgorithm který přijímá tři argumenty – graf skládající se z uzlů, počet uzlů v grafu a zdrojový uzel. Uvnitř této funkce jsme definovali některé datové struktury, jako je 2D matice, která bude fungovat jako prioritní fronta pro algoritmus, pole pro udržování vzdálenosti mezi uzly, pole pro udržování záznamu předchozích uzlů, pole pro ukládání informace o navštívených uzlech a některé celočíselné proměnné pro uložení hodnoty minimální vzdálenosti, čítače, hodnoty dalšího uzlu a další. Poté jsme použili a vnořený for-loop iterovat uzly grafu a podle toho je přidat do fronty priorit. Opět jsme použili for-loop iterovat prvky v prioritní frontě počínaje zdrojovým uzlem a aktualizovat jejich vzdálenosti. Mimo smyčku máme nastavenou vzdálenost zdrojového uzlu jako 0 a označili jej jako navštívené v navštívené_uzly[] pole. Potom jsme nastavili hodnotu čítače jako jednu a použili jsme zatímco smyčka iterující přes počet uzlů. Uvnitř této smyčky jsme nastavili hodnotu minimální_vzdálenost tak jako INF a použil for-loop aktualizovat hodnotu minimální_vzdálenost proměnná s minimální hodnotou z a vzdálenost[] pole. Poté jsme iterovali přes nenavštívené sousední uzly vybraného uzlu pomocí for-loop a provedli relaxaci. Poté jsme vytiskli výsledná data vzdáleností vypočítaných pomocí Dijkstrova algoritmu.
V hlavní definovali a deklarovali jsme proměnné reprezentující graf, počet uzlů a zdrojový uzel. Nakonec jsme zavolali DijkstraAlgorithm() funkce předáním požadovaných parametrů.
V důsledku toho jsou uživatelům vytištěny požadované nejkratší možné cesty pro každý uzel ze zdrojového uzlu.
Kód pro Dijkstrův algoritmus v C++
Následuje implementace Dijkstrova algoritmu v programovacím jazyce C++:
Soubor: DijkstraAlgorithm.cpp
přednost java operátoru
// 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;> Vysvětlení:
Do výše uvedeného fragmentu kódu jsme zahrnuli 'iostream' a 'vektor' hlavičkových souborů a definoval konstantní hodnotu jako MAX_INT = 10000000 . Poté jsme použili standardní jmenný prostor a vytvořili prototyp DijkstraAlgorithm() funkce. Poté jsme definovali hlavní funkci programu, kterou jsme nazvali DijkstraAlgorithm() funkce. Poté jsme deklarovali některé třídy pro vytváření vrcholů a hran. Také jsme vytvořili prototyp více funkcí pro nalezení nejkratší možné cesty ze zdrojového vrcholu do cílového vrcholu a vytvořili instance tříd Vertex a Edge. Poté jsme definovali obě třídy, abychom vytvořili vrcholy a hrany grafu. Poté jsme definovali DijkstraAlgorithm() funkce k vytvoření grafu a provádění různých operací. Uvnitř této funkce jsme deklarovali některé vrcholy a hrany. Poté jsme nastavili zdrojový vrchol grafu a zavolali Dijkstra() funkce pro nalezení nejkratší možné vzdálenosti a Print_Shortest_Route_To() funkce pro tisk nejkratší vzdálenosti od zdrojového vrcholu k vrcholu 'F' . Poté jsme definovali Dijkstra() funkce pro výpočet nejkratších možných vzdáleností všech vrcholů od zdrojového vrcholu. Také jsme definovali některé další funkce pro nalezení vrcholu s nejkratší vzdáleností, abychom vrátili všechny vrcholy sousedící se zbývajícím vrcholem, vrátili vzdálenost mezi dvěma spojenými vrcholy, zkontrolovali, zda vybraný vrchol v grafu existuje, a vytiskli nejkratší možnou cestu ze zdrojového vrcholu do cílového vrcholu.
Výsledkem je požadovaná nejkratší cesta pro vrchol 'F' ze zdrojového uzlu se vytiskne pro uživatele.
Kód pro Dijkstrův algoritmus v Javě
Následuje implementace Dijkstrova algoritmu v programovacím jazyce Java:
Soubor: 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;> Vysvětlení:
Ve výše uvedeném úryvku kódu jsme definovali veřejnou třídu jako DijkstraAlgorithm() . Uvnitř této třídy jsme definovali veřejnou metodu jako dijkstraAlgorithm() najít nejkratší vzdálenost od zdrojového vrcholu k cílovému vrcholu. Uvnitř této metody jsme definovali proměnnou pro uložení počtu uzlů. Poté jsme definovali booleovské pole pro ukládání informací o navštívených vrcholech a pole celých čísel pro ukládání jejich příslušných vzdáleností. Zpočátku jsme deklarovali hodnoty v obou polích jako Nepravdivé a MAX_VALUE , resp. Také jsme nastavili vzdálenost zdrojového vrcholu na nulu a použili jsme for-loop pro aktualizaci vzdálenosti mezi zdrojovým vrcholem a cílovým vrcholem s minimální vzdáleností. Potom jsme aktualizovali vzdálenosti sousedních vrcholů vybraného vrcholu provedením relaxace a vytiskli nejkratší vzdálenosti pro každý vrchol. Poté jsme definovali metodu, jak najít minimální vzdálenost od zdrojového vrcholu k cílovému vrcholu. Poté jsme definovali hlavní funkci, kde jsme deklarovali vrcholy grafu a vytvořili instanci DijkstraAlgorithm() třída. Nakonec jsme zavolali dijkstraAlgorithm() metoda k nalezení nejkratší vzdálenosti mezi zdrojovým vrcholem a cílovým vrcholem.
V důsledku toho jsou uživatelům vytištěny požadované nejkratší možné cesty pro každý uzel ze zdrojového uzlu.
vložit vodoznak do wordu
Kód pro Dijkstrův algoritmus v Pythonu
Následuje implementace Dijkstrova algoritmu v programovacím jazyce Python:
Soubor: 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>
Výstup
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
Vysvětlení:
Ve výše uvedeném úryvku kódu jsme importovali sys a deklaroval seznamy skládající se z hodnot pro uzly a hrany. Potom jsme definovali funkci jako toBeVisited() zjistit, který uzel bude navštíven jako další. Poté jsme zjistili celkový počet uzlů v grafu a nastavili počáteční vzdálenosti pro každý uzel. Poté jsme vypočítali minimální vzdálenost od zdrojového uzlu k cílovému uzlu, provedli relaxaci na sousedních uzlech a aktualizovali vzdálenosti v seznamu. Tyto vzdálenosti jsme pak uživatelům vytiskli ze seznamu.
V důsledku toho jsou uživatelům vytištěny požadované nejkratší možné cesty pro každý uzel ze zdrojového uzlu.
Časová a prostorová složitost Dijkstrova algoritmu
- Časová složitost Dijkstrova algoritmu je O(E log V) , kde E je počet hran a V je počet vrcholů.
- Prostorová složitost Dijkstrova algoritmu je O(V), kde V je počet vrcholů.
Výhody a nevýhody Dijkstrova algoritmu
Pojďme diskutovat o některých výhodách Dijkstrova algoritmu:
- Jednou z hlavních výhod použití Dijkstrova algoritmu je, že má téměř lineární časovou a prostorovou složitost.
- Tento algoritmus můžeme použít k výpočtu nejkratší cesty z jednoho vrcholu do všech ostatních vrcholů a jednoho zdrojového vrcholu do jednoho cílového vrcholu zastavením algoritmu, jakmile získáme nejkratší vzdálenost pro cílový vrchol.
- Tento algoritmus funguje pouze pro řízené vážené grafy a všechny okraje tohoto grafu by měly být nezáporné.
Navzdory mnoha výhodám má Dijkstrův algoritmus také některé nevýhody, jako například:
- Dijkstrův algoritmus provádí skrytý průzkum, který během procesu zabere hodně času.
- Tento algoritmus je neschopný zpracovat negativní hrany.
- Protože tento algoritmus směřuje k acyklickému grafu, nemůže vypočítat přesnou nejkratší cestu.
- Vyžaduje také údržbu, aby se vedl záznam o navštívených vrcholech.
Některé aplikace Dijkstrova algoritmu
Dijkstrův algoritmus má různé aplikace v reálném světě, z nichž některé jsou uvedeny níže:
Závěr
- Ve výše uvedeném tutoriálu jsme nejprve porozuměli základním konceptům Graph spolu s jeho typy a aplikacemi.
- Poté jsme se dozvěděli o Dijkstrově algoritmu a jeho historii.
- S pomocí příkladu jsme také pochopili základní fungování Dijkstrova algoritmu.
- Poté jsme studovali, jak napsat kód pro Dijkstrův algoritmus pomocí Pseudokódu.
- Pozorovali jsme jeho implementaci v programovacích jazycích jako C, C++, Java a Python se správnými výstupy a vysvětleními.
- Také jsme pochopili časovou a prostorovou složitost Dijkstrova algoritmu.
- Nakonec jsme diskutovali o výhodách a nevýhodách Dijkstrova algoritmu a některých jeho aplikací v reálném životě.