АЛГОРИТМ НАЙКОРОТШОГО ШЛЯХУ ДЕЙКСТРИ З ПРИКЛАДАМИ

Наступний посібник навчить нас про алгоритм найкоротшого шляху Дейкстри. Ми зрозуміємо роботу алгоритму Дейкстри з покроковим графічним поясненням.

Ми розглянемо наступне:

Короткий огляд фундаментальних понять графа
Зрозумійте використання алгоритму Дейкстри
Зрозумійте роботу алгоритму на прикладі крок за кроком

Отже, почнемо.

Короткий вступ до графіків

графіки це нелінійні структури даних, що представляють «зв'язки» між елементами. Ці елементи відомі як Вершини , а лінії або дуги, які з’єднують будь-які дві вершини графа, називаються Краї . Більш формально, граф містить набір вершин (V) і набір країв (E) . Граф позначається G(V, E) .

Компоненти графа

Вершини:Вершини — це основні одиниці графа, які використовуються для представлення реальних об’єктів, осіб або сутностей. Іноді вершини також називають вузлами.Краї:Ребра малюються або використовуються для з’єднання двох вершин графа. Іноді ребра також називаються дугами.

На наступному малюнку показано графічне представлення графіка:

Фігура 1: Графічне представлення графа

На наведеному вище малюнку вершини/вузли позначено кольоровими колами, а ребра позначено лініями, що з’єднують вузли.

Застосування графіків

Графи використовуються для вирішення багатьох реальних завдань. Для представлення мереж використовуються графіки. Ці мережі можуть включати в себе телефонні або комунікаційні мережі або шляхи в місті.

перевести рядок як int java

Наприклад, ми могли б використовувати Graphs для розробки моделі транспортної мережі, де вершини відображають об’єкти, які відправляють або отримують продукти, а ребра представляють дороги або шляхи, що їх з’єднують. Нижче наведено графічне зображення того самого:

малюнок 2: Ілюстративне зображення транспортної мережі

Графіки також використовуються в різних соціальних мережах, таких як LinkedIn, Facebook, Twitter тощо. Наприклад, такі платформи, як Facebook, використовують Graphs для зберігання даних своїх користувачів, де кожна особа позначена вершиною, і кожна з них є структурою, що містить таку інформацію, як ідентифікатор особи, ім’я, стать, адреса тощо.

Типи графіків

Графіки можна розділити на два типи:

Неорієнтований граф
Орієнтований граф

Неорієнтований графік: Граф з ребрами, які не мають напрямку, називається неорієнтованим графом. Ребра цього графа передбачають двосторонній зв’язок, у якому кожне ребро можна обійти в обох напрямках. На наступному малюнку зображено простий неорієнтований граф із чотирма вузлами та п’ятьма ребрами.

малюнок 3: Простий неорієнтований граф

Спрямований графік: Граф із ребрами з напрямком називається орієнтованим графом. Ребра цього графіка передбачають односторонній зв’язок, у якому кожне ребро можна обійти лише в одному напрямку. На наступному малюнку зображено простий орієнтований граф із чотирма вузлами та п’ятьма ребрами.

Малюнок 4: Простий орієнтований граф

Абсолютна довжина, положення або орієнтація ребер на ілюстрації графіка зазвичай не мають значення. Іншими словами, ми можемо візуалізувати один і той самий граф різними способами, переставляючи вершини або спотворюючи ребра, якщо базова структура графа не змінюється.

Що таке зважені графіки?

Граф називається зваженим, якщо кожному ребру присвоєно «вагу». Вага ребра може позначати відстань, час або будь-що, що моделює «з’єднання» між парою вершин, які воно з’єднує.

Наприклад, ми можемо побачити синє число біля кожного краю на наступному малюнку зваженого графіка. Це число використовується для позначення ваги відповідного краю.

Малюнок 5: Приклад зваженого графіка

Введення в алгоритм Дейкстри

Тепер, коли ми знаємо деякі базові концепції графів, давайте поглибимося в розуміння концепції алгоритму Дейкстри.

Ви коли-небудь замислювалися, як Google Maps знаходить найкоротший і найшвидший маршрут між двома місцями?

Ну, відповідь така Алгоритм Дейкстри . Алгоритм Дейкстри є графовим алгоритмом що знаходить найкоротший шлях від вершини джерела до всіх інших вершин у графі (найкоротший шлях одного джерела). Це тип жадібного алгоритму, який працює лише на зважених графіках із додатними вагами. Часова складність алгоритму Дейкстри становить O(V²) за допомогою представлення графа матрицею суміжності. На цей час складність можна скоротити до O((V + E) log V) за допомогою списку суміжності представлення графа, де IN є число вершин і І це кількість ребер у графі.

Історія алгоритму Дейкстри

Алгоритм Дейкстри був розроблений і опублікований Доктор. Едсгер В. Дейкстра , голландський фахівець з інформатики, інженер-програміст, програміст, науковий есеїст і системознавець.

Під час інтерв’ю з Філіпом Л. Франою для комунікацій журналу ACM у 2001 році доктор Едсгер В. Дейкстра відкрив:

Який найкоротший шлях подорожі з Роттердама до Гронінгена взагалі: з певного міста в дане місто? Це алгоритм найкоротшого шляху, який я розробив приблизно за двадцять хвилин. Одного ранку я робив покупки в Амстердамі зі своєю молодою нареченою, і втомлені ми сіли на терасу кафе, щоб випити чашку кави, і я просто думав, чи зможу я це зробити, і тоді я розробив алгоритм найкоротшого шляху . Як я вже сказав, це був двадцятихвилинний винахід. Насправді вона була опублікована в 1959 році, трьома роками пізніше. Видання ще читабельне, воно, правда, досить гарне. Однією з причин, чому це так гарно, було те, що я створив його без олівця та паперу. Пізніше я дізнався, що одна з переваг проектування без олівця та паперу полягає в тому, що ви майже змушені уникати всіх складнощів, яких можна уникнути. Згодом цей алгоритм став, на мій превеликий подив, одним із наріжних каменів моєї слави».

Дейкстра думав про проблему найкоротшого шляху, працюючи програмістом у Математичному центрі в Амстердамі в 1956 році, щоб проілюструвати можливості нового комп’ютера, відомого як ARMAC. Його мета полягала в тому, щоб вибрати як проблему, так і рішення (вироблене комп’ютером), які люди, які не мають комп’ютерного досвіду, могли б зрозуміти. Він розробив алгоритм найкоротшого шляху та пізніше виконав його для ARMAC для нечітко скороченої транспортної карти 64 міст у Нідерландах (64 міста, тому 6 біт було б достатньо для кодування номера міста). Через рік він зіткнувся з іншою проблемою від інженерів апаратного забезпечення, які керували наступним комп’ютером інституту: зведіть до мінімуму кількість дроту, необхідного для з’єднання контактів на задній панелі машини. Як рішення він заново відкрив алгоритм під назвою «алгоритм мінімального остовного дерева Прима» та опублікував його в 1959 році.

Основи алгоритму Дейкстри

Нижче наведені основні концепції алгоритму Дейкстри:

Алгоритм Дейкстри починається з вузла, який ми вибираємо (вихідний вузол), і він перевіряє граф, щоб знайти найкоротший шлях між цим вузлом та всіма іншими вузлами на графі.
Алгоритм зберігає записи поточної визнаної найкоротшої відстані від кожного вузла до вихідного вузла та оновлює ці значення, якщо знаходить будь-який коротший шлях.
Після того, як алгоритм знайде найкоротший шлях між джерелом та іншим вузлом, цей вузол позначається як «відвіданий» і включається в шлях.
Процедура триває, доки всі вузли в графі не будуть включені в шлях. Таким чином ми маємо шлях, що з’єднує вихідний вузол з усіма іншими вузлами, дотримуючись найкоротшого можливого шляху до кожного вузла.

Розуміння роботи алгоритму Дейкстри

А графік і вихідна вершина є вимогами до алгоритму Дейкстри. Цей алгоритм заснований на жадібному підході і, таким чином, знаходить локально оптимальний вибір (у цьому випадку локальні мінімуми) на кожному кроці алгоритму.

Кожна Вершина в цьому Алгоритмі матиме дві визначені властивості:

Відвідав власність
Властивість шляху

Коротко розберемо ці властивості.

Відвідане майно:

Властивість 'visited' означає, чи був вузол відвіданий.
Ми використовуємо цю властивість, щоб не переглядати жодного вузла.
Вузол позначається як відвіданий лише тоді, коли знайдено найкоротший шлях.

Властивість шляху:

Властивість 'path' зберігає значення поточного мінімального шляху до вузла.
Поточний мінімальний шлях передбачає найкоротший шлях, яким ми досягли цього вузла досі.
Ця властивість переглядається, коли відвідується будь-який сусід вузла.
Ця властивість є важливою, оскільки вона зберігатиме остаточну відповідь для кожного вузла.

Спочатку ми позначаємо всі вершини або вузли як невідвідані, оскільки їх ще потрібно відвідати. Шлях до всіх вузлів також встановлено на нескінченність, окрім вихідного вузла. Крім того, шлях до вихідного вузла встановлюється на нуль (0).

Потім ми вибираємо вихідний вузол і позначаємо його як відвіданий. Після цього ми отримуємо доступ до всіх сусідніх вузлів вихідного вузла та виконуємо релаксацію на кожному вузлі. Релаксація - це процес зниження вартості досягнення вузла за допомогою іншого вузла.

У процесі релаксації шлях кожного вузла переглядається до мінімального значення серед поточного шляху вузла, суми шляху до попереднього вузла та шляху від попереднього вузла до поточного вузла.

Припустимо, що p[n] — це значення поточного шляху для вузла n, p[m] — це значення шляху до попередньо відвіданого вузла m, а w — вага ребра між поточним вузлом і раніше відвіданий (вага краю між n і m).

У математичному сенсі релаксацію можна проілюструвати так:

p[n] = мінімум (p[n], p[m] + w)

Потім ми позначаємо невідвіданий вузол із найменшим шляхом як відвіданий на кожному наступному кроці та оновлюємо шляхи його сусідів.

Ми повторюємо цю процедуру, доки всі вузли на графіку не будуть позначені як відвідані.

Щоразу, коли ми додаємо вузол до відвіданого набору, шлях до всіх його сусідніх вузлів також змінюється відповідно.

Якщо будь-який вузол залишається недосяжним (відключений компонент), його шлях залишається «нескінченним». Якщо сам джерело є окремим компонентом, то шлях до всіх інших вузлів залишається «нескінченним».

Розуміння алгоритму Дейкстри на прикладі

Нижче наведено крок, який ми виконаємо для реалізації алгоритму Дейкстри:

Крок 1: Спочатку ми позначимо вихідний вузол поточною відстанню 0 і встановимо решту вузлів на НЕСКІНЧЕННІ.

Крок 2: Потім ми встановимо невідвіданий вузол із найменшою поточною відстанню як поточний вузол, припустимо, X.

крок 3: Для кожного сусіда N поточного вузла X: потім ми додамо поточну відстань X із вагою ребра, що з’єднує X-N. Якщо вона менша за поточну відстань N, встановіть її як нову поточну відстань N.

веб-сайти з фільмами, схожі на 123movies

крок 4: Потім ми позначимо поточний вузол X як відвіданий.

крок 5: Ми повторимо процес з 'Крок 2' якщо на графіку залишився невідвіданий вузол.

Тепер розберемося з реалізацією алгоритму на прикладі:

Малюнок 6: Заданий граф

Ми будемо використовувати наведений вище графік як вхідні дані з вузлом А як джерело.
Спочатку ми позначимо всі вузли як невідвідані.
Ми встановимо шлях до 0 у вузлі А і НЕСКІНЧЕННІСТЬ для всіх інших вузлів.
Тепер ми позначимо вихідний вузол А як відвіданий і отримати доступ до сусідніх вузлів.
Примітка: Ми лише отримали доступ до сусідніх вузлів, а не відвідали їх.
Тепер ми оновимо шлях до вузла Б за 4 за допомогою релаксації, оскільки шлях до вузла А є 0 і шлях від вузла А до Б є 4 , і мінімум ((0 + 4), НЕСКІНЧЕННІ) є 4 .
Ми також оновимо шлях до вузла C за 5 за допомогою релаксації, оскільки шлях до вузла А є 0 і шлях від вузла А до C є 5 , і мінімум((0 + 5), НЕСКІНЧЕННІСТЬ) є 5 . Обидва сусіди вузла А тепер розслаблені; тому ми можемо рухатися вперед.
Тепер ми виберемо наступний невідвіданий вузол із найменшим шляхом і відвідаємо його. Отже, ми відвідаємо node Б і здійснити релаксацію на своїх невідвіданих сусідах. Після виконання релаксації шлях до вузла C залишиться 5 , тоді як шлях до вузла І стане одинадцять і шлях до вузла Д стане 13 .
Зараз ми відвідаємо вузол І і виконати релаксацію на сусідніх вузлах B, D , і Ф . Оскільки тільки вузол Ф не відвідуваний, буде розслаблено. Таким чином, шлях до вузла Б залишиться як є, тобто 4 , шлях до вузла Д також залишиться 13 і шлях до вузла Ф стане 14 (8 + 6) .
Зараз ми відвідаємо вузол Д , і тільки вузол Ф буде розслаблено. Однак шлях до вузла Ф залишиться без змін, тобто 14 .
Оскільки тільки вузол Ф залишається, ми відвідаємо його, але не будемо виконувати будь-яку релаксацію, оскільки всі його сусідні вузли вже відвідані.
Після відвідування всіх вузлів графіків програма завершиться.

Отже, остаточні шляхи, які ми дійшли, такі:

 A = 0 B = 4 (A -&gt; B) C = 5 (A -&gt; C) D = 4 + 9 = 13 (A -&gt; B -&gt; D) E = 5 + 3 = 8 (A -&gt; C -&gt; E) F = 5 + 3 + 6 = 14 (A -&gt; C -&gt; E -&gt; F)

Псевдокод для алгоритму Дейкстри

Тепер ми розберемося з псевдокодом для алгоритму Дейкстри.

Ми повинні вести запис про відстань шляху кожного вузла. Таким чином, ми можемо зберегти відстань шляху кожного вузла в масиві розміром n, де n — загальна кількість вузлів.
Крім того, ми хочемо отримати найкоротший шлях разом із довжиною цього шляху. Щоб подолати цю проблему, ми зіставимо кожен вузол з вузлом, який останнім оновив довжину свого шляху.
Після завершення алгоритму ми можемо відстежити вузол призначення до вузла джерела, щоб отримати шлях.
Ми можемо використовувати чергу з мінімальним пріоритетом, щоб отримати вузол із найменшою відстанню шляху ефективним способом.

Давайте тепер реалізуємо псевдокод наведеної вище ілюстрації:

Псевдокод:

 function Dijkstra_Algorithm(Graph, source_node) // iterating through the nodes in Graph and set their distances to INFINITY for each node N in Graph: distance[N] = INFINITY previous[N] = NULL If N != source_node, add N to Priority Queue G // setting the distance of the source node of the Graph to 0 distance[source_node] = 0 // iterating until the Priority Queue G is not empty while G is NOT empty: // selecting a node Q having the least distance and marking it as visited Q = node in G with the least distance[] mark Q visited // iterating through the unvisited neighboring nodes of the node Q and performing relaxation accordingly for each unvisited neighbor node N of Q: temporary_distance = distance[Q] + distance_between(Q, N) // if the temporary distance is less than the given distance of the path to the Node, updating the resultant distance with the minimum value if temporary_distance <distance[n] distance[n] :="temporary_distance" previous[n] returning the final list of distance return distance[], previous[] < pre> <p> <strong>Explanation:</strong> </p> <p>In the above pseudocode, we have defined a function that accepts multiple parameters - the Graph consisting of the nodes and the source node. Inside this function, we have iterated through each node in the Graph, set their initial distance to <strong>INFINITY</strong> , and set the previous node value to <strong>NULL</strong> . We have also checked whether any selected node is not a source node and added the same into the Priority Queue. Moreover, we have set the distance of the source node to <strong>0</strong> . We then iterated through the nodes in the priority queue, selected the node with the least distance, and marked it as visited. We then iterated through the unvisited neighboring nodes of the selected node and performed relaxation accordingly. At last, we have compared both the distances (original and temporary distance) between the source node and the destination node, updated the resultant distance with the minimum value and previous node information, and returned the final list of distances with their previous node information.</p> <h2>Implementation of Dijkstra&apos;s Algorithm in Different Programming Languages</h2> <p>Now that we have successfully understood the pseudocode of Dijkstra&apos;s Algorithm, it is time to see its implementation in different programming languages like C, C++, Java, and Python.</p> <h3>Code for Dijkstra&apos;s Algorithm in C</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the C Programming Language:</p> <p> <strong>File: DijkstraAlgorithm.c</strong> </p> <pre> // Implementation of Dijkstra&apos;s Algorithm in C // importing the standard I/O header file #include // defining some constants #define INF 9999 #define MAX 10 // prototyping of the function void DijkstraAlgorithm(int Graph[MAX][MAX], int size, int start); // defining the function for Dijkstra&apos;s Algorithm void DijkstraAlgorithm(int Graph[MAX][MAX], int size, int start) { int cost[MAX][MAX], distance[MAX], previous[MAX]; int visited_nodes[MAX], counter, minimum_distance, next_node, i, j; // creating cost matrix for (i = 0; i <size; i++) for (j="0;" j < size; j++) if (graph[i][j]="=" 0) cost[i][j]="INF;" else (i="0;" i { distance[i]="cost[start][i];" previous[i]="start;" visited_nodes[i]="0;" } distance[start]="0;" visited_nodes[start]="1;" counter="1;" while (counter size - 1) minimum_distance="INF;" (distance[i] && !visited_nodes[i]) next_node="i;" visited_nodes[next_node]="1;" (!visited_nodes[i]) (minimum_distance + cost[next_node][i] distance[i]) cost[next_node][i]; counter++; printing the distance !="start)" printf('
distance from source node to %d: %d', i, distance[i]); main function int main() defining variables graph[max][max], j, size, source; declaring of matrix nodes graph graph[0][0]="0;" graph[0][1]="4;" graph[0][2]="0;" graph[0][3]="0;" graph[0][4]="0;" graph[0][5]="8;" graph[0][6]="0;" graph[1][0]="4;" graph[1][1]="0;" graph[1][2]="8;" graph[1][3]="0;" graph[1][4]="0;" graph[1][5]="11;" graph[1][6]="0;" graph[2][0]="0;" graph[2][1]="8;" graph[2][2]="0;" graph[2][3]="7;" graph[2][4]="0;" graph[2][5]="4;" graph[2][6]="0;" graph[3][0]="0;" graph[3][1]="0;" graph[3][2]="7;" graph[3][3]="0;" graph[3][4]="9;" graph[3][5]="14;" graph[3][6]="0;" graph[4][0]="0;" graph[4][1]="0;" graph[4][2]="0;" graph[4][3]="9;" graph[4][4]="0;" graph[4][5]="10;" graph[4][6]="2;" graph[5][0]="0;" graph[5][1]="0;" graph[5][2]="4;" graph[5][3]="14;" graph[5][4]="10;" graph[5][5]="0;" graph[5][6]="2;" graph[6][0]="0;" graph[6][1]="0;" graph[6][2]="0;" graph[6][3]="0;" graph[6][4]="2;" graph[6][5]="0;" graph[6][6]="1;" calling dijkstraalgorithm() by passing graph, number and dijkstraalgorithm(graph, source); return 0; pre> <p> <strong>Output</strong> </p> <pre> Distance from the Source Node to 1: 4 Distance from the Source Node to 2: 12 Distance from the Source Node to 3: 19 Distance from the Source Node to 4: 12 Distance from the Source Node to 5: 8 Distance from the Source Node to 6: 10 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have included the <strong>stdio.h</strong> header file defined two constant values: <strong>INF = 9999</strong> and <strong>MAX = 10</strong> . We have declared the prototyping of the function and then defined the function for Dijkstra&apos;s Algorithm as <strong>DijkstraAlgorithm</strong> that accepts three arguments - the Graph consisting of the nodes, the number of nodes in the Graph, and the source node. Inside this function, we have defined some data structures such as a 2D matrix that will work as the Priority Queue for the algorithm, an array to main the distance between the nodes, an array to maintain the record of previous nodes, an array to store the visited nodes information, and some integer variables to store minimum distance value, counter, next node value and more. We then used a <strong>nested for-loop</strong> to iterate through the nodes of the Graph and add them to the priority queue accordingly. We have again used the <strong>for-loop</strong> to iterate through the elements in the priority queue starting from the source node and update their distances. Outside the loop, we have set the distance of the source node as <strong>0</strong> and marked it as visited in the <strong>visited_nodes[]</strong> array. We then set the counter value as one and used the <strong>while</strong> loop iterating through the number of nodes. Inside this loop, we have set the value of <strong>minimum_distance</strong> as <strong>INF</strong> and used the <strong>for-loop</strong> to update the value of the <strong>minimum_distance</strong> variable with the minimum value from a <strong>distance[]</strong> array. We then iterated through the unvisited neighboring nodes of the selected node using the <strong>for-loop</strong> and performed relaxation. We then printed the resulting data of the distances calculated using Dijkstra&apos;s Algorithm.</p> <p>In the <strong>main</strong> function, we have defined and declared the variables representing the Graph, the number of nodes, and the source node. At last, we have called the <strong>DijkstraAlgorithm()</strong> function by passing the required parameters.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h3>Code for Dijkstra&apos;s Algorithm in C++</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the C++ Programming Language:</p> <p> <strong>File: DijkstraAlgorithm.cpp</strong> </p> <pre> // Implementation of Dijkstra&apos;s Algorithm in C++ // importing the required header files #include #include // defining constant #define MAX_INT 10000000 // using the standard namespace using namespace std; // prototyping of the DijkstraAlgorithm() function void DijkstraAlgorithm(); // main function int main() { DijkstraAlgorithm(); return 0; } // declaring the classes class Vertex; class Edge; // prototyping the functions void Dijkstra(); vector* Adjacent_Remaining_Nodes(Vertex* vertex); Vertex* Extract_Smallest(vector&amp; vertices); int Distance(Vertex* vertexOne, Vertex* vertexTwo); bool Contains(vector&amp; vertices, Vertex* vertex); void Print_Shortest_Route_To(Vertex* des); // instantiating the classes vector vertices; vector edges; // defining the class for the vertices of the graph class Vertex { public: Vertex(char id) : id(id), prev(NULL), distance_from_start(MAX_INT) { vertices.push_back(this); } public: char id; Vertex* prev; int distance_from_start; }; // defining the class for the edges of the graph class Edge { public: Edge(Vertex* vertexOne, Vertex* vertexTwo, int distance) : vertexOne(vertexOne), vertexTwo(vertexTwo), distance(distance) { edges.push_back(this); } bool Connects(Vertex* vertexOne, Vertex* vertexTwo) public: Vertex* vertexOne; Vertex* vertexTwo; int distance; }; // defining the function to collect the details of the graph void DijkstraAlgorithm() { // declaring some vertices Vertex* vertex_a = new Vertex(&apos;A&apos;); Vertex* vertex_b = new Vertex(&apos;B&apos;); Vertex* vertex_c = new Vertex(&apos;C&apos;); Vertex* vertex_d = new Vertex(&apos;D&apos;); Vertex* vertex_e = new Vertex(&apos;E&apos;); Vertex* vertex_f = new Vertex(&apos;F&apos;); Vertex* vertex_g = new Vertex(&apos;G&apos;); // declaring some edges Edge* edge_1 = new Edge(vertex_a, vertex_c, 1); Edge* edge_2 = new Edge(vertex_a, vertex_d, 2); Edge* edge_3 = new Edge(vertex_b, vertex_c, 2); Edge* edge_4 = new Edge(vertex_c, vertex_d, 1); Edge* edge_5 = new Edge(vertex_b, vertex_f, 3); Edge* edge_6 = new Edge(vertex_c, vertex_e, 3); Edge* edge_7 = new Edge(vertex_e, vertex_f, 2); Edge* edge_8 = new Edge(vertex_d, vertex_g, 1); Edge* edge_9 = new Edge(vertex_g, vertex_f, 1); vertex_a -&gt; distance_from_start = 0; // setting a start vertex // calling the Dijkstra() function to find the shortest route possible Dijkstra(); // calling the Print_Shortest_Route_To() function to print the shortest route from the source vertex to the destination vertex Print_Shortest_Route_To(vertex_f); } // defining the function for Dijkstra&apos;s Algorithm void Dijkstra() { while (vertices.size() &gt; 0) { Vertex* smallest = Extract_Smallest(vertices); vector* adjacent_nodes = Adjacent_Remaining_Nodes(smallest); const int size = adjacent_nodes -&gt; size(); for (int i = 0; i at(i); int distance = Distance(smallest, adjacent) + smallest -&gt; distance_from_start; if (distance distance_from_start) { adjacent -&gt; distance_from_start = distance; adjacent -&gt; prev = smallest; } } delete adjacent_nodes; } } // defining the function to find the vertex with the shortest distance, removing it, and returning it Vertex* Extract_Smallest(vector&amp; vertices) { int size = vertices.size(); if (size == 0) return NULL; int smallest_position = 0; Vertex* smallest = vertices.at(0); for (int i = 1; i distance_from_start distance_from_start) { smallest = current; smallest_position = i; } } vertices.erase(vertices.begin() + smallest_position); return smallest; } // defining the function to return all vertices adjacent to &apos;vertex&apos; which are still in the &apos;vertices&apos; collection. vector* Adjacent_Remaining_Nodes(Vertex* vertex) { vector* adjacent_nodes = new vector(); const int size = edges.size(); for (int i = 0; i vertexOne == vertex) { adjacent = edge -&gt; vertexTwo; } else if (edge -&gt; vertexTwo == vertex) { adjacent = edge -&gt; vertexOne; } if (adjacent &amp;&amp; Contains(vertices, adjacent)) { adjacent_nodes -&gt; push_back(adjacent); } } return adjacent_nodes; } // defining the function to return distance between two connected vertices int Distance(Vertex* vertexOne, Vertex* vertexTwo) { const int size = edges.size(); for (int i = 0; i Connects(vertexOne, vertexTwo)) { return edge -&gt; distance; } } return -1; // should never happen } // defining the function to check if the &apos;vertices&apos; vector contains &apos;vertex&apos; bool Contains(vector&amp; vertices, Vertex* vertex) { const int size = vertices.size(); for (int i = 0; i <size; ++i) { if (vertex="=" vertices.at(i)) return true; } false; defining the function to print shortest route destination void print_shortest_route_to(vertex* des) vertex* prev="des;" cout << 'distance from start: ' < distance_from_start endl; while (prev) id prev; pre> <p> <strong>Output</strong> </p> <pre> Distance from start: 4 F G D A </pre> <p> <strong>Explanation:</strong> </p> <p>In the above code snippet, we included the <strong>&apos;iostream&apos;</strong> and <strong>&apos;vector&apos;</strong> header files and defined a constant value as <strong>MAX_INT = 10000000</strong> . We then used the standard namespace and prototyped the <strong>DijkstraAlgorithm()</strong> function. We then defined the main function of the program within, which we have called the <strong>DijkstraAlgorithm()</strong> function. After that, we declared some classes to create vertices and edges. We have also prototyped more functions to find the shortest possible path from the source vertex to the destination vertex and instantiated the Vertex and Edge classes. We then defined both classes to create the vertices and edges of the graph. We have then defined the <strong>DijkstraAlgorithm()</strong> function to create a graph and perform different operations. Inside this function, we have declared some vertices and edges. We then set the source vertex of the graph and called the <strong>Dijkstra()</strong> function to find the shortest possible distance and <strong>Print_Shortest_Route_To()</strong> function to print the shortest distance from the source vertex to vertex <strong>&apos;F&apos;</strong> . We have then defined the <strong>Dijkstra()</strong> function to calculate the shortest possible distances of the all the vertices from the source vertex. We have also defined some more functions to find the vertex with the shortest distance to return all the vertices adjacent to the remaining vertex, to return the distance between two connected vertices, to check if the selected vertex exists in the graph, and to print the shortest possible path from the source vertex to the destination vertex.</p> <p>As a result, the required shortest path for the vertex <strong>&apos;F&apos;</strong> from the source node is printed for the users.</p> <h3>Code for Dijkstra&apos;s Algorithm in Java</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the Java Programming Language:</p> <p> <strong>File: DijkstraAlgorithm.java</strong> </p> <pre> // Implementation of Dijkstra&apos;s Algorithm in Java // defining the public class for Dijkstra&apos;s Algorithm public class DijkstraAlgorithm { // defining the method to implement Dijkstra&apos;s Algorithm public void dijkstraAlgorithm(int[][] graph, int source) { // number of nodes int nodes = graph.length; boolean[] visited_vertex = new boolean[nodes]; int[] dist = new int[nodes]; for (int i = 0; i <nodes; 0 1 i++) { visited_vertex[i]="false;" dist[i]="Integer.MAX_VALUE;" } distance of self loop is zero dist[source]="0;" for (int i="0;" < nodes; updating the between neighboring vertex and source int u="find_min_distance(dist," visited_vertex); visited_vertex[u]="true;" distances all vertices v="0;" v++) if (!visited_vertex[v] && graph[u][v] !="0" (dist[u] + dist[v])) dist[v]="dist[u]" graph[u][v]; dist.length; system.out.println(string.format('distance from %s to %s', source, i, dist[i])); defining method find minimum private static find_min_distance(int[] dist, boolean[] visited_vertex) minimum_distance="Integer.MAX_VALUE;" minimum_distance_vertex="-1;" (!visited_vertex[i] minimum_distance) return minimum_distance_vertex; main function public void main(string[] args) declaring nodes graphs graph[][]="new" int[][] 0, 1, 2, }, 3, }; instantiating dijkstraalgorithm() class dijkstraalgorithm test="new" dijkstraalgorithm(); calling shortest node destination test.dijkstraalgorithm(graph, 0); pre> <p> <strong>Output</strong> </p> <pre> Distance from Vertex 0 to Vertex 0 is 0 Distance from Vertex 0 to Vertex 1 is 1 Distance from Vertex 0 to Vertex 2 is 1 Distance from Vertex 0 to Vertex 3 is 2 Distance from Vertex 0 to Vertex 4 is 4 Distance from Vertex 0 to Vertex 5 is 4 Distance from Vertex 0 to Vertex 6 is 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have defined a public class as <strong>DijkstraAlgorithm()</strong> . Inside this class, we have defined a public method as <strong>dijkstraAlgorithm()</strong> to find the shortest distance from the source vertex to the destination vertex. Inside this method, we have defined a variable to store the number of nodes. We have then defined a Boolean array to store the information regarding the visited vertices and an integer array to store their respective distances. Initially, we declared the values in both the arrays as <strong>False</strong> and <strong>MAX_VALUE</strong> , respectively. We have also set the distance of the source vertex as zero and used the <strong>for-loop</strong> to update the distance between the source vertex and destination vertices with the minimum distance. We have then updated the distances of the neighboring vertices of the selected vertex by performing relaxation and printed the shortest distances for every vertex. We have then defined a method to find the minimum distance from the source vertex to the destination vertex. We then defined the main function where we declared the vertices of the graph and instantiated the <strong>DijkstraAlgorithm()</strong> class. Finally, we have called the <strong>dijkstraAlgorithm()</strong> method to find the shortest distance between the source vertex and the destination vertices.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h3>Code for Dijkstra&apos;s Algorithm in Python</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the Python Programming Language:</p> <p> <strong>File: DikstraAlgorithm.py</strong> </p> <pre> # Implementation of Dijkstra&apos;s Algorithm in Python # importing the sys module import sys # declaring the list of nodes for the graph nodes = [ [0, 0, 1, 0, 1, 0, 0], [0, 0, 1, 0, 0, 1, 0], [1, 1, 0, 1, 1, 0, 0], [1, 0, 1, 0, 0, 0, 1], [0, 0, 1, 0, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # declaring the list of edges for the graph edges = [ [0, 0, 1, 0, 2, 0, 0], [0, 0, 2, 0, 0, 3, 0], [1, 2, 0, 1, 3, 0, 0], [2, 0, 1, 0, 0, 0, 1], [0, 0, 3, 0, 0, 2, 0], [0, 3, 0, 0, 2, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # defining the function to find which node is to be visited next def toBeVisited(): global visitedAndDistance v = -10 for index in range(numberOfNodes): if visitedAndDistance[index][0] == 0 and (v <0 1 or visitedanddistance[index][1] <="visitedAndDistance[v][1]):" v="index" return # finding the number of nodes in graph numberofnodes="len(nodes[0])" visitedanddistance="[[0," 0]] for i range(numberofnodes - 1): visitedanddistance.append([0, sys.maxsize]) node range(numberofnodes): next to be visited tovisit="toBeVisited()" neighborindex updating new distances if nodes[tovisit][neighborindex]="=" and visitedanddistance[neighborindex][0]="=" 0: newdistance="visitedAndDistance[toVisit][1]" + edges[tovisit][neighborindex] visitedanddistance[neighborindex][1]> newDistance: visitedAndDistance[neighborIndex][1] = newDistance visitedAndDistance[toVisit][0] = 1 i = 0 # printing the distance for distance in visitedAndDistance: print(&apos;Distance of&apos;, chr(ord(&apos;A&apos;) + i), &apos;from source node:&apos;, distance[1]) i = i + 1 </0></pre> <p> <strong>Output</strong> </p> <pre> Distance of A from source node: 0 Distance of B from source node: 3 Distance of C from source node: 1 Distance of D from source node: 2 Distance of E from source node: 2 Distance of F from source node: 4 Distance of G from source node: 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have imported the <strong>sys</strong> module and declared the lists consisting of the values for the nodes and edges. We have then defined a function as <strong>toBeVisited()</strong> to find which node will be visited next. We then found the total number of nodes in the graph and set the initial distances for every node. We have then calculated the minimum distance from the source node to the destination node, performed relaxation on neighboring nodes, and updated the distances in the list. We then printed those distances from the list for the users.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h2>Time and Space Complexity of Dijkstra&apos;s Algorithm</h2> <ul> <li>The Time Complexity of Dijkstra&apos;s Algorithm is <strong>O(E log V)</strong> , where E is the number of edges and V is the number of vertices.</li> <li>The Space Complexity of Dijkstra&apos;s Algorithm is O(V), where V is the number of vertices.</li> </ul> <h2>Advantages and Disadvantages of Dijkstra&apos;s Algorithm</h2> <p> <strong>Let us discuss some advantages of Dijkstra&apos;s Algorithm:</strong> </p> <ol class="points"> <li>One primary advantage of using Dijkstra&apos;s Algorithm is that it has an almost linear time and space complexity.</li> <li>We can use this algorithm to calculate the shortest path from a single vertex to all other vertices and a single source vertex to a single destination vertex by stopping the algorithm once we get the shortest distance for the destination vertex.</li> <li>This algorithm only works for directed weighted graphs, and all the edges of this graph should be non-negative.</li> </ol> <p> <strong>Despite having multiple advantages, Dijkstra&apos;s algorithm has some disadvantages also, such as:</strong> </p> <ol class="points"> <li>Dijkstra&apos;s Algorithm performs a concealed exploration that utilizes a lot of time during the process.</li> <li>This algorithm is impotent to handle negative edges.</li> <li>Since this algorithm heads to the acyclic graph, it cannot calculate the exact shortest path.</li> <li>It also requires maintenance to keep a record of vertices that have been visited.</li> </ol> <h2>Some Applications of Dijkstra&apos;s Algorithm</h2> <p> <strong>Dijkstra&apos;s Algorithm has various real-world applications, some of which are stated below:</strong> </p> <ol class="points"> <tr><td>Digital Mapping Services in Google Maps:</td> There are various times when we have tried to find the distance in Google Maps either from our location to the nearest preferred location or from one city to another, which comprises multiple routes/paths connecting them; however, the application must display the minimum distance. This is only possible because Dijkstra&apos;s algorithm helps the application find the shortest between two given locations along the path. Let us consider the USA as a graph wherein the cities/places are represented as vertices, and the routes between two cities/places are represented as edges. Then with the help of Dijkstra&apos;s Algorithm, we can calculate the shortest routes between any two cities/places. </tr><tr><td>Social Networking Applications:</td> In many applications like Facebook, Twitter, Instagram, and more, many of us might have observed that these apps suggest the list of friends that a specific user may know. How do many social media companies implement this type of feature in an efficient and effective way, specifically when the system has over a billion users? The answer to this question is Dijkstra&apos;s Algorithm. The standard Dijkstra&apos;s Algorithm is generally used to estimate the shortest distance between the users measured through the connections or mutuality among them. When social networking is very small, it uses the standard Dijkstra&apos;s Algorithm in addition to some other features in order to determine the shortest paths. However, when the graph is much bigger, the standard algorithm takes several seconds to count, and thus, some advanced algorithms are used as the alternative. </tr><tr><td>Telephone Network:</td> As some of us might know, in a telephone network, each transmission line has a bandwidth, &apos;b&apos;. The bandwidth is the highest frequency that the transmission line can support. In general, if the frequency of the signal is higher in a specific line, the signal is reduced by that line. Bandwidth represents the amount of information that can be transmitted by the line. Let us consider a city a graph wherein the switching stations are represented using the vertices, the transmission lines are represented as the edges, and the bandwidth, &apos;b&apos;, is represented using the weight of the edges. Thus, as we can observe, the telephone network can also fall into the category of the shortest distance problem and can be solved using Dijkstra&apos;s Algorithm. </tr><tr><td>Flight Program:</td> Suppose that a person requires software to prepare an agenda of flights for customers. The agent has access to a database with all flights and airports. In addition to the flight number, origin airport, and destination, the flights also have departure and arrival times. So, in order to determine the earliest arrival time for the selected destination from the original airport and given start time, the agents make use of Dijkstra&apos;s Algorithm. </tr><tr><td>IP routing to find Open Shortest Path First:</td> Open Shortest Path First (abbreviated as OSPF) is a link-state routing protocol used to find the best path between the source and destination router with the help of its own Shortest Path First. Dijkstra&apos;s Algorithm is extensively utilized in the routing protocols required by the routers in order to update their forwarding table. The algorithm gives the shortest cost path from the source router to the other routers present in the network. </tr><tr><td>Robotic Path:</td> These days, drones and robots have come into existence, some operated manually and some automatically. The drones and robots which are operated automatically and used to deliver the packages to a given location or used for any certain task are configured with Dijkstra&apos;s Algorithm module so that whenever the source and destination are known, the drone and robot will move in the ordered direction by following the shortest path keeping the time taken to a minimum in order to deliver the packages. </tr><tr><td>Designate the File Server:</td> Dijkstra&apos;s Algorithm is also used to designate a file server in a Local Area Network (LAN). Suppose that an infinite period of time is needed for the transmission of the files from one computer to another. So, to minimize the number of &apos;hops&apos; from the file server to every other computer on the network, we will use Dijkstra&apos;s Algorithm. This algorithm will return the shortest path between the networks resulting in the minimum number of hops. </tr></ol> <h2>The Conclusion</h2> <ul> <li>In the above tutorial, firstly, we have understood the basic concepts of Graph along with its types and applications.</li> <li>We then learned about Dijkstra&apos;s Algorithm and its history.</li> <li>We have also understood the fundamental working of Dijkstra&apos;s Algorithm with the help of an example.</li> <li>After that, we studied how to write code for Dijkstra&apos;s Algorithm with the help of Pseudocode.</li> <li>We observed its implementation in programming languages like C, C++, Java, and Python with proper outputs and explanations.</li> <li>We have also understood the Time and Space Complexity of Dijkstra&apos;s Algorithm.</li> <li>Finally, we have discussed the advantages and disadvantages of Dijkstra&apos;s algorithm and some of its real-life applications.</li> </ul> <hr></nodes;></pre></size;></pre></size;></pre></distance[n]>

Пояснення:

У наведений вище фрагмент коду ми включили stdio.h файл заголовка визначив два постійні значення: INF = 9999 і МАКС = 10 . Ми оголосили прототип функції, а потім визначили функцію для алгоритму Дейкстри як Алгоритм Дейкстри який приймає три аргументи – Граф, що складається з вузлів, кількість вузлів у Графі та вихідний вузол. У цій функції ми визначили деякі структури даних, такі як двовимірна матриця, яка працюватиме як пріоритетна черга для алгоритму, масив для визначення відстані між вузлами, масив для збереження запису попередніх вузлів, масив для зберігання інформація про відвідані вузли та деякі цілі змінні для збереження мінімального значення відстані, лічильника, значення наступного вузла тощо. Тоді ми використали a вкладений цикл for щоб перебирати вузли Graph і відповідно додавати їх до черги пріоритетів. Ми знову використали цикл for щоб перебирати елементи в черзі пріоритетів, починаючи з вихідного вузла, і оновлювати їх відстані. За межами циклу ми встановили відстань вихідного вузла як 0 і позначив його як відвіданий у відвідані_вузли[] масив. Потім ми встановили значення лічильника як одиницю та використали поки цикл, що перебирає кількість вузлів. Усередині цього циклу ми встановили значення мінімальна_відстань як ІНФ і використовував цикл for щоб оновити значення мінімальна_відстань змінна з мінімальним значенням від a відстань[] масив. Потім ми повторили невідвідані сусідні вузли вибраного вузла за допомогою цикл for і виконав релаксацію. Потім ми надрукували отримані дані про відстані, розраховані за допомогою алгоритму Дейкстри.

В основний ми визначили й оголосили змінні, що представляють граф, кількість вузлів і вихідний вузол. Нарешті ми подзвонили Алгоритм Дейкстра() передаючи необхідні параметри.

У результаті для користувачів друкуються необхідні найкоротші шляхи для кожного вузла з вихідного вузла.

Код для алгоритму Дейкстри в C++

Нижче наведено реалізацію алгоритму Дейкстри на мові програмування C++:

Файл: DijkstraAlgorithm.cpp

 // Implementation of Dijkstra&apos;s Algorithm in C++ // importing the required header files #include #include // defining constant #define MAX_INT 10000000 // using the standard namespace using namespace std; // prototyping of the DijkstraAlgorithm() function void DijkstraAlgorithm(); // main function int main() { DijkstraAlgorithm(); return 0; } // declaring the classes class Vertex; class Edge; // prototyping the functions void Dijkstra(); vector* Adjacent_Remaining_Nodes(Vertex* vertex); Vertex* Extract_Smallest(vector&amp; vertices); int Distance(Vertex* vertexOne, Vertex* vertexTwo); bool Contains(vector&amp; vertices, Vertex* vertex); void Print_Shortest_Route_To(Vertex* des); // instantiating the classes vector vertices; vector edges; // defining the class for the vertices of the graph class Vertex { public: Vertex(char id) : id(id), prev(NULL), distance_from_start(MAX_INT) { vertices.push_back(this); } public: char id; Vertex* prev; int distance_from_start; }; // defining the class for the edges of the graph class Edge { public: Edge(Vertex* vertexOne, Vertex* vertexTwo, int distance) : vertexOne(vertexOne), vertexTwo(vertexTwo), distance(distance) { edges.push_back(this); } bool Connects(Vertex* vertexOne, Vertex* vertexTwo) public: Vertex* vertexOne; Vertex* vertexTwo; int distance; }; // defining the function to collect the details of the graph void DijkstraAlgorithm() { // declaring some vertices Vertex* vertex_a = new Vertex(&apos;A&apos;); Vertex* vertex_b = new Vertex(&apos;B&apos;); Vertex* vertex_c = new Vertex(&apos;C&apos;); Vertex* vertex_d = new Vertex(&apos;D&apos;); Vertex* vertex_e = new Vertex(&apos;E&apos;); Vertex* vertex_f = new Vertex(&apos;F&apos;); Vertex* vertex_g = new Vertex(&apos;G&apos;); // declaring some edges Edge* edge_1 = new Edge(vertex_a, vertex_c, 1); Edge* edge_2 = new Edge(vertex_a, vertex_d, 2); Edge* edge_3 = new Edge(vertex_b, vertex_c, 2); Edge* edge_4 = new Edge(vertex_c, vertex_d, 1); Edge* edge_5 = new Edge(vertex_b, vertex_f, 3); Edge* edge_6 = new Edge(vertex_c, vertex_e, 3); Edge* edge_7 = new Edge(vertex_e, vertex_f, 2); Edge* edge_8 = new Edge(vertex_d, vertex_g, 1); Edge* edge_9 = new Edge(vertex_g, vertex_f, 1); vertex_a -&gt; distance_from_start = 0; // setting a start vertex // calling the Dijkstra() function to find the shortest route possible Dijkstra(); // calling the Print_Shortest_Route_To() function to print the shortest route from the source vertex to the destination vertex Print_Shortest_Route_To(vertex_f); } // defining the function for Dijkstra&apos;s Algorithm void Dijkstra() { while (vertices.size() &gt; 0) { Vertex* smallest = Extract_Smallest(vertices); vector* adjacent_nodes = Adjacent_Remaining_Nodes(smallest); const int size = adjacent_nodes -&gt; size(); for (int i = 0; i at(i); int distance = Distance(smallest, adjacent) + smallest -&gt; distance_from_start; if (distance distance_from_start) { adjacent -&gt; distance_from_start = distance; adjacent -&gt; prev = smallest; } } delete adjacent_nodes; } } // defining the function to find the vertex with the shortest distance, removing it, and returning it Vertex* Extract_Smallest(vector&amp; vertices) { int size = vertices.size(); if (size == 0) return NULL; int smallest_position = 0; Vertex* smallest = vertices.at(0); for (int i = 1; i distance_from_start distance_from_start) { smallest = current; smallest_position = i; } } vertices.erase(vertices.begin() + smallest_position); return smallest; } // defining the function to return all vertices adjacent to &apos;vertex&apos; which are still in the &apos;vertices&apos; collection. vector* Adjacent_Remaining_Nodes(Vertex* vertex) { vector* adjacent_nodes = new vector(); const int size = edges.size(); for (int i = 0; i vertexOne == vertex) { adjacent = edge -&gt; vertexTwo; } else if (edge -&gt; vertexTwo == vertex) { adjacent = edge -&gt; vertexOne; } if (adjacent &amp;&amp; Contains(vertices, adjacent)) { adjacent_nodes -&gt; push_back(adjacent); } } return adjacent_nodes; } // defining the function to return distance between two connected vertices int Distance(Vertex* vertexOne, Vertex* vertexTwo) { const int size = edges.size(); for (int i = 0; i Connects(vertexOne, vertexTwo)) { return edge -&gt; distance; } } return -1; // should never happen } // defining the function to check if the &apos;vertices&apos; vector contains &apos;vertex&apos; bool Contains(vector&amp; vertices, Vertex* vertex) { const int size = vertices.size(); for (int i = 0; i <size; ++i) { if (vertex="=" vertices.at(i)) return true; } false; defining the function to print shortest route destination void print_shortest_route_to(vertex* des) vertex* prev="des;" cout << \'distance from start: \' < distance_from_start endl; while (prev) id prev; pre> <p> <strong>Output</strong> </p> <pre> Distance from start: 4 F G D A </pre> <p> <strong>Explanation:</strong> </p> <p>In the above code snippet, we included the <strong>&apos;iostream&apos;</strong> and <strong>&apos;vector&apos;</strong> header files and defined a constant value as <strong>MAX_INT = 10000000</strong> . We then used the standard namespace and prototyped the <strong>DijkstraAlgorithm()</strong> function. We then defined the main function of the program within, which we have called the <strong>DijkstraAlgorithm()</strong> function. After that, we declared some classes to create vertices and edges. We have also prototyped more functions to find the shortest possible path from the source vertex to the destination vertex and instantiated the Vertex and Edge classes. We then defined both classes to create the vertices and edges of the graph. We have then defined the <strong>DijkstraAlgorithm()</strong> function to create a graph and perform different operations. Inside this function, we have declared some vertices and edges. We then set the source vertex of the graph and called the <strong>Dijkstra()</strong> function to find the shortest possible distance and <strong>Print_Shortest_Route_To()</strong> function to print the shortest distance from the source vertex to vertex <strong>&apos;F&apos;</strong> . We have then defined the <strong>Dijkstra()</strong> function to calculate the shortest possible distances of the all the vertices from the source vertex. We have also defined some more functions to find the vertex with the shortest distance to return all the vertices adjacent to the remaining vertex, to return the distance between two connected vertices, to check if the selected vertex exists in the graph, and to print the shortest possible path from the source vertex to the destination vertex.</p> <p>As a result, the required shortest path for the vertex <strong>&apos;F&apos;</strong> from the source node is printed for the users.</p> <h3>Code for Dijkstra&apos;s Algorithm in Java</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the Java Programming Language:</p> <p> <strong>File: DijkstraAlgorithm.java</strong> </p> <pre> // Implementation of Dijkstra&apos;s Algorithm in Java // defining the public class for Dijkstra&apos;s Algorithm public class DijkstraAlgorithm { // defining the method to implement Dijkstra&apos;s Algorithm public void dijkstraAlgorithm(int[][] graph, int source) { // number of nodes int nodes = graph.length; boolean[] visited_vertex = new boolean[nodes]; int[] dist = new int[nodes]; for (int i = 0; i <nodes; 0 1 i++) { visited_vertex[i]="false;" dist[i]="Integer.MAX_VALUE;" } distance of self loop is zero dist[source]="0;" for (int i="0;" < nodes; updating the between neighboring vertex and source int u="find_min_distance(dist," visited_vertex); visited_vertex[u]="true;" distances all vertices v="0;" v++) if (!visited_vertex[v] && graph[u][v] !="0" (dist[u] + dist[v])) dist[v]="dist[u]" graph[u][v]; dist.length; system.out.println(string.format(\'distance from %s to %s\', source, i, dist[i])); defining method find minimum private static find_min_distance(int[] dist, boolean[] visited_vertex) minimum_distance="Integer.MAX_VALUE;" minimum_distance_vertex="-1;" (!visited_vertex[i] minimum_distance) return minimum_distance_vertex; main function public void main(string[] args) declaring nodes graphs graph[][]="new" int[][] 0, 1, 2, }, 3, }; instantiating dijkstraalgorithm() class dijkstraalgorithm test="new" dijkstraalgorithm(); calling shortest node destination test.dijkstraalgorithm(graph, 0); pre> <p> <strong>Output</strong> </p> <pre> Distance from Vertex 0 to Vertex 0 is 0 Distance from Vertex 0 to Vertex 1 is 1 Distance from Vertex 0 to Vertex 2 is 1 Distance from Vertex 0 to Vertex 3 is 2 Distance from Vertex 0 to Vertex 4 is 4 Distance from Vertex 0 to Vertex 5 is 4 Distance from Vertex 0 to Vertex 6 is 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have defined a public class as <strong>DijkstraAlgorithm()</strong> . Inside this class, we have defined a public method as <strong>dijkstraAlgorithm()</strong> to find the shortest distance from the source vertex to the destination vertex. Inside this method, we have defined a variable to store the number of nodes. We have then defined a Boolean array to store the information regarding the visited vertices and an integer array to store their respective distances. Initially, we declared the values in both the arrays as <strong>False</strong> and <strong>MAX_VALUE</strong> , respectively. We have also set the distance of the source vertex as zero and used the <strong>for-loop</strong> to update the distance between the source vertex and destination vertices with the minimum distance. We have then updated the distances of the neighboring vertices of the selected vertex by performing relaxation and printed the shortest distances for every vertex. We have then defined a method to find the minimum distance from the source vertex to the destination vertex. We then defined the main function where we declared the vertices of the graph and instantiated the <strong>DijkstraAlgorithm()</strong> class. Finally, we have called the <strong>dijkstraAlgorithm()</strong> method to find the shortest distance between the source vertex and the destination vertices.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h3>Code for Dijkstra&apos;s Algorithm in Python</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the Python Programming Language:</p> <p> <strong>File: DikstraAlgorithm.py</strong> </p> <pre> # Implementation of Dijkstra&apos;s Algorithm in Python # importing the sys module import sys # declaring the list of nodes for the graph nodes = [ [0, 0, 1, 0, 1, 0, 0], [0, 0, 1, 0, 0, 1, 0], [1, 1, 0, 1, 1, 0, 0], [1, 0, 1, 0, 0, 0, 1], [0, 0, 1, 0, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # declaring the list of edges for the graph edges = [ [0, 0, 1, 0, 2, 0, 0], [0, 0, 2, 0, 0, 3, 0], [1, 2, 0, 1, 3, 0, 0], [2, 0, 1, 0, 0, 0, 1], [0, 0, 3, 0, 0, 2, 0], [0, 3, 0, 0, 2, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # defining the function to find which node is to be visited next def toBeVisited(): global visitedAndDistance v = -10 for index in range(numberOfNodes): if visitedAndDistance[index][0] == 0 and (v <0 1 or visitedanddistance[index][1] <="visitedAndDistance[v][1]):" v="index" return # finding the number of nodes in graph numberofnodes="len(nodes[0])" visitedanddistance="[[0," 0]] for i range(numberofnodes - 1): visitedanddistance.append([0, sys.maxsize]) node range(numberofnodes): next to be visited tovisit="toBeVisited()" neighborindex updating new distances if nodes[tovisit][neighborindex]="=" and visitedanddistance[neighborindex][0]="=" 0: newdistance="visitedAndDistance[toVisit][1]" + edges[tovisit][neighborindex] visitedanddistance[neighborindex][1]> newDistance: visitedAndDistance[neighborIndex][1] = newDistance visitedAndDistance[toVisit][0] = 1 i = 0 # printing the distance for distance in visitedAndDistance: print(&apos;Distance of&apos;, chr(ord(&apos;A&apos;) + i), &apos;from source node:&apos;, distance[1]) i = i + 1 </0></pre> <p> <strong>Output</strong> </p> <pre> Distance of A from source node: 0 Distance of B from source node: 3 Distance of C from source node: 1 Distance of D from source node: 2 Distance of E from source node: 2 Distance of F from source node: 4 Distance of G from source node: 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have imported the <strong>sys</strong> module and declared the lists consisting of the values for the nodes and edges. We have then defined a function as <strong>toBeVisited()</strong> to find which node will be visited next. We then found the total number of nodes in the graph and set the initial distances for every node. We have then calculated the minimum distance from the source node to the destination node, performed relaxation on neighboring nodes, and updated the distances in the list. We then printed those distances from the list for the users.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h2>Time and Space Complexity of Dijkstra&apos;s Algorithm</h2> <ul> <li>The Time Complexity of Dijkstra&apos;s Algorithm is <strong>O(E log V)</strong> , where E is the number of edges and V is the number of vertices.</li> <li>The Space Complexity of Dijkstra&apos;s Algorithm is O(V), where V is the number of vertices.</li> </ul> <h2>Advantages and Disadvantages of Dijkstra&apos;s Algorithm</h2> <p> <strong>Let us discuss some advantages of Dijkstra&apos;s Algorithm:</strong> </p> <ol class="points"> <li>One primary advantage of using Dijkstra&apos;s Algorithm is that it has an almost linear time and space complexity.</li> <li>We can use this algorithm to calculate the shortest path from a single vertex to all other vertices and a single source vertex to a single destination vertex by stopping the algorithm once we get the shortest distance for the destination vertex.</li> <li>This algorithm only works for directed weighted graphs, and all the edges of this graph should be non-negative.</li> </ol> <p> <strong>Despite having multiple advantages, Dijkstra&apos;s algorithm has some disadvantages also, such as:</strong> </p> <ol class="points"> <li>Dijkstra&apos;s Algorithm performs a concealed exploration that utilizes a lot of time during the process.</li> <li>This algorithm is impotent to handle negative edges.</li> <li>Since this algorithm heads to the acyclic graph, it cannot calculate the exact shortest path.</li> <li>It also requires maintenance to keep a record of vertices that have been visited.</li> </ol> <h2>Some Applications of Dijkstra&apos;s Algorithm</h2> <p> <strong>Dijkstra&apos;s Algorithm has various real-world applications, some of which are stated below:</strong> </p> <ol class="points"> <tr><td>Digital Mapping Services in Google Maps:</td> There are various times when we have tried to find the distance in Google Maps either from our location to the nearest preferred location or from one city to another, which comprises multiple routes/paths connecting them; however, the application must display the minimum distance. This is only possible because Dijkstra&apos;s algorithm helps the application find the shortest between two given locations along the path. Let us consider the USA as a graph wherein the cities/places are represented as vertices, and the routes between two cities/places are represented as edges. Then with the help of Dijkstra&apos;s Algorithm, we can calculate the shortest routes between any two cities/places. </tr><tr><td>Social Networking Applications:</td> In many applications like Facebook, Twitter, Instagram, and more, many of us might have observed that these apps suggest the list of friends that a specific user may know. How do many social media companies implement this type of feature in an efficient and effective way, specifically when the system has over a billion users? The answer to this question is Dijkstra&apos;s Algorithm. The standard Dijkstra&apos;s Algorithm is generally used to estimate the shortest distance between the users measured through the connections or mutuality among them. When social networking is very small, it uses the standard Dijkstra&apos;s Algorithm in addition to some other features in order to determine the shortest paths. However, when the graph is much bigger, the standard algorithm takes several seconds to count, and thus, some advanced algorithms are used as the alternative. </tr><tr><td>Telephone Network:</td> As some of us might know, in a telephone network, each transmission line has a bandwidth, &apos;b&apos;. The bandwidth is the highest frequency that the transmission line can support. In general, if the frequency of the signal is higher in a specific line, the signal is reduced by that line. Bandwidth represents the amount of information that can be transmitted by the line. Let us consider a city a graph wherein the switching stations are represented using the vertices, the transmission lines are represented as the edges, and the bandwidth, &apos;b&apos;, is represented using the weight of the edges. Thus, as we can observe, the telephone network can also fall into the category of the shortest distance problem and can be solved using Dijkstra&apos;s Algorithm. </tr><tr><td>Flight Program:</td> Suppose that a person requires software to prepare an agenda of flights for customers. The agent has access to a database with all flights and airports. In addition to the flight number, origin airport, and destination, the flights also have departure and arrival times. So, in order to determine the earliest arrival time for the selected destination from the original airport and given start time, the agents make use of Dijkstra&apos;s Algorithm. </tr><tr><td>IP routing to find Open Shortest Path First:</td> Open Shortest Path First (abbreviated as OSPF) is a link-state routing protocol used to find the best path between the source and destination router with the help of its own Shortest Path First. Dijkstra&apos;s Algorithm is extensively utilized in the routing protocols required by the routers in order to update their forwarding table. The algorithm gives the shortest cost path from the source router to the other routers present in the network. </tr><tr><td>Robotic Path:</td> These days, drones and robots have come into existence, some operated manually and some automatically. The drones and robots which are operated automatically and used to deliver the packages to a given location or used for any certain task are configured with Dijkstra&apos;s Algorithm module so that whenever the source and destination are known, the drone and robot will move in the ordered direction by following the shortest path keeping the time taken to a minimum in order to deliver the packages. </tr><tr><td>Designate the File Server:</td> Dijkstra&apos;s Algorithm is also used to designate a file server in a Local Area Network (LAN). Suppose that an infinite period of time is needed for the transmission of the files from one computer to another. So, to minimize the number of &apos;hops&apos; from the file server to every other computer on the network, we will use Dijkstra&apos;s Algorithm. This algorithm will return the shortest path between the networks resulting in the minimum number of hops. </tr></ol> <h2>The Conclusion</h2> <ul> <li>In the above tutorial, firstly, we have understood the basic concepts of Graph along with its types and applications.</li> <li>We then learned about Dijkstra&apos;s Algorithm and its history.</li> <li>We have also understood the fundamental working of Dijkstra&apos;s Algorithm with the help of an example.</li> <li>After that, we studied how to write code for Dijkstra&apos;s Algorithm with the help of Pseudocode.</li> <li>We observed its implementation in programming languages like C, C++, Java, and Python with proper outputs and explanations.</li> <li>We have also understood the Time and Space Complexity of Dijkstra&apos;s Algorithm.</li> <li>Finally, we have discussed the advantages and disadvantages of Dijkstra&apos;s algorithm and some of its real-life applications.</li> </ul> <hr></nodes;></pre></size;>

Пояснення:

У наведеному вище фрагменті коду ми включили 'iostream' і 'вектор' файли заголовків і визначив постійне значення як MAX_INT = 10000000 . Потім ми використали стандартний простір імен і створили прототип Алгоритм Дейкстра() функція. Потім ми визначили основну функцію програми, яку ми назвали Алгоритм Дейкстра() функція. Після цього ми оголосили кілька класів для створення вершин і ребер. Ми також прототипували більше функцій для пошуку найкоротшого шляху від вихідної вершини до кінцевої вершини та створили екземпляри класів Vertex і Edge. Потім ми визначили обидва класи для створення вершин і ребер графа. Потім ми визначили Алгоритм Дейкстра() функція для створення графіка та виконання різних операцій. У цій функції ми оголосили кілька вершин і ребер. Потім ми встановили вихідну вершину графа та викликали Дейкстра() функція пошуку найкоротшої відстані та Print_Shortest_Route_To() функція для друку найкоротшої відстані від вихідної вершини до вершини 'F' . Потім ми визначили Дейкстра() функція для обчислення найкоротших можливих відстаней усіх вершин від вихідної вершини. Ми також визначили ще деякі функції для пошуку вершини з найкоротшою відстанню, щоб повернути всі вершини, суміжні з іншою вершиною, повернути відстань між двома з’єднаними вершинами, перевірити, чи існує вибрана вершина в графі, і надрукувати найкоротший шлях від вихідної вершини до кінцевої вершини.

В результаті шуканий найкоротший шлях для вершини 'F' з вихідного вузла друкується для користувачів.

Код для алгоритму Дейкстри в Java

Нижче наведено реалізацію алгоритму Дейкстри на мові програмування Java:

Файл: DijkstraAlgorithm.java

 // Implementation of Dijkstra&apos;s Algorithm in Java // defining the public class for Dijkstra&apos;s Algorithm public class DijkstraAlgorithm { // defining the method to implement Dijkstra&apos;s Algorithm public void dijkstraAlgorithm(int[][] graph, int source) { // number of nodes int nodes = graph.length; boolean[] visited_vertex = new boolean[nodes]; int[] dist = new int[nodes]; for (int i = 0; i <nodes; 0 1 i++) { visited_vertex[i]="false;" dist[i]="Integer.MAX_VALUE;" } distance of self loop is zero dist[source]="0;" for (int i="0;" < nodes; updating the between neighboring vertex and source int u="find_min_distance(dist," visited_vertex); visited_vertex[u]="true;" distances all vertices v="0;" v++) if (!visited_vertex[v] && graph[u][v] !="0" (dist[u] + dist[v])) dist[v]="dist[u]" graph[u][v]; dist.length; system.out.println(string.format(\'distance from %s to %s\', source, i, dist[i])); defining method find minimum private static find_min_distance(int[] dist, boolean[] visited_vertex) minimum_distance="Integer.MAX_VALUE;" minimum_distance_vertex="-1;" (!visited_vertex[i] minimum_distance) return minimum_distance_vertex; main function public void main(string[] args) declaring nodes graphs graph[][]="new" int[][] 0, 1, 2, }, 3, }; instantiating dijkstraalgorithm() class dijkstraalgorithm test="new" dijkstraalgorithm(); calling shortest node destination test.dijkstraalgorithm(graph, 0); pre> <p> <strong>Output</strong> </p> <pre> Distance from Vertex 0 to Vertex 0 is 0 Distance from Vertex 0 to Vertex 1 is 1 Distance from Vertex 0 to Vertex 2 is 1 Distance from Vertex 0 to Vertex 3 is 2 Distance from Vertex 0 to Vertex 4 is 4 Distance from Vertex 0 to Vertex 5 is 4 Distance from Vertex 0 to Vertex 6 is 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have defined a public class as <strong>DijkstraAlgorithm()</strong> . Inside this class, we have defined a public method as <strong>dijkstraAlgorithm()</strong> to find the shortest distance from the source vertex to the destination vertex. Inside this method, we have defined a variable to store the number of nodes. We have then defined a Boolean array to store the information regarding the visited vertices and an integer array to store their respective distances. Initially, we declared the values in both the arrays as <strong>False</strong> and <strong>MAX_VALUE</strong> , respectively. We have also set the distance of the source vertex as zero and used the <strong>for-loop</strong> to update the distance between the source vertex and destination vertices with the minimum distance. We have then updated the distances of the neighboring vertices of the selected vertex by performing relaxation and printed the shortest distances for every vertex. We have then defined a method to find the minimum distance from the source vertex to the destination vertex. We then defined the main function where we declared the vertices of the graph and instantiated the <strong>DijkstraAlgorithm()</strong> class. Finally, we have called the <strong>dijkstraAlgorithm()</strong> method to find the shortest distance between the source vertex and the destination vertices.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h3>Code for Dijkstra&apos;s Algorithm in Python</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the Python Programming Language:</p> <p> <strong>File: DikstraAlgorithm.py</strong> </p> <pre> # Implementation of Dijkstra&apos;s Algorithm in Python # importing the sys module import sys # declaring the list of nodes for the graph nodes = [ [0, 0, 1, 0, 1, 0, 0], [0, 0, 1, 0, 0, 1, 0], [1, 1, 0, 1, 1, 0, 0], [1, 0, 1, 0, 0, 0, 1], [0, 0, 1, 0, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # declaring the list of edges for the graph edges = [ [0, 0, 1, 0, 2, 0, 0], [0, 0, 2, 0, 0, 3, 0], [1, 2, 0, 1, 3, 0, 0], [2, 0, 1, 0, 0, 0, 1], [0, 0, 3, 0, 0, 2, 0], [0, 3, 0, 0, 2, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # defining the function to find which node is to be visited next def toBeVisited(): global visitedAndDistance v = -10 for index in range(numberOfNodes): if visitedAndDistance[index][0] == 0 and (v <0 1 or visitedanddistance[index][1] <="visitedAndDistance[v][1]):" v="index" return # finding the number of nodes in graph numberofnodes="len(nodes[0])" visitedanddistance="[[0," 0]] for i range(numberofnodes - 1): visitedanddistance.append([0, sys.maxsize]) node range(numberofnodes): next to be visited tovisit="toBeVisited()" neighborindex updating new distances if nodes[tovisit][neighborindex]="=" and visitedanddistance[neighborindex][0]="=" 0: newdistance="visitedAndDistance[toVisit][1]" + edges[tovisit][neighborindex] visitedanddistance[neighborindex][1]> newDistance: visitedAndDistance[neighborIndex][1] = newDistance visitedAndDistance[toVisit][0] = 1 i = 0 # printing the distance for distance in visitedAndDistance: print(&apos;Distance of&apos;, chr(ord(&apos;A&apos;) + i), &apos;from source node:&apos;, distance[1]) i = i + 1 </0></pre> <p> <strong>Output</strong> </p> <pre> Distance of A from source node: 0 Distance of B from source node: 3 Distance of C from source node: 1 Distance of D from source node: 2 Distance of E from source node: 2 Distance of F from source node: 4 Distance of G from source node: 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have imported the <strong>sys</strong> module and declared the lists consisting of the values for the nodes and edges. We have then defined a function as <strong>toBeVisited()</strong> to find which node will be visited next. We then found the total number of nodes in the graph and set the initial distances for every node. We have then calculated the minimum distance from the source node to the destination node, performed relaxation on neighboring nodes, and updated the distances in the list. We then printed those distances from the list for the users.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h2>Time and Space Complexity of Dijkstra&apos;s Algorithm</h2> <ul> <li>The Time Complexity of Dijkstra&apos;s Algorithm is <strong>O(E log V)</strong> , where E is the number of edges and V is the number of vertices.</li> <li>The Space Complexity of Dijkstra&apos;s Algorithm is O(V), where V is the number of vertices.</li> </ul> <h2>Advantages and Disadvantages of Dijkstra&apos;s Algorithm</h2> <p> <strong>Let us discuss some advantages of Dijkstra&apos;s Algorithm:</strong> </p> <ol class="points"> <li>One primary advantage of using Dijkstra&apos;s Algorithm is that it has an almost linear time and space complexity.</li> <li>We can use this algorithm to calculate the shortest path from a single vertex to all other vertices and a single source vertex to a single destination vertex by stopping the algorithm once we get the shortest distance for the destination vertex.</li> <li>This algorithm only works for directed weighted graphs, and all the edges of this graph should be non-negative.</li> </ol> <p> <strong>Despite having multiple advantages, Dijkstra&apos;s algorithm has some disadvantages also, such as:</strong> </p> <ol class="points"> <li>Dijkstra&apos;s Algorithm performs a concealed exploration that utilizes a lot of time during the process.</li> <li>This algorithm is impotent to handle negative edges.</li> <li>Since this algorithm heads to the acyclic graph, it cannot calculate the exact shortest path.</li> <li>It also requires maintenance to keep a record of vertices that have been visited.</li> </ol> <h2>Some Applications of Dijkstra&apos;s Algorithm</h2> <p> <strong>Dijkstra&apos;s Algorithm has various real-world applications, some of which are stated below:</strong> </p> <ol class="points"> <tr><td>Digital Mapping Services in Google Maps:</td> There are various times when we have tried to find the distance in Google Maps either from our location to the nearest preferred location or from one city to another, which comprises multiple routes/paths connecting them; however, the application must display the minimum distance. This is only possible because Dijkstra&apos;s algorithm helps the application find the shortest between two given locations along the path. Let us consider the USA as a graph wherein the cities/places are represented as vertices, and the routes between two cities/places are represented as edges. Then with the help of Dijkstra&apos;s Algorithm, we can calculate the shortest routes between any two cities/places. </tr><tr><td>Social Networking Applications:</td> In many applications like Facebook, Twitter, Instagram, and more, many of us might have observed that these apps suggest the list of friends that a specific user may know. How do many social media companies implement this type of feature in an efficient and effective way, specifically when the system has over a billion users? The answer to this question is Dijkstra&apos;s Algorithm. The standard Dijkstra&apos;s Algorithm is generally used to estimate the shortest distance between the users measured through the connections or mutuality among them. When social networking is very small, it uses the standard Dijkstra&apos;s Algorithm in addition to some other features in order to determine the shortest paths. However, when the graph is much bigger, the standard algorithm takes several seconds to count, and thus, some advanced algorithms are used as the alternative. </tr><tr><td>Telephone Network:</td> As some of us might know, in a telephone network, each transmission line has a bandwidth, &apos;b&apos;. The bandwidth is the highest frequency that the transmission line can support. In general, if the frequency of the signal is higher in a specific line, the signal is reduced by that line. Bandwidth represents the amount of information that can be transmitted by the line. Let us consider a city a graph wherein the switching stations are represented using the vertices, the transmission lines are represented as the edges, and the bandwidth, &apos;b&apos;, is represented using the weight of the edges. Thus, as we can observe, the telephone network can also fall into the category of the shortest distance problem and can be solved using Dijkstra&apos;s Algorithm. </tr><tr><td>Flight Program:</td> Suppose that a person requires software to prepare an agenda of flights for customers. The agent has access to a database with all flights and airports. In addition to the flight number, origin airport, and destination, the flights also have departure and arrival times. So, in order to determine the earliest arrival time for the selected destination from the original airport and given start time, the agents make use of Dijkstra&apos;s Algorithm. </tr><tr><td>IP routing to find Open Shortest Path First:</td> Open Shortest Path First (abbreviated as OSPF) is a link-state routing protocol used to find the best path between the source and destination router with the help of its own Shortest Path First. Dijkstra&apos;s Algorithm is extensively utilized in the routing protocols required by the routers in order to update their forwarding table. The algorithm gives the shortest cost path from the source router to the other routers present in the network. </tr><tr><td>Robotic Path:</td> These days, drones and robots have come into existence, some operated manually and some automatically. The drones and robots which are operated automatically and used to deliver the packages to a given location or used for any certain task are configured with Dijkstra&apos;s Algorithm module so that whenever the source and destination are known, the drone and robot will move in the ordered direction by following the shortest path keeping the time taken to a minimum in order to deliver the packages. </tr><tr><td>Designate the File Server:</td> Dijkstra&apos;s Algorithm is also used to designate a file server in a Local Area Network (LAN). Suppose that an infinite period of time is needed for the transmission of the files from one computer to another. So, to minimize the number of &apos;hops&apos; from the file server to every other computer on the network, we will use Dijkstra&apos;s Algorithm. This algorithm will return the shortest path between the networks resulting in the minimum number of hops. </tr></ol> <h2>The Conclusion</h2> <ul> <li>In the above tutorial, firstly, we have understood the basic concepts of Graph along with its types and applications.</li> <li>We then learned about Dijkstra&apos;s Algorithm and its history.</li> <li>We have also understood the fundamental working of Dijkstra&apos;s Algorithm with the help of an example.</li> <li>After that, we studied how to write code for Dijkstra&apos;s Algorithm with the help of Pseudocode.</li> <li>We observed its implementation in programming languages like C, C++, Java, and Python with proper outputs and explanations.</li> <li>We have also understood the Time and Space Complexity of Dijkstra&apos;s Algorithm.</li> <li>Finally, we have discussed the advantages and disadvantages of Dijkstra&apos;s algorithm and some of its real-life applications.</li> </ul> <hr></nodes;>

Пояснення:

У наведеному вище фрагменті коду ми визначили публічний клас як Алгоритм Дейкстра() . У цьому класі ми визначили відкритий метод як dijkstraAlgorithm() щоб знайти найкоротшу відстань від вихідної вершини до кінцевої вершини. У цьому методі ми визначили змінну для зберігання кількості вузлів. Потім ми визначили логічний масив для зберігання інформації про відвідані вершини та масив цілих чисел для зберігання їхніх відповідних відстаней. Спочатку ми оголосили значення в обох масивах як помилковий і MAX_VALUE , відповідно. Ми також встановили відстань вихідної вершини як нуль і використали цикл for щоб оновити відстань між вихідною вершиною та кінцевою вершиною з мінімальною відстанню. Потім ми оновили відстані до сусідніх вершин вибраної вершини, виконавши релаксацію, і надрукували найкоротші відстані для кожної вершини. Потім ми визначили метод визначення мінімальної відстані від вихідної вершини до кінцевої вершини. Потім ми визначили основну функцію, де оголосили вершини графа та створили екземпляр Алгоритм Дейкстра() клас. Нарешті ми подзвонили dijkstraAlgorithm() метод пошуку найкоротшої відстані між вихідною вершиною та кінцевою вершиною.

У результаті для користувачів друкуються необхідні найкоротші шляхи для кожного вузла з вихідного вузла.

Код для алгоритму Дейкстри в Python

Нижче наведено реалізацію алгоритму Дейкстри на мові програмування Python:

Файл: DikstraAlgorithm.py

 # Implementation of Dijkstra&apos;s Algorithm in Python # importing the sys module import sys # declaring the list of nodes for the graph nodes = [ [0, 0, 1, 0, 1, 0, 0], [0, 0, 1, 0, 0, 1, 0], [1, 1, 0, 1, 1, 0, 0], [1, 0, 1, 0, 0, 0, 1], [0, 0, 1, 0, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # declaring the list of edges for the graph edges = [ [0, 0, 1, 0, 2, 0, 0], [0, 0, 2, 0, 0, 3, 0], [1, 2, 0, 1, 3, 0, 0], [2, 0, 1, 0, 0, 0, 1], [0, 0, 3, 0, 0, 2, 0], [0, 3, 0, 0, 2, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # defining the function to find which node is to be visited next def toBeVisited(): global visitedAndDistance v = -10 for index in range(numberOfNodes): if visitedAndDistance[index][0] == 0 and (v <0 1 or visitedanddistance[index][1] <="visitedAndDistance[v][1]):" v="index" return # finding the number of nodes in graph numberofnodes="len(nodes[0])" visitedanddistance="[[0," 0]] for i range(numberofnodes - 1): visitedanddistance.append([0, sys.maxsize]) node range(numberofnodes): next to be visited tovisit="toBeVisited()" neighborindex updating new distances if nodes[tovisit][neighborindex]="=" and visitedanddistance[neighborindex][0]="=" 0: newdistance="visitedAndDistance[toVisit][1]" + edges[tovisit][neighborindex] visitedanddistance[neighborindex][1]> newDistance: visitedAndDistance[neighborIndex][1] = newDistance visitedAndDistance[toVisit][0] = 1 i = 0 # printing the distance for distance in visitedAndDistance: print(&apos;Distance of&apos;, chr(ord(&apos;A&apos;) + i), &apos;from source node:&apos;, distance[1]) i = i + 1 </0>

Вихід

 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

Пояснення:

прямий ланцюг

У наведеному вище фрагменті коду ми імпортували система модуль і оголосив списки, що складаються зі значень для вузлів і ребер. Потім ми визначили функцію як toBeVisited() щоб визначити, який вузол буде відвідано наступним. Потім ми знайшли загальну кількість вузлів на графіку та встановили початкові відстані для кожного вузла. Потім ми обчислили мінімальну відстань від вузла джерела до вузла призначення, виконали релаксацію на сусідніх вузлах і оновили відстані в списку. Потім ми роздрукували ці відстані зі списку для користувачів.

У результаті для користувачів друкуються необхідні найкоротші шляхи для кожного вузла з вихідного вузла.

Часова та просторова складність алгоритму Дейкстри

Часова складність алгоритму Дейкстри становить O(E log V) , де E – кількість ребер, а V – кількість вершин.
Просторова складність алгоритму Дейкстри дорівнює O(V), де V — кількість вершин.

Переваги та недоліки алгоритму Дейкстри

Давайте обговоримо деякі переваги алгоритму Дейкстри:

Однією з основних переваг використання алгоритму Дейкстри є те, що він має майже лінійну часову та просторову складність.
Ми можемо використовувати цей алгоритм для обчислення найкоротшого шляху від однієї вершини до всіх інших вершин і однієї вихідної вершини до однієї вершини призначення, зупиняючи алгоритм, коли ми отримуємо найкоротшу відстань для вершини призначення.
Цей алгоритм працює лише для орієнтованих зважених графів, і всі ребра цього графа мають бути невід’ємними.

Незважаючи на численні переваги, алгоритм Дейкстри також має деякі недоліки, такі як:

Алгоритм Дейкстри виконує приховане дослідження, яке використовує багато часу під час процесу.
Цей алгоритм неспроможний обробляти негативні краї.
Оскільки цей алгоритм спрямовується на ациклічний граф, він не може обчислити точний найкоротший шлях.
Він також вимагає обслуговування, щоб вести облік відвіданих вершин.

Деякі застосування алгоритму Дейкстри

Алгоритм Дейкстри має різні реальні застосування, деякі з яких наведено нижче:

Цифрові картографічні служби в Google Maps:Бувають різні випадки, коли ми намагаємося знайти відстань на Картах Google або від нашого місцезнаходження до найближчого бажаного місця, або від одного міста до іншого, що складається з кількох маршрутів/шляхів, що з’єднують їх; проте програма повинна відображати мінімальну відстань. Це можливо лише тому, що алгоритм Дейкстри допомагає програмі знаходити найкоротший шлях між двома вказаними місцями. Розглянемо США як граф, у якому міста/місця представлені як вершини, а маршрути між двома містами/місцями представлені як ребра. Потім за допомогою алгоритму Дейкстри ми можемо розрахувати найкоротші маршрути між будь-якими двома містами/місцями.Програми соціальних мереж:У багатьох програмах, таких як Facebook, Twitter, Instagram тощо, багато хто з нас могли помітити, що ці програми пропонують список друзів, яких може знати конкретний користувач. Як багатьом компаніям соціальних медіа впроваджувати цей тип функції ефективним і ефективним способом, особливо коли система має понад мільярд користувачів? Відповіддю на це питання є алгоритм Дейкстри. Стандартний алгоритм Дейкстри зазвичай використовується для оцінки найкоротшої відстані між користувачами, виміряної через зв’язки або взаємність між ними. Коли соціальна мережа дуже мала, вона використовує стандартний алгоритм Дейкстри на додаток до деяких інших функцій для визначення найкоротших шляхів. Однак, коли графік набагато більший, підрахунок стандартного алгоритму займає кілька секунд, тому в якості альтернативи використовуються деякі вдосконалені алгоритми.Телефонна мережа:Як деякі з нас можуть знати, у телефонній мережі кожна лінія передачі має пропускну здатність «b». Смуга пропускання – це найвища частота, яку може підтримувати лінія передачі. Загалом, якщо частота сигналу вища в певному рядку, сигнал зменшується на цей рядок. Пропускна здатність означає кількість інформації, яку можна передати лінією. Розглянемо місто як граф, на якому комутаційні станції представлені за допомогою вершин, лінії передачі представлені як ребра, а пропускна здатність, «b», представлена за допомогою ваги ребер. Таким чином, як ми бачимо, телефонна мережа також може підпадати під категорію проблеми найкоротшої відстані та може бути розв’язана за допомогою алгоритму Дейкстри.Програма польоту:Припустімо, що людині потрібне програмне забезпечення для підготовки розкладу рейсів для клієнтів. Агент має доступ до бази даних з усіма рейсами та аеропортами. Окрім номера рейсу, аеропорту відправлення та пункту призначення, рейси також мають час відправлення та прибуття. Таким чином, щоб визначити найраніший час прибуття у вибраний пункт призначення з початкового аеропорту та заданий час початку, агенти використовують алгоритм Дейкстри.IP-маршрутизація, щоб спочатку знайти відкритий найкоротший шлях:Open Shortest Path First (скорочено OSPF) — це протокол маршрутизації за станом зв’язку, який використовується для пошуку найкращого шляху між маршрутизатором джерела та призначення за допомогою власного протоколу Shortest Path First. Алгоритм Дейкстри широко використовується в протоколах маршрутизації, необхідних маршрутизаторам для оновлення таблиці пересилання. Алгоритм забезпечує найкоротший шлях від вихідного маршрутизатора до інших маршрутизаторів у мережі.Роботизований шлях:У наші дні з’явилися дрони та роботи, деякі з яких працюють вручну, а інші – автоматично. Безпілотники та роботи, які керуються автоматично та використовуються для доставки посилок у певне місце або використовуються для будь-якого певного завдання, налаштовані за допомогою модуля алгоритму Дейкстри таким чином, що коли джерело та пункт призначення відомі, дрон і робот рухатимуться в замовленому напрямку. дотримуючись найкоротшого шляху, мінімально витрачаючи час на доставку посилок.Призначте файловий сервер:Алгоритм Дейкстри також використовується для визначення файлового сервера в локальній мережі (LAN). Припустимо, що для передачі файлів з одного комп’ютера на інший потрібен нескінченний період часу. Отже, щоб мінімізувати кількість «стрибків» від файлового сервера до кожного іншого комп’ютера в мережі, ми використаємо алгоритм Дейкстри. Цей алгоритм поверне найкоротший шлях між мережами, що призведе до мінімальної кількості переходів.

Висновок

У наведеному вище підручнику, по-перше, ми зрозуміли основні поняття Graph разом із його типами та застосуваннями.
Потім ми дізналися про алгоритм Дейкстри та його історію.
Ми також зрозуміли фундаментальну роботу алгоритму Дейкстри за допомогою прикладу.
Після цього ми вивчали, як писати код для алгоритму Дейкстри за допомогою псевдокоду.
Ми спостерігали за його впровадженням у таких мовах програмування, як C, C++, Java та Python, з відповідними результатами та поясненнями.
Ми також зрозуміли часову та просторову складність алгоритму Дейкстри.
Нарешті, ми обговорили переваги та недоліки алгоритму Дейкстри та деякі з його реальних застосувань.