Следният урок ще ни научи за алгоритъма за най-краткия път на Дейкстра. Ще разберем работата на алгоритъма на Дейкстра с поетапно графично обяснение.
Ние ще покрием следното:
- Кратък преглед на основните понятия на графа
- Разберете използването на алгоритъма на Дейкстра
- Разберете работата на алгоритъма с пример стъпка по стъпка
И така, да започваме.
Кратко въведение в графиките
Графики са нелинейни структури от данни, представящи „връзките“ между елементите. Тези елементи са известни като Върхове , а линиите или дъгите, които свързват всеки два върха в графиката, са известни като Ръбове . По-формално, графиката включва набор от върхове (V) и набор от ръбове (E) . Графиката се обозначава с G(V, E) .
Компоненти на графика
Следващата фигура показва графично представяне на графика:
Фигура 1: Графично представяне на графика
В горната фигура върховете/възлите са означени с цветни кръгове, а ръбовете са означени с линиите, свързващи възлите.
Приложения на графиките
Графиките се използват за решаване на много проблеми от реалния живот. Графиките се използват за представяне на мрежите. Тези мрежи могат да включват телефонни или верижни мрежи или пътеки в града.
Например, можем да използваме Graphs, за да проектираме модел на транспортна мрежа, където върховете показват съоръженията, които изпращат или получават продуктите, а краищата представляват пътища или пътеки, които ги свързват. Следното е картинно представяне на същото:
Фигура 2: Картинно представяне на транспортна мрежа
Графиките се използват и в различни социални медийни платформи като LinkedIn, Facebook, Twitter и др. Например платформи като Facebook използват Graphs, за да съхраняват данните на своите потребители, където всеки човек е обозначен с връх и всеки от тях е структура, съдържаща информация като ID на лицето, име, пол, адрес и т.н.
Видове графики
Графиките могат да бъдат категоризирани в два типа:
- Неориентирана графика
- Насочена графика
Неориентирана графика: Граф с ребра, които нямат посока, се нарича неориентиран граф. Ръбовете на тази графика предполагат двупосочна връзка, при която всеки ръб може да бъде обходен и в двете посоки. Следващата фигура показва проста неориентирана графика с четири възела и пет ребра.
Фигура 3: Прост неориентиран график
Насочена графика: Граф с ребра с посока се нарича насочен граф. Ръбовете на тази графика предполагат еднопосочна връзка, в която всеки ръб може да бъде обходен само в една посока. Следващата фигура показва проста насочена графика с четири възела и пет ребра.
Фигура 4: Прост насочен график
Абсолютната дължина, позиция или ориентация на ръбовете в илюстрация на графика обикновено нямат значение. С други думи, можем да визуализираме една и съща графика по различни начини чрез пренареждане на върховете или изкривяване на ръбовете, ако основната структура на графиката не се променя.
Какво представляват претеглените графики?
Графът се нарича претеглен, ако на всяко ребро е присвоено „тегло“. Теглото на ребро може да означава разстояние, време или нещо, което моделира „връзката“ между двойката върхове, които свързва.
Например, можем да наблюдаваме синьо число до всеки ръб на следващата фигура на претеглената графика. Това число се използва за означаване на теглото на съответния ръб.
Фигура 5: Пример за претеглена графика
Въведение в алгоритъма на Дейкстра
Сега, след като знаем някои основни концепции на Graphs, нека се потопим в разбирането на концепцията на алгоритъма на Дейкстра.
Някога чудили ли сте се как Google Maps намира най-краткия и бърз маршрут между две места?
Е, отговорът е Алгоритъмът на Дейкстра . Алгоритъмът на Дейкстра е графичен алгоритъм който намира най-краткия път от изходен връх до всички други върхове в Графа (най-краткият път на един източник). Това е вид алчен алгоритъм, който работи само върху претеглени графики с положителни тегла. Времевата сложност на алгоритъма на Дейкстра е O(V2) с помощта на матрицата на съседство на графа. Тази времева сложност може да бъде намалена до O((V + E) log V) с помощта на списък със съседство представяне на графиката, където IN е броят на върховете и И е броят на ръбовете в графиката.
c++ int към низ
История на алгоритъма на Дейкстра
Алгоритъмът на Дейкстра е проектиран и публикуван от д-р Edsger W. Dijkstra , холандски компютърен учен, софтуерен инженер, програмист, научен есеист и системен учен.
По време на интервю с Филип Л. Франа за съобщенията на списание ACM през 2001 г., д-р Едсгер В. Дайкстра разкри:
„Какъв е най-краткият път за пътуване от Ротердам до Гронинген като цяло: от даден град до даден град? Това е алгоритъмът за най-краткия път, който проектирах за около двадесет минути. Една сутрин пазарувах в Амстердам с моята млада годеница и уморени седнахме на терасата на кафенето да изпием чаша кафе и аз просто си мислех дали мога да направя това и тогава създадох алгоритъма за най-краткия път . Както казах, това беше двадесетминутно изобретение. Всъщност тя е публикувана през 59-та, три години по-късно. Публикацията все още се чете, всъщност е доста хубава. Една от причините да е толкова хубав беше, че го проектирах без молив и хартия. По-късно научих, че едно от предимствата на проектирането без молив и хартия е, че сте почти принудени да избягвате всички усложнения, които можете да избегнете. В крайна сметка този алгоритъм се превърна за мое голямо учудване в един от крайъгълните камъни на моята слава.
Дейкстра мисли за проблема с най-краткия път, докато работи като програмист в Математическия център в Амстердам през 1956 г., за да илюстрира възможностите на нов компютър, известен като ARMAC. Неговата цел беше да избере както проблем, така и решение (произведено от компютъра), които хората без компютърно образование да могат да разберат. Той разработи алгоритъм за най-краткия път и по-късно го изпълни за ARMAC за неясно съкратена транспортна карта на 64 града в Холандия (64 града, така че 6 бита биха били достатъчни за кодиране на номера на града). Година по-късно той се натъква на друг проблем от хардуерните инженери, работещи със следващия компютър на института: Намалете до минимум количеството проводници, необходими за свързване на щифтовете на задния панел на машината. Като решение той преоткрива алгоритъма, наречен алгоритъм на минимално обхващащо дърво на Прим, и го публикува през 1959 г.
Основи на алгоритъма на Дейкстра
Следват основните концепции на алгоритъма на Дейкстра:
- Алгоритъмът на Dijkstra започва от избрания от нас възел (изходния възел) и изследва графиката, за да намери най-краткия път между този възел и всички останали възли в графиката.
- Алгоритъмът съхранява записи на текущо потвърденото най-късо разстояние от всеки възел до изходния възел и актуализира тези стойности, ако намери по-къс път.
- След като алгоритъмът извлече най-краткия път между източника и друг възел, този възел се маркира като „посетен“ и се включва в пътя.
- Процедурата продължава, докато всички възли в графиката бъдат включени в пътя. По този начин имаме път, свързващ изходния възел с всички други възли, следвайки възможно най-краткия път за достигане до всеки възел.
Разбиране на работата на алгоритъма на Дейкстра
А графика и изходен връх са изисквания за алгоритъма на Дейкстра. Този алгоритъм е установен на алчен подход и по този начин намира локално оптималния избор (локални минимуми в този случай) на всяка стъпка от алгоритъма.
Всеки връх в този алгоритъм ще има две свойства, дефинирани за него:
- Посетен имот
- Свойство на пътя
Нека разберем тези свойства накратко.
Посетен имот:
- Свойството „посетен“ показва дали възелът е бил посетен или не.
- Ние използваме това свойство, за да не посещаваме отново нито един възел.
- Възел се маркира като посетен само когато е намерен най-краткият път.
Свойство на пътя:
- Свойството '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.
Стъпка 4: След това ще маркираме текущия възел X като посетен.
Стъпка 5: Ще повторим процеса от 'Стъпка 2' ако в графиката има непосетен възел.
Нека сега разберем изпълнението на алгоритъма с помощта на пример:
Фигура 6: Дадената графика
- Ще използваме горната графика като вход с възел А като източник.
- Първо, ще маркираме всички възли като непосетени.
- Ние ще определим пътя към 0 на възел А и БЕЗКРАЙНОСТ за всички останали възли.
- Сега ще маркираме изходния възел А като посетен и достъп до съседните му възли.
Забележка: Имаме достъп само до съседните възли, а не ги посещаваме. - Сега ще актуализираме пътя до възела Б от 4 с помощта на релаксация, защото пътят към възел А е 0 и пътя от възела А да се Б е 4 , и минимум ((0 + 4), БЕЗКРАЙНО) е 4 .
- Също така ще актуализираме пътя до възела ° С от 5 с помощта на релаксация, защото пътят към възел А е 0 и пътя от възела А да се ° С е 5 , и минимум ((0 + 5), БЕЗКРАЙНО) е 5 . И двамата съседи на възел А вече са отпуснати; следователно можем да продължим напред.
- Сега ще изберем следващия непосетен възел с най-малък път и ще го посетим. Следователно ще посетим възел Б и извършва релаксация на своите непосетени съседи. След извършване на релаксация, пътят към възел ° С ще напомня 5 , докато пътят към възел И ще стане единадесет и пътя към възела д ще стане 13 .
- Сега ще посетим възел И и извършва релаксация на съседните възли Б, Г , и Е . Тъй като само възел Е е непосетен, ще бъде отпуснат. По този начин, пътят към възел Б ще остане както е, т.е. 4 , пътят към възела д също ще остане 13 и пътя към възела Е ще стане 14 (8 + 6) .
- Сега ще посетим възел д , и само възел Е ще бъде отпуснат. Въпреки това, пътят към възел Е ще остане непроменена, т. 14 .
- Тъй като само възел Е остава, ще го посетим, но няма да извършим релаксация, тъй като всичките му съседни възли вече са посетени.
- След като бъдат посетени всички възли на графиките, програмата ще приключи.
Следователно окончателните пътища, които заключихме, са:
дискета
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)
Псевдокод за алгоритъма на Дейкстра
Сега ще разберем псевдокод за алгоритъма на Дейкстра.
низ json java
- Трябва да поддържаме запис на разстоянието на пътя на всеки възел. Следователно можем да съхраним разстоянието на пътя на всеки възел в масив с размер 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'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]> Обяснение:
В горния кодов фрагмент сме включили stdio.h заглавният файл дефинира две постоянни стойности: INF = 9999 и МАКС = 10 . Декларирахме прототипа на функцията и след това дефинирахме функцията за алгоритъма на Дейкстра като Алгоритъм на Дейкстра който приема три аргумента - графика, състояща се от възлите, броя на възлите в графиката и изходния възел. В тази функция сме дефинирали някои структури от данни като 2D матрица, която ще работи като приоритетна опашка за алгоритъма, масив за поддържане на разстоянието между възлите, масив за поддържане на записа на предишни възли, масив за съхраняване информацията за посетените възли и някои целочислени променливи за съхраняване на стойност на минимално разстояние, брояч, стойност на следващия възел и др. След това използвахме a вложен for-цикъл за итерация през възлите на графиката и съответно добавянето им към опашката с приоритети. Отново използвахме for-цикъл за итерация през елементите в приоритетната опашка, започвайки от изходния възел и актуализиране на техните разстояния. Извън цикъла сме задали разстоянието на изходния възел като 0 и го маркира като посетен в посетени_възли[] масив. След това зададохме стойността на брояча като единица и използвахме докато цикъл, итериращ през броя на възлите. Вътре в този цикъл сме задали стойността на минимално_разстояние като ИНФ и използваха for-цикъл за актуализиране на стойността на минимално_разстояние променлива с минималната стойност от a разстояние[] масив. След това повторихме непосетените съседни възли на избрания възел, използвайки for-цикъл и извършена релаксация. След това отпечатахме получените данни за разстоянията, изчислени с помощта на алгоритъма на Дейкстра.
В основен функция, сме дефинирали и декларирали променливите, представляващи Graph, броя на възлите и изходния възел. Най-накрая се обадихме на DijkstraAlgorithm() функция чрез предаване на необходимите параметри.
В резултат на това необходимите възможно най-кратки пътища за всеки възел от изходния възел се отпечатват за потребителите.
Код за алгоритъма на Дейкстра в C++
Следното е изпълнението на алгоритъма на Дейкстра в езика за програмиране C++:
Файл: 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;> Обяснение:
В горния кодов фрагмент включихме 'iostream' и 'вектор' заглавни файлове и дефинира постоянна стойност като MAX_INT = 10000000 . След това използвахме стандартното пространство от имена и създадохме прототип на DijkstraAlgorithm() функция. След това дефинирахме основната функция на програмата, която нарекохме DijkstraAlgorithm() функция. След това декларирахме някои класове за създаване на върхове и ръбове. Също така създадохме прототипи на повече функции за намиране на възможно най-краткия път от изходния връх до целевия връх и инстанцирахме класовете Vertex и Edge. След това дефинирахме двата класа, за да създадем върховете и ръбовете на графиката. След това дефинирахме DijkstraAlgorithm() функция за създаване на графика и извършване на различни операции. В тази функция сме декларирали някои върхове и ръбове. След това зададохме изходния връх на графиката и извикахме Дейкстра () функция за намиране на възможно най-краткото разстояние и Print_Shortest_Route_To() функция за отпечатване на най-късото разстояние от изходния връх до връх 'F' . След това дефинирахме Дейкстра () функция за изчисляване на възможно най-кратките разстояния на всички върхове от изходния връх. Също така дефинирахме още няколко функции за намиране на върха с най-късо разстояние за връщане на всички върхове, съседни на оставащия връх, за връщане на разстоянието между два свързани върха, за проверка дали избраният връх съществува в графиката и за отпечатване на най-краткият възможен път от изходния връх до целевия връх.
В резултат на това се изисква най-краткият път за върха 'F' от изходния възел се отпечатва за потребителите.
Код за алгоритъма на Дейкстра в Java
Следното е изпълнението на алгоритъма на Дейкстра в езика за програмиране Java:
Файл: 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;> Обяснение:
В горния кодов фрагмент сме дефинирали публичен клас като DijkstraAlgorithm() . Вътре в този клас сме дефинирали публичен метод като dijkstraAlgorithm() за намиране на най-късото разстояние от изходния връх до целевия връх. Вътре в този метод сме дефинирали променлива за съхраняване на броя на възлите. След това сме дефинирали булев масив за съхраняване на информацията относно посетените върхове и целочислен масив за съхраняване на техните съответни разстояния. Първоначално декларирахме стойностите в двата масива като Невярно и MAX_VALUE , съответно. Също така сме задали разстоянието на изходния връх като нула и сме използвали for-цикъл за актуализиране на разстоянието между изходния връх и целевия връх с минималното разстояние. След това актуализирахме разстоянията на съседните върхове на избрания връх чрез извършване на релаксация и отпечатахме най-късите разстояния за всеки връх. След това дефинирахме метод за намиране на минималното разстояние от изходния връх до целевия връх. След това дефинирахме основната функция, където декларирахме върховете на графиката и инстанцирахме DijkstraAlgorithm() клас. Накрая се обадихме на dijkstraAlgorithm() метод за намиране на най-късото разстояние между изходния връх и целевия връх.
В резултат на това необходимите възможно най-кратки пътища за всеки възел от изходния възел се отпечатват за потребителите.
Код за алгоритъма на Дейкстра в Python
Следното е изпълнението на алгоритъма на Дейкстра в езика за програмиране Python:
Файл: 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>
Изход
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 е броят на върховете.
Предимства и недостатъци на алгоритъма на Дейкстра
Нека обсъдим някои предимства на алгоритъма на Дейкстра:
- Едно основно предимство на използването на алгоритъма на Дейкстра е, че той има почти линейна времева и пространствена сложност.
- Можем да използваме този алгоритъм, за да изчислим най-краткия път от един връх до всички останали върхове и един изходен връх до един целеви връх, като спрем алгоритъма, след като получим най-късото разстояние за целевия връх.
- Този алгоритъм работи само за насочени претеглени графики и всички ребра на тази графика трябва да са неотрицателни.
Въпреки че има множество предимства, алгоритъмът на Дейкстра има и някои недостатъци, като например:
- Алгоритъмът на Dijkstra извършва скрито изследване, което използва много време по време на процеса.
- Този алгоритъм е немощен да се справи с отрицателните ръбове.
- Тъй като този алгоритъм се насочва към ацикличната графика, той не може да изчисли точния най-кратък път.
- Освен това изисква поддръжка, за да се поддържа запис на посетените върхове.
Някои приложения на алгоритъма на Дейкстра
Алгоритъмът на Dijkstra има различни приложения в реалния свят, някои от които са посочени по-долу:
Заключението
- В горния урок, първо, разбрахме основните концепции на Graph заедно с неговите видове и приложения.
- След това научихме за алгоритъма на Дейкстра и неговата история.
- Ние също така разбрахме фундаменталната работа на алгоритъма на Дейкстра с помощта на пример.
- След това проучихме как да пишем код за алгоритъма на Дейкстра с помощта на псевдокод.
- Наблюдавахме внедряването му в езици за програмиране като C, C++, Java и Python с подходящи резултати и обяснения.
- Ние също така разбрахме времевата и пространствената сложност на алгоритъма на Дейкстра.
- И накрая, обсъдихме предимствата и недостатъците на алгоритъма на Дейкстра и някои от неговите приложения в реалния живот.