A következő oktatóanyag Dijkstra legrövidebb út algoritmusát tanítja meg nekünk. Dijkstra algoritmusának működését egy lépésenkénti grafikus magyarázattal fogjuk megérteni.
A következőkre térünk ki:
- A gráf alapvető fogalmainak rövid áttekintése
- Ismerje meg a Dijkstra-algoritmus használatát
- Ismerje meg az algoritmus működését egy lépésről lépésre példával
Tehát kezdjük.
A grafikonok rövid bemutatása
Grafikonok nem lineáris adatstruktúrák, amelyek az elemek közötti „kapcsolatokat” reprezentálják. Ezeket az elemeket a Csúcsok , és a gráf bármely két csúcsát összekötő vonalak vagy ívek a Élek . Formálisabban a Graph tartalmaz csúcsok halmaza (V) és élkészlet (E) . A grafikont jelöli G(V, E) .
Grafikon összetevői
Az alábbi ábra egy grafikon grafikus ábrázolását mutatja:
1.ábra: Grafikon grafikus ábrázolása
A fenti ábrán a csúcsokat/csomópontokat színes körökkel, az éleket pedig a csomópontokat összekötő vonalakkal jelöljük.
A grafikonok alkalmazásai
A grafikonokat számos valós probléma megoldására használják. A hálózatok ábrázolására grafikonokat használnak. Ezek a hálózatok tartalmazhatnak telefon- vagy áramköri hálózatokat vagy útvonalakat egy városban.
Például használhatunk Graphokat egy olyan közlekedési hálózati modell megtervezéséhez, ahol a csúcsok a termékeket küldő vagy fogadó létesítményeket jelenítik meg, az élek pedig az őket összekötő utakat vagy útvonalakat. Az alábbiakban ugyanennek a képi ábrázolása:
2. ábra: A közlekedési hálózat képi ábrázolása
A grafikonokat különféle közösségi média platformokon is használják, mint például a LinkedIn, a Facebook, a Twitter és így tovább. Például az olyan platformok, mint a Facebook, grafikonokat használnak felhasználóik adatainak tárolására, ahol minden személyt egy csúcs jelzi, és mindegyik egy olyan struktúra, amely olyan információkat tartalmaz, mint a személyazonosító, név, nem, cím stb.
regressziós kifejezés java-ban
Grafikonok típusai
A grafikonok két típusba sorolhatók:
- Irányítatlan gráf
- Irányított grafikon
Irányítatlan grafikon: Az irány nélküli élekkel rendelkező gráfot irányítatlan gráfnak nevezzük. Ennek a gráfnak az élei egy kétirányú kapcsolatot jelentenek, amelyben minden él mindkét irányban bejárható. A következő ábra egy egyszerű irányítatlan gráfot mutat be négy csomóponttal és öt éllel.
3. ábra: Egy egyszerű irányítatlan grafikon
Irányított grafikon: Az élekkel rendelkező gráfot irányított gráfnak nevezzük. Ennek a gráfnak az élei egyirányú összefüggést jelentenek, amelyben az egyes élek csak egy irányban járhatók be. A következő ábra egy egyszerű irányított gráfot mutat be négy csomóponttal és öt éllel.
4. ábra: Egy egyszerű irányított grafikon
Az élek abszolút hosszának, helyzetének vagy irányának egy gráfillusztrációban jellemzően nincs jelentése. Más szavakkal, ugyanazt a gráfot különböző módon vizualizálhatjuk a csúcsok átrendezésével vagy az élek torzításával, ha a gráf mögöttes szerkezete nem változik.
Mik azok a súlyozott grafikonok?
Egy gráfot súlyozottnak mondunk, ha minden élhez hozzá van rendelve egy „súly”. Egy él súlya jelölhet távolságot, időt vagy bármit, ami az általa összekapcsolt csúcspárok közötti „kapcsolatot” modellezi.
Például a súlyozott gráf következő ábráján minden él mellett egy kék szám látható. Ez a szám a megfelelő él súlyának jelzésére szolgál.
5. ábra: Példa súlyozott grafikonra
Bevezetés a Dijkstra-algoritmusba
Most, hogy ismerünk néhány alapvető grafikonfogalmat, merüljünk el a Dijkstra-algoritmus fogalmának megértésében.
Gondolkozott már azon, hogyan találja meg a Google Térkép a legrövidebb és leggyorsabb útvonalat két hely között?
Nos, a válasz az Dijkstra algoritmusa . Dijkstra algoritmusa egy Graph algoritmus hogy megtalálja a legrövidebb utat forráscsúcstól a Graph összes többi csúcsáig (egyetlen forrás legrövidebb útja). Ez egyfajta mohó algoritmus, amely csak pozitív súllyal rendelkező súlyozott grafikonokon működik. Dijkstra algoritmusának időbeli összetettsége az O(V2) a gráf szomszédsági mátrixábrázolása segítségével. Ez az idő bonyolultsága csökkenthető O((V + E) log V) a gráf szomszédsági listás ábrázolása segítségével, ahol BAN BEN a csúcsok száma és ÉS a gráf éleinek száma.
Dijkstra algoritmusának története
Dijkstra algoritmusát tervezte és adta ki Dr. Edsger W. Dijkstra , holland informatikus, szoftvermérnök, programozó, tudományos esszéíró és rendszertudós.
mik azok a szelektorok a css-ben
Egy Philip L. Franával, az ACM folyóirat kommunikációja számára készített interjú során 2001-ben Dr. Edsger W. Dijkstra felfedte:
„Általában mi a legrövidebb út Rotterdamból Groningenbe: adott városból adott városba? Ez a legrövidebb út algoritmusa, amit körülbelül húsz perc alatt megterveztem. Egyik reggel Amszterdamban vásároltam a fiatal menyasszonyommal, és fáradtan leültünk a kávézó teraszára inni egy csésze kávét, és csak azon gondolkodtam, hogy meg tudom-e csinálni, majd megterveztem a legrövidebb út algoritmusát. . Mint mondtam, húszperces találmány volt. Valójában '59-ben jelent meg, három évvel később. A kiadvány továbbra is olvasható, sőt, egész szép. Az egyik oka annak, hogy olyan szép, hogy ceruza és papír nélkül terveztem. Később tudtam meg, hogy a ceruza és papír nélküli tervezés egyik előnye, hogy szinte kénytelen kerülni minden elkerülhető bonyolultságot. Végül nagy ámulatomra ez az algoritmus lett a hírnevem egyik sarokköve.
Dijkstra a legrövidebb út problémájára gondolt, miközben programozóként dolgozott az amszterdami Matematikai Központban 1956-ban, hogy bemutassa az ARMAC néven ismert új számítógép képességeit. Célja az volt, hogy olyan problémát és megoldást (a számítógép által előállított) válasszon ki, amelyet számítógépes háttérrel nem rendelkező emberek is megértenek. Kifejlesztette a legrövidebb út algoritmusát, majd később végrehajtotta az ARMAC számára 64 holland város halmozottan lerövidített közlekedési térképéhez (64 város, tehát 6 bit elegendő lenne a városszám kódolásához). Egy évvel később újabb problémára bukkant az intézet következő számítógépét kezelő hardvermérnökök részéről: Csökkentse a minimálisra a gép hátlapján lévő érintkezők csatlakoztatásához szükséges vezetékek mennyiségét. Megoldásként újra felfedezte a Prim minimális feszítőfa algoritmusát, és 1959-ben publikálta.
Dijkstra algoritmusának alapjai
A Dijkstra-algoritmus alapfogalmai a következők:
- A Dijkstra algoritmusa az általunk kiválasztott csomópontnál (a forráscsomópontnál) kezdődik, és megvizsgálja a gráfot, hogy megtalálja a legrövidebb utat az adott csomópont és a gráf összes többi csomópontja között.
- Az algoritmus rögzíti az aktuálisan elismert legrövidebb távolságot az egyes csomópontoktól a forráscsomópontig, és frissíti ezeket az értékeket, ha rövidebb utat talál.
- Miután az algoritmus lekérte a forrás és egy másik csomópont közötti legrövidebb utat, az adott csomópont „látogatott”-ként lesz megjelölve, és belekerül az útvonalba.
- Az eljárás mindaddig folytatódik, amíg a gráf összes csomópontja be nem kerül az elérési útba. Ily módon van egy útvonalunk, amely összeköti a forráscsomópontot az összes többi csomóponttal, a lehető legrövidebb utat követve az egyes csomópontok eléréséhez.
Dijkstra algoritmusa működésének megértése
A grafikon és forráscsúcs követelményei a Dijkstra algoritmusának. Ez az algoritmus a mohó megközelítésen alapul, és így megtalálja a lokálisan optimális választást (jelen esetben a helyi minimumokat) az algoritmus minden lépésében.
Ebben az algoritmusban minden csúcsnak két tulajdonsága van:
- Meglátogatott ingatlan
- Útvonal tulajdonság
Fogalmazzuk meg röviden ezeket a tulajdonságokat.
Meglátogatott ingatlan:
- A „látogatott” tulajdonság azt jelzi, hogy a csomópontot meglátogatták-e vagy sem.
- Ezt a tulajdonságot azért használjuk, hogy ne keressünk fel újra egyetlen csomópontot sem.
- Egy csomópont csak akkor jelölődik meglátogatottnak, ha megtalálta a legrövidebb utat.
Útvonal tulajdonság:
- A „path” tulajdonság a csomóponthoz vezető aktuális minimális útvonal értékét tárolja.
- A jelenlegi minimális út az eddigi legrövidebb utat jelenti, amelyen elértük ezt a csomópontot.
- Ezt a tulajdonságot a rendszer felülvizsgálja, amikor a csomópont bármely szomszédját meglátogatják.
- Ez a tulajdonság azért fontos, mert minden csomóponthoz tárolja a végső választ.
Kezdetben az összes csúcsot vagy csomópontot meg nem látogatottnak jelöljük, mivel azokat még meg kell látogatni. Az összes csomópont elérési útja szintén a végtelenbe van állítva, kivéve a forráscsomópontot. Ezenkívül a forráscsomópont elérési útja nullára (0) van állítva.
Ezután kiválasztjuk a forráscsomópontot, és megjelöljük látogatottként. Ezt követően elérjük a forráscsomópont összes szomszédos csomópontját, és minden csomóponton relaxációt hajtunk végre. A relaxáció az a folyamat, amelynek során csökkentik egy csomópont elérésének költségét egy másik csomópont segítségével.
Az ellazítás során az egyes csomópontok útvonalát a minimális értékre módosítják a csomópont aktuális útvonala, az előző csomóponthoz vezető útvonal és az előző csomóponttól az aktuális csomópontig tartó útvonal összege között.
Tegyük fel, hogy p[n] az n csomópont aktuális útvonalának értéke, p[m] a korábban meglátogatott m csomóponthoz vezető út értéke, w pedig az aktuális csomópont és az aktuális csomópont közötti él súlya. korábban meglátogatott (n és m közötti élsúly).
Matematikai értelemben a relaxációt a következőképpen lehet szemléltetni:
p[n] = minimum (p[n], p[m] + w)
Ezután minden további lépésben megjelölünk egy nem látogatott csomópontot, amelyen a legkevesebb elérési út jár, és frissítjük a szomszédja útvonalait.
Ezt az eljárást addig ismételjük, amíg a grafikon összes csomópontja meglátogatottnak nem lesz jelölve.
Amikor hozzáadunk egy csomópontot a látogatott halmazhoz, az összes szomszédos csomópont elérési útja is ennek megfelelően változik.
Ha bármely csomópont elérhetetlen marad (leválasztott komponens), az útvonala „végtelen” marad. Abban az esetben, ha maga a forrás egy különálló komponens, akkor az összes többi csomóponthoz vezető út „végtelen” marad.
hogyan lehet karakterláncból int-re konvertálni
Dijkstra algoritmusának megértése egy példával
A következő lépés a Dijkstra algoritmus megvalósítása:
1. lépés: Először a forráscsomópontot 0 aktuális távolsággal jelöljük meg, a többi csomópontot pedig VÉGTELENSÉGRE állítjuk.
2. lépés: Ezután a legkisebb aktuális távolsággal rendelkező, nem látogatott csomópontot állítjuk be aktuális csomópontnak, tegyük fel, hogy X.
3. lépés: Az aktuális X csomópont minden N szomszédjához: Ezután hozzáadjuk X aktuális távolságát az X-N-t összekötő él súlyához. Ha kisebb, mint az N aktuális távolsága, állítsa be N új aktuális távolságaként.
4. lépés: Ezután az aktuális X csomópontot látogatottként jelöljük meg.
5. lépés: A folyamatot megismételjük től '2. lépés' ha a gráfban maradt meglátogatatlan csomópont.
Most egy példa segítségével értsük meg az algoritmus megvalósítását:
6. ábra: Az adott grafikon
- A fenti grafikont használjuk bemenetként, csomóponttal A mint a forrás.
- Először az összes csomópontot nem látogatottként jelöljük meg.
- Kijelöljük az utat 0 csomópontnál A és VÉGTELENSÉG az összes többi csomóponthoz.
- Most megjelöljük a forráscsomópontot A meglátogatott, és hozzáférhet a szomszédos csomópontokhoz.
Jegyzet: A szomszédos csomópontokat csak elértük, nem látogattuk meg. - Most frissítjük a csomópont elérési útját B által 4 relaxáció segítségével, mert a csomóponthoz vezető út A van 0 és az út a csomóponttól A nak nek B van 4 , és a minimum((0 + 4), VÉGTELEN) van 4 .
- A csomópont elérési útját is frissítjük C által 5 relaxáció segítségével, mert a csomóponthoz vezető út A van 0 és az út a csomóponttól A nak nek C van 5 , és a minimum((0 + 5), VÉGTELEN) van 5 . Mindkét csomópont szomszédja A most nyugodtak; ezért előre tudunk lépni.
- Most kiválasztjuk a következő nem látogatott csomópontot, amelynél a legkevesebb elérési út van, és meglátogatjuk. Ezért meglátogatjuk a csomópontot B és relaxációt végez a nem látogatott szomszédokon. A relaxáció elvégzése után az út a csomóponthoz C marad 5 , míg a csomóponthoz vezető út ÉS válik tizenegy , és a csomóponthoz vezető út D válik 13 .
- Most meglátogatjuk a csomópontot ÉS és relaxációt végez a szomszédos csomópontjain B, D , és F . Mivel csak csomópont F látogatatlan, nyugodt lesz. Így a csomóponthoz vezető út B marad, ahogy van, azaz 4 , a csomóponthoz vezető út D is megmarad 13 , és a csomóponthoz vezető út F válik 14 (8 + 6) .
- Most meglátogatjuk a csomópontot D , és csak a csomópont F laza lesz. Azonban a csomóponthoz vezető út F változatlan marad, azaz 14 .
- Mivel csak csomópont F megmaradt, meglátogatjuk, de nem hajtunk végre semmilyen relaxációt, mivel az összes szomszédos csomópont már meg van látogatva.
- Miután a grafikonok összes csomópontját meglátogatta, a program véget ér.
Ezért az utolsó utak, amelyeket levontunk, a következők:
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)
Pszeudokód Dijkstra algoritmusához
Most megértjük a Dijkstra-féle algoritmus pszeudokódját.
- Minden csomópont úttávolságáról nyilvántartást kell vezetnünk. Ezért az egyes csomópontok úttávolságát egy n méretű tömbben tárolhatjuk, ahol n a csomópontok teljes száma.
- Sőt, a legrövidebb utat szeretnénk lekérni az út hosszával együtt. A probléma megoldása érdekében minden csomópontot leképezünk arra a csomópontra, amely utoljára frissítette az útvonal hosszát.
- Ha az algoritmus elkészült, visszaállíthatjuk a célcsomópontot a forráscsomóponthoz az elérési út lekéréséhez.
- Használhatunk minimális prioritási sort a legkisebb útvonaltávolságú csomópont hatékony lekérésére.
Valósítsuk meg a fenti ábra pszeudokódját:
Pszeudokó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]> Magyarázat:
A fenti kódrészletben a stdio.h A fejlécfájl két állandó értéket definiált: INF = 9999 és MAX = 10 . Deklaráltuk a függvény prototípusát, majd definiáltuk a függvényt Dijkstra algoritmusához DijkstraAlgoritmus amely három argumentumot fogad el – a csomópontokból álló grafikont, a grafikon csomópontjainak számát és a forráscsomópontot. Ezen a függvényen belül definiáltunk néhány adatstruktúrát, például egy 2D mátrixot, amely az algoritmus prioritási soraként működik, egy tömböt a csomópontok közötti távolság meghatározásához, egy tömböt az előző csomópontok rekordjának megőrzéséhez, egy tömböt a tároláshoz. a meglátogatott csomópontok információi, valamint néhány egész változó a minimális távolság értékének, a számlálónak, a következő csomópont értékének és egyebeknek a tárolására. Ezután használtuk a beágyazott for-hurok hogy a Graph csomópontjain keresztül iteráljon, és ennek megfelelően adja hozzá őket a prioritási sorhoz. Ismét használtuk a for-hurok hogy a prioritási sor elemeit a forráscsomóponttól kezdve iterálja, és frissítse a távolságukat. A cikluson kívül a forráscsomópont távolságát a következőre állítottuk be 0 és látogatottként jelölte meg a látogatott_csomópontok[] sor. Ezután beállítottuk a számláló értékét egynek, és használtuk a míg hurok iteráció a csomópontok számán keresztül. Ezen a hurkon belül beállítottuk az értékét minimális_távolság mint INF és használta a for-hurok az érték frissítéséhez minimális_távolság változó a minimális értékkel távolság[] sor. Ezután a kiválasztott csomópont nem látogatott szomszédos csomópontjain keresztül iteráltuk a for-hurok és relaxációt végzett. Ezután kinyomtattuk a Dijkstra-féle algoritmus segítségével kiszámított távolságok eredő adatait.
Ban,-ben fő- függvényben definiáltuk és deklaráltuk a Graphot reprezentáló változókat, a csomópontok számát és a forráscsomópontot. Végre felhívtuk a DijkstraAlgoritmus() funkciót a szükséges paraméterek átadásával.
Ennek eredményeként a rendszer kinyomtatja a felhasználók számára a szükséges lehető legrövidebb útvonalakat a forráscsomópont minden csomópontjához.
Dijkstra algoritmusának kódja C++ nyelven
Az alábbiakban bemutatjuk a Dijkstra algoritmus megvalósítását a C++ programozási nyelven:
Fájl: 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;> Magyarázat:
A fenti kódrészletben a 'iostream' és 'vektor' fejlécfájlokat, és definiált egy állandó értéket, mint MAX_INT = 10000000 . Ezután a szabványos névteret használtuk, és prototípust készítettünk a DijkstraAlgoritmus() funkció. Ezután meghatároztuk a program fő funkcióját, amelyet a DijkstraAlgoritmus() funkció. Ezt követően deklaráltunk néhány osztályt csúcsok és élek létrehozására. Több függvény prototípusát is elkészítettük, hogy megtaláljuk a lehető legrövidebb utat a forráscsúcstól a célcsúcsig, és példányosítottuk a Vertex és Edge osztályokat. Ezután mindkét osztályt meghatároztuk, hogy létrehozzuk a gráf csúcsait és éleit. Ezután meghatároztuk a DijkstraAlgoritmus() függvény grafikon létrehozásához és különböző műveletek végrehajtásához. Ezen a függvényen belül deklaráltunk néhány csúcsot és élt. Ezután beállítjuk a gráf forráscsúcsát, és elhívjuk a Dijkstra() funkció segítségével megtalálja a lehető legrövidebb távolságot és Nyomtatás_rövidebb_útvonal() függvény a forráscsúcs és a csúcs közötti legrövidebb távolság kinyomtatására 'F' . Ezután meghatároztuk a Dijkstra() függvény az összes csúcs lehető legrövidebb távolságának kiszámításához a forráscsúcstól. Meghatároztunk néhány további függvényt is a legrövidebb távolságú csúcs megkeresésére, hogy visszaadja a fennmaradó csúcsokkal szomszédos összes csúcsot, visszaadja két összekapcsolt csúcs közötti távolságot, ellenőrizze, hogy a kiválasztott csúcs létezik-e a gráfban, és kinyomtathatja a a lehető legrövidebb út a forráscsúcstól a célcsúcsig.
Ennek eredményeként a csúcshoz szükséges legrövidebb út 'F' a forrás csomópontból kinyomtatva a felhasználók számára.
gépirat nyíl funkció
Dijkstra algoritmusának kódja Java nyelven
A következő a Dijkstra algoritmus implementációja a Java programozási nyelvben:
Fájl: 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;> Magyarázat:
A fenti kódrészletben egy nyilvános osztályt a következőképpen határoztunk meg DijkstraAlgoritmus() . Ezen az osztályon belül definiáltunk egy nyilvános metódust, mint dijkstraAlgoritmus() hogy megtaláljuk a forráscsúcs és a célcsúcs közötti legrövidebb távolságot. Ezen a metóduson belül definiáltunk egy változót a csomópontok számának tárolására. Ezután definiáltunk egy logikai tömböt a meglátogatott csúcsokkal kapcsolatos információk tárolására, valamint egy egész szám tömböt a megfelelő távolságok tárolására. Kezdetben mindkét tömbben a következőképpen deklaráltuk az értékeket Hamis és MAX_VALUE , ill. A forráscsúcs távolságát is nullára állítottuk, és a for-hurok hogy frissítse a forráscsúcs és a célcsúcs közötti távolságot a minimális távolsággal. Ezután frissítettük a kiválasztott csúcs szomszédos csúcsainak távolságait relaxáció végrehajtásával, és minden csúcsra kinyomtattuk a legrövidebb távolságokat. Ezután meghatároztunk egy módszert a forráscsúcs és a célcsúcs közötti minimális távolság meghatározására. Ezután meghatároztuk a fő függvényt, ahol deklaráltuk a gráf csúcsait, és példányosítottuk a DijkstraAlgoritmus() osztály. Végül felhívtuk a dijkstraAlgoritmus() módszer a forráscsúcs és a célcsúcs közötti legrövidebb távolság meghatározására.
Ennek eredményeként a rendszer kinyomtatja a felhasználók számára a szükséges lehető legrövidebb útvonalakat a forráscsomópont minden csomópontjához.
Dijkstra algoritmusának kódja Pythonban
Az alábbiakban bemutatjuk a Dijkstra algoritmus megvalósítását a Python programozási nyelvben:
Fájl: 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>
Kimenet
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
Magyarázat:
A fenti kódrészletben importáltuk a sys modult, és deklarálta a csomópontok és élek értékeit tartalmazó listákat. Ezután definiáltunk egy függvényt, mint látogatni() hogy megtudja, melyik csomópontot keresi fel legközelebb. Ezután megtaláltuk a csomópontok teljes számát a grafikonon, és minden csomóponthoz beállítottuk a kezdeti távolságokat. Ezután kiszámítottuk a forráscsomópont és a célcsomópont közötti minimális távolságot, relaxációt végeztünk a szomszédos csomópontokon, és frissítettük a listában szereplő távolságokat. Ezután ezeket a távolságokat kinyomtattuk a listából a felhasználók számára.
Ennek eredményeként a rendszer kinyomtatja a felhasználók számára a szükséges lehető legrövidebb útvonalakat a forráscsomópont minden csomópontjához.
Dijkstra algoritmusának idő és tér összetettsége
- Dijkstra algoritmusának időbonyolultsága az O(E log V) , ahol E az élek száma, V pedig a csúcsok száma.
- A Dijkstra-algoritmus térkomplexitása O(V), ahol V a csúcsok száma.
A Dijkstra-algoritmus előnyei és hátrányai
Beszéljünk a Dijkstra algoritmus előnyeiről:
- A Dijkstra-algoritmus használatának egyik fő előnye, hogy szinte lineáris idő- és térkomplexitású.
- Ezzel az algoritmussal kiszámíthatjuk a legrövidebb utat egyetlen csúcstól az összes többi csúcsig és egyetlen forráscsúcstól egyetlen célcsúcsig, ha leállítjuk az algoritmust, ha megkapjuk a célcsúcs legrövidebb távolságát.
- Ez az algoritmus csak irányított súlyozott gráfoknál működik, és ennek a gráfnak minden éle nem lehet negatív.
Annak ellenére, hogy számos előnye van, a Dijkstra algoritmusnak vannak hátrányai is, például:
- A Dijkstra algoritmusa rejtett feltárást hajt végre, amely sok időt vesz igénybe a folyamat során.
- Ez az algoritmus tehetetlen a negatív élek kezelésére.
- Mivel ez az algoritmus az aciklikus gráfhoz vezet, nem tudja kiszámítani a pontos legrövidebb utat.
- Ezenkívül karbantartást igényel a meglátogatott csúcsok nyilvántartása.
A Dijkstra-algoritmus néhány alkalmazása
A Dijkstra algoritmusa különféle valós alkalmazásokkal rendelkezik, amelyek közül néhányat az alábbiakban ismertetünk:
A következtetés
- A fenti oktatóanyagban először is megértettük a Graph alapfogalmait, típusait és alkalmazásait.
- Ezután megismerkedtünk Dijkstra algoritmusával és történetével.
- Dijkstra algoritmusának alapvető működését is megértettük egy példa segítségével.
- Ezt követően azt tanulmányoztuk, hogyan írjunk kódot Dijkstra algoritmusához a Pseudocode segítségével.
- Megfigyeltük a megvalósítását olyan programozási nyelveken, mint a C, C++, Java és Python, megfelelő kimenetekkel és magyarázatokkal.
- Megértettük Dijkstra algoritmusának idő és tér összetettségét is.
- Végül megvitattuk a Dijkstra algoritmus előnyeit és hátrányait, valamint néhány valós alkalmazását.