Poniższy samouczek nauczy nas o algorytmie najkrótszej ścieżki Dijkstry. Działanie algorytmu Dijkstry zrozumiemy dzięki stopniowemu wyjaśnieniu graficznemu.
Omówimy następujące kwestie:
- Krótki przegląd podstawowych pojęć dotyczących wykresu
- Zrozumienie zastosowania algorytmu Dijkstry
- Zrozum działanie algorytmu na przykładzie krok po kroku
Więc zacznijmy.
Krótkie wprowadzenie do wykresów
Wykresy są nieliniowymi strukturami danych reprezentującymi „połączenia” pomiędzy elementami. Elementy te nazywane są tzw Wierzchołki , a linie lub łuki łączące dowolne dwa wierzchołki grafu nazywane są Krawędzie . Bardziej formalnie, wykres zawiera zbiór wierzchołków (V) I zestaw krawędzi (E) . Wykres jest oznaczony przez G(V, E) .
wartość ciągu Java
Składniki wykresu
Poniższy rysunek przedstawia graficzną reprezentację wykresu:
Rysunek 1: Graficzna reprezentacja wykresu
Na powyższym rysunku wierzchołki/węzły oznaczono kolorowymi kółkami, a krawędzie liniami łączącymi węzły.
Zastosowania wykresów
Wykresy służą do rozwiązywania wielu rzeczywistych problemów. Do przedstawienia sieci wykorzystywane są wykresy. Sieci te mogą obejmować sieci telefoniczne lub obwody lub ścieżki w mieście.
Na przykład moglibyśmy użyć wykresów do zaprojektowania modelu sieci transportowej, w którym wierzchołki przedstawiają obiekty wysyłające lub odbierające produkty, a krawędzie reprezentują łączące je drogi lub ścieżki. Poniżej znajduje się obrazowe przedstawienie tego samego:
Rysunek 2: Obrazowe przedstawienie sieci transportowej
Wykresy są również wykorzystywane na różnych platformach mediów społecznościowych, takich jak LinkedIn, Facebook, Twitter i nie tylko. Na przykład platformy takie jak Facebook używają wykresów do przechowywania danych swoich użytkowników, gdzie każda osoba jest oznaczona wierzchołkiem, a każda z nich jest strukturą zawierającą informacje takie jak identyfikator osoby, imię i nazwisko, płeć, adres itp.
Rodzaje wykresów
Wykresy można podzielić na dwa typy:
- Wykres nieskierowany
- Kierowany wykres
Wykres nieskierowany: Graf, którego krawędzie nie mają kierunku, nazywany jest grafem nieskierowanym. Krawędzie tego wykresu implikują dwukierunkową relację, w której każdą krawędź można pokonać w obu kierunkach. Poniższy rysunek przedstawia prosty graf nieskierowany z czterema węzłami i pięcioma krawędziami.
Rysunek 3: Prosty graf nieskierowany
Kierowany wykres: Wykres posiadający krawędzie z określonym kierunkiem nazywany jest grafem skierowanym. Krawędzie tego wykresu implikują relację jednokierunkową, w której każdą krawędź można pokonać tylko w jednym kierunku. Poniższy rysunek przedstawia prosty graf skierowany z czterema węzłami i pięcioma krawędziami.
Rysunek 4: Prosty graf skierowany
Bezwzględna długość, położenie lub orientacja krawędzi na wykresie charakterystycznie nie ma znaczenia. Innymi słowy, możemy wizualizować ten sam wykres na różne sposoby, zmieniając położenie wierzchołków lub zniekształcając krawędzie, jeśli podstawowa struktura wykresu nie ulegnie zmianie.
Co to są wykresy ważone?
Graf nazywa się ważonym, jeśli każdej krawędzi przypisano „wagę”. Waga krawędzi może oznaczać odległość, czas lub cokolwiek, co modeluje „połączenie” pomiędzy parą połączonych wierzchołków.
Na przykład na poniższym rysunku Grafu ważonego możemy zaobserwować niebieską liczbę obok każdej krawędzi. Liczba ta służy do oznaczenia ciężaru odpowiedniej krawędzi.
Rysunek 5: Przykład wykresu ważonego
Wprowadzenie do algorytmu Dijkstry
Teraz, gdy znamy już podstawowe pojęcia związane z wykresami, przejdźmy do zrozumienia koncepcji algorytmu Dijkstry.
Czy zastanawiałeś się kiedyś, w jaki sposób Mapy Google znajdują najkrótszą i najszybszą trasę między dwoma miejscami?
Cóż, odpowiedź brzmi Algorytm Dijkstry . Algorytm Dijkstry jest algorytmem graficznym który znajdzie najkrótszą ścieżkę z wierzchołka źródłowego do wszystkich pozostałych wierzchołków wykresu (najkrótsza ścieżka z jednego źródła). Jest to rodzaj algorytmu zachłannego, który działa tylko na wykresach ważonych o dodatnich wagach. Złożoność czasowa algorytmu Dijkstry wynosi O(V2) za pomocą reprezentacji wykresu za pomocą macierzy sąsiedztwa. Tym razem złożoność można zredukować do O((V + E) log V) za pomocą reprezentacji grafu na podstawie listy sąsiedztwa, gdzie W jest liczbą wierzchołków i I to liczba krawędzi w grafie.
Historia algorytmu Dijkstry
Algorytm Dijkstry został zaprojektowany i opublikowany przez Dr. Edsger W. Dijkstra , holenderski informatyk, inżynier oprogramowania, programista, eseista naukowy i naukowiec zajmujący się systemami.
Podczas wywiadu z Philipem L. Franą dla „Komunikacji” czasopisma ACM w 2001 roku dr Edsger W. Dijkstra ujawnił:
„Jak ogólnie jest najkrótsza droga dotarcia z Rotterdamu do Groningen: z danego miasta do danego miasta? Jest to algorytm najkrótszej ścieżki, który zaprojektowałem w około dwadzieścia minut. Pewnego ranka robiłem zakupy w Amsterdamie z moją młodą narzeczoną i zmęczeni, usiedliśmy na tarasie kawiarni, aby wypić filiżankę kawy i zastanawiałem się, czy dam radę, a następnie zaprojektowałem algorytm dla najkrótszej ścieżki . Jak mówiłem, był to wynalazek dwudziestominutowy. W rzeczywistości została opublikowana w 1959 r., trzy lata później. Publikację nadal można przeczytać, jest naprawdę całkiem ładna. Jednym z powodów, dla których jest taki ładny, było to, że zaprojektowałem go bez ołówka i papieru. Dowiedziałem się później, że jedną z zalet projektowania bez ołówka i papieru jest to, że niemal zmuszeni jesteśmy unikać wszelkich możliwych do uniknięcia komplikacji. W końcu, ku mojemu wielkiemu zdumieniu, algorytm ten stał się jednym z kamieni węgielnych mojej sławy.
Dijkstra myślał o problemie najkrótszej ścieżki, pracując jako programista w Centrum Matematycznym w Amsterdamie w 1956 roku, aby zilustrować możliwości nowego komputera znanego jako ARMAC. Jego celem było wybranie zarówno problemu, jak i rozwiązania (wygenerowanego przez komputer), które osoby niemające wiedzy komputerowej byłyby w stanie zrozumieć. Opracował algorytm najkrótszej ścieżki, a później wykonał go dla ARMAC dla niejasno skróconej mapy transportowej 64 miast w Holandii (64 miasta, więc do zakodowania numeru miasta wystarczyłoby 6 bitów). Rok później inżynierowie sprzętu obsługujący kolejny komputer instytutu natknął się na kolejną kwestię: Zminimalizuj ilość przewodów wymaganych do podłączenia pinów na tylnym panelu maszyny. Jako rozwiązanie ponownie odkrył algorytm zwany algorytmem minimalnego drzewa rozpinającego Prima i opublikował go w roku 1959.
Podstawy algorytmu Dijkstry
Poniżej przedstawiono podstawowe pojęcia algorytmu Dijkstry:
- Algorytm Dijkstry zaczyna się od wybranego przez nas węzła (węzła źródłowego) i sprawdza graf w celu znalezienia najkrótszej ścieżki między tym węzłem a wszystkimi pozostałymi węzłami na wykresie.
- Algorytm rejestruje aktualnie uznaną najkrótszą odległość od każdego węzła do węzła źródłowego i aktualizuje te wartości, jeśli znajdzie krótszą ścieżkę.
- Gdy algorytm pobierze najkrótszą ścieżkę między źródłem a innym węzłem, węzeł ten zostaje oznaczony jako „odwiedzony” i uwzględniony w ścieżce.
- Procedura jest kontynuowana do momentu, aż wszystkie węzły grafu zostaną uwzględnione w ścieżce. W ten sposób otrzymujemy ścieżkę łączącą węzeł źródłowy ze wszystkimi innymi węzłami, podążającą najkrótszą możliwą ścieżką dotarcia do każdego węzła.
Zrozumienie działania algorytmu Dijkstry
A wykres I wierzchołek źródłowy są wymaganiami dla algorytmu Dijkstry. Algorytm ten opiera się na podejściu zachłannym i w ten sposób znajduje lokalnie optymalny wybór (w tym przypadku lokalne minima) na każdym etapie algorytmu.
Każdy wierzchołek w tym algorytmie będzie miał zdefiniowane dwie właściwości:
- Odwiedzony obiekt
- Właściwość ścieżki
Przyjrzyjmy się pokrótce tym właściwościom.
Odwiedzony obiekt:
- Właściwość „visited” wskazuje, czy węzeł został odwiedzony, czy nie.
- Używamy tej właściwości, aby nie odwiedzać ponownie żadnego węzła.
- Węzeł zostaje oznaczony jako odwiedzony dopiero po znalezieniu najkrótszej ścieżki.
Właściwość ścieżki:
- Właściwość „path” przechowuje wartość bieżącej minimalnej ścieżki do węzła.
- Obecna minimalna ścieżka oznacza najkrótszą drogę, jaką dotarliśmy do tego węzła.
- Ta właściwość jest korygowana po odwiedzeniu dowolnego sąsiada węzła.
- Ta właściwość jest istotna, ponieważ przechowuje ostateczną odpowiedź dla każdego węzła.
Początkowo zaznaczamy wszystkie wierzchołki, czyli węzły, nieodwiedzone, ponieważ nie zostały jeszcze odwiedzone. Ścieżka do wszystkich węzłów jest również ustawiona na nieskończoność, z wyjątkiem węzła źródłowego. Ponadto ścieżka do węzła źródłowego jest ustawiona na zero (0).
Następnie wybieramy węzeł źródłowy i oznaczamy go jako odwiedzony. Następnie uzyskujemy dostęp do wszystkich sąsiadujących węzłów węzła źródłowego i przeprowadzamy relaksację w każdym węźle. Relaksacja to proces obniżania kosztu dotarcia do węzła za pomocą innego węzła.
W procesie relaksacji ścieżka każdego węzła jest korygowana do minimalnej wartości spośród bieżącej ścieżki węzła, sumy ścieżki do poprzedniego węzła i ścieżki od poprzedniego węzła do bieżącego węzła.
Załóżmy, że p[n] jest wartością bieżącej ścieżki dla węzła n, p[m] jest wartością ścieżki do poprzednio odwiedzonego węzła m, a w jest wagą krawędzi pomiędzy bieżącym węzłem a poprzednio odwiedzany (waga krawędzi pomiędzy n i m).
W sensie matematycznym relaksację można przedstawić jako:
p[n] = minimum(p[n], p[m] + w)
Następnie w każdym kolejnym kroku oznaczamy nieodwiedzony węzeł z najmniejszą ścieżką jako odwiedzony i aktualizujemy ścieżki jego sąsiadów.
Powtarzamy tę procedurę, aż wszystkie węzły na wykresie zostaną oznaczone jako odwiedzone.
Ilekroć dodamy węzeł do odwiedzanego zbioru, ścieżka do wszystkich sąsiadujących węzłów również się odpowiednio zmieni.
Jeśli jakikolwiek węzeł pozostanie nieosiągalny (odłączony komponent), jego ścieżka pozostaje „nieskończona”. W przypadku, gdy samo źródło jest oddzielnym komponentem, ścieżka do wszystkich pozostałych węzłów pozostaje „nieskończona”.
Zrozumienie algorytmu Dijkstry na przykładzie
Oto krok, który wykonamy, aby wdrożyć algorytm Dijkstry:
Krok 1: Najpierw oznaczymy węzeł źródłowy bieżącą odległością 0, a pozostałe węzły ustawimy na INFINITY.
Krok 2: Następnie ustawimy nieodwiedzony węzeł o najmniejszej bieżącej odległości jako bieżący węzeł, załóżmy X.
Krok 3: Dla każdego sąsiada N bieżącego węzła X: Następnie dodamy bieżącą odległość X z wagą krawędzi łączącej X-N. Jeśli jest mniejsza niż bieżąca odległość N, ustaw ją jako nową aktualną odległość N.
Krok 4: Następnie oznaczymy bieżący węzeł X jako odwiedzony.
Krok 5: Powtórzymy proces od 'Krok 2' jeśli na grafie pozostał jakiś nieodwiedzony węzeł.
Przyjrzyjmy się teraz implementacji algorytmu na przykładzie:
następny skaner Java
Rysunek 6: Podany wykres
- Jako dane wejściowe wykorzystamy powyższy wykres z node A jako źródło.
- Najpierw oznaczymy wszystkie węzły jako nieodwiedzone.
- Ustalimy ścieżkę do 0 w węźle A I NIESKOŃCZONOŚĆ dla wszystkich pozostałych węzłów.
- Zaznaczymy teraz węzeł źródłowy A jako odwiedzane i uzyskują dostęp do sąsiadujących węzłów.
Notatka: Uzyskaliśmy dostęp tylko do sąsiednich węzłów, a nie odwiedziliśmy je. - Zaktualizujemy teraz ścieżkę do node B przez 4 przy pomocy relaksu, ponieważ ścieżka do węzła A Jest 0 i ścieżka z węzła A Do B Jest 4 , oraz minimum((0 + 4), NIESKOŃCZONOŚĆ) Jest 4 .
- Zaktualizujemy także ścieżkę do node C przez 5 przy pomocy relaksu, ponieważ ścieżka do węzła A Jest 0 i ścieżka z węzła A Do C Jest 5 , oraz minimum((0 + 5), NIESKOŃCZONOŚĆ) Jest 5 . Obaj sąsiedzi węzła A są teraz zrelaksowani; dlatego możemy iść dalej.
- Wybierzemy teraz następny nieodwiedzony węzeł z najmniejszą ścieżką i odwiedzimy go. Dlatego odwiedzimy węzeł B i relaksuje się na nieodwiedzanych sąsiadach. Po wykonaniu relaksacji ścieżka do węzła C pozostanie 5 , natomiast ścieżka do węzła I stanie się jedenaście i ścieżka do węzła D stanie się 13 .
- Odwiedzimy teraz węzeł I i wykonać relaksację na sąsiednich węzłach B, D , I F . Ponieważ tylko węzeł F nie jest odwiedzany, będzie zrelaksowany. Zatem ścieżka do węzła B pozostanie tak jak jest, tj. 4 , ścieżka do węzła D również pozostanie 13 i ścieżka do węzła F stanie się 14 (8 + 6) .
- Teraz odwiedzimy węzeł D i tylko węzeł F będzie zrelaksowany. Jednak ścieżka do node F pozostanie bez zmian, tj. 14 .
- Ponieważ tylko węzeł F pozostanie, odwiedzimy go, ale nie dokonamy żadnej relaksacji, ponieważ wszystkie sąsiednie węzły są już odwiedzone.
- Po odwiedzeniu wszystkich węzłów wykresów program zakończy się.
Dlatego ostateczne ścieżki, które doszliśmy do wniosku, to:
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)
Pseudokod algorytmu Dijkstry
Teraz zrozumiemy pseudokod algorytmu Dijkstry.
- Musimy prowadzić rejestr odległości ścieżki każdego węzła. Dlatego możemy przechowywać odległość ścieżki każdego węzła w tablicy o rozmiarze n, gdzie n to całkowita liczba węzłów.
- Co więcej, chcemy pobrać najkrótszą ścieżkę wraz z długością tej ścieżki. Aby rozwiązać ten problem, zamapujemy każdy węzeł na węzeł, który jako ostatni zaktualizował długość ścieżki.
- Po zakończeniu algorytmu możemy cofnąć się od węzła docelowego do węzła źródłowego, aby pobrać ścieżkę.
- Możemy użyć minimalnej kolejki priorytetowej, aby w efektywny sposób odzyskać węzeł o najmniejszej odległości ścieżki.
Zaimplementujmy teraz pseudokod z powyższej ilustracji:
Pseudo kod:
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]> Wyjaśnienie:
W powyższym fragmencie kodu umieściliśmy plik stdio.h plik nagłówkowy zdefiniował dwie stałe wartości: INF = 9999 I MAKS = 10 . Zadeklarowaliśmy prototypowanie funkcji, a następnie zdefiniowaliśmy funkcję dla algorytmu Dijkstry jako Algorytm Dijkstry który przyjmuje trzy argumenty — Graf składający się z węzłów, liczbę węzłów na Grafie i węzeł źródłowy. Wewnątrz tej funkcji zdefiniowaliśmy pewne struktury danych, takie jak macierz 2D, która będzie działać jako kolejka priorytetowa dla algorytmu, tablica do pomiaru odległości między węzłami, tablica do przechowywania rekordu poprzednich węzłów, tablica do przechowywania informacje o odwiedzonych węzłach i niektóre zmienne całkowite do przechowywania minimalnej wartości odległości, licznika, wartości następnego węzła i innych. Następnie użyliśmy a zagnieżdżona pętla for iterować po węzłach Grafu i odpowiednio dodawać je do kolejki priorytetowej. Ponownie skorzystaliśmy z dla pętli iterować po elementach kolejki priorytetowej, zaczynając od węzła źródłowego i aktualizować ich odległości. Poza pętlą ustawiliśmy odległość węzła źródłowego jako 0 i oznaczyłem go jako odwiedzony w odwiedzone_węzły[] szyk. Następnie ustawiliśmy wartość licznika na jeden i użyliśmy chwila pętla iterująca po liczbie węzłów. Wewnątrz tej pętli ustawiliśmy wartość minimalna_odległość Jak INF i użył dla pętli aby zaktualizować wartość minimalna_odległość zmienna o wartości minimalnej z a dystans[] szyk. Następnie wykonaliśmy iterację przez nieodwiedzone sąsiednie węzły wybranego węzła, używając metody dla pętli i wykonywał relaksację. Następnie wydrukowaliśmy uzyskane dane dotyczące odległości obliczonych przy użyciu algorytmu Dijkstry.
w główny funkcji zdefiniowaliśmy i zadeklarowaliśmy zmienne reprezentujące Graf, liczbę węzłów i węzeł źródłowy. W końcu zadzwoniliśmy do Algorytm Dijkstry() funkcję poprzez przekazanie wymaganych parametrów.
W rezultacie dla każdego węzła drukowane są wymagane najkrótsze możliwe ścieżki z węzła źródłowego.
Kod algorytmu Dijkstry w C++
Poniżej znajduje się implementacja algorytmu Dijkstry w języku programowania C++:
Plik: 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;> Wyjaśnienie:
W powyższym fragmencie kodu umieściliśmy plik „iostream” I 'wektor' pliki nagłówkowe i zdefiniowano stałą wartość jako MAX_INT = 10000000 . Następnie użyliśmy standardowej przestrzeni nazw i stworzyliśmy prototyp pliku Algorytm Dijkstry() funkcjonować. Następnie zdefiniowaliśmy główną funkcję programu, którą nazwaliśmy Algorytm Dijkstry() funkcjonować. Następnie zadeklarowaliśmy kilka klas do tworzenia wierzchołków i krawędzi. Stworzyliśmy także prototypy większej liczby funkcji, aby znaleźć najkrótszą możliwą ścieżkę od wierzchołka źródłowego do wierzchołka docelowego i utworzyliśmy instancje klas Vertex i Edge. Następnie zdefiniowaliśmy obie klasy, aby utworzyć wierzchołki i krawędzie grafu. Następnie zdefiniowaliśmy Algorytm Dijkstry() funkcję tworzenia wykresu i wykonywania różnych operacji. Wewnątrz tej funkcji zadeklarowaliśmy kilka wierzchołków i krawędzi. Następnie ustalamy wierzchołek źródłowy grafu i nazywamy go Dijkstry() funkcja znajdowania najkrótszej możliwej odległości i Print_Shortest_Route_To() funkcja drukująca najkrótszą odległość od wierzchołka źródłowego do wierzchołka 'F' . Następnie zdefiniowaliśmy Dijkstry() funkcja obliczająca możliwie najkrótszą odległość wszystkich wierzchołków od wierzchołka źródłowego. Zdefiniowaliśmy także kilka dodatkowych funkcji, aby znaleźć wierzchołek o najkrótszej odległości, zwrócić wszystkie wierzchołki sąsiadujące z pozostałym wierzchołkiem, zwrócić odległość pomiędzy dwoma połączonymi wierzchołkami, sprawdzić, czy wybrany wierzchołek istnieje na grafie i wydrukować najkrótsza możliwa ścieżka od wierzchołka źródłowego do wierzchołka docelowego.
W rezultacie wymagana najkrótsza ścieżka dla wierzchołka 'F' z węzła źródłowego jest drukowany dla użytkowników.
Kod algorytmu Dijkstry w Javie
Poniżej znajduje się implementacja algorytmu Dijkstry w języku programowania Java:
Plik: 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;> Wyjaśnienie:
W powyższym fragmencie kodu zdefiniowaliśmy klasę publiczną jako Algorytm Dijkstry() . Wewnątrz tej klasy zdefiniowaliśmy metodę publiczną jako algorytm dijkstra() aby znaleźć najkrótszą odległość od wierzchołka źródłowego do wierzchołka docelowego. Wewnątrz tej metody zdefiniowaliśmy zmienną przechowującą liczbę węzłów. Następnie zdefiniowaliśmy tablicę logiczną do przechowywania informacji dotyczących odwiedzanych wierzchołków oraz tablicę liczb całkowitych do przechowywania odpowiednich odległości. Początkowo zadeklarowaliśmy wartości w obu tablicach jako FAŁSZ I MAKSYMALNA WARTOŚĆ odpowiednio. Ustawiliśmy również odległość wierzchołka źródłowego na zero i zastosowaliśmy dla pętli aby zaktualizować odległość między wierzchołkiem źródłowym a wierzchołkami docelowymi o minimalną odległość. Następnie zaktualizowaliśmy odległości sąsiednich wierzchołków wybranego wierzchołka, wykonując relaksację i wydrukowaliśmy najkrótsze odległości dla każdego wierzchołka. Następnie zdefiniowaliśmy metodę znajdowania minimalnej odległości od wierzchołka źródłowego do wierzchołka docelowego. Następnie zdefiniowaliśmy główną funkcję, w której zadeklarowaliśmy wierzchołki grafu i utworzyliśmy instancję Algorytm Dijkstry() klasa. W końcu zadzwoniliśmy do algorytm dijkstra() metoda znalezienia najkrótszej odległości między wierzchołkiem źródłowym a wierzchołkami docelowymi.
W rezultacie dla każdego węzła drukowane są wymagane najkrótsze możliwe ścieżki z węzła źródłowego.
Kod algorytmu Dijkstry w Pythonie
Poniżej znajduje się implementacja algorytmu Dijkstry w języku programowania Python:
Plik: 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>
Wyjście
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
Wyjaśnienie:
W powyższym fragmencie kodu zaimportowaliśmy plik sys moduł i zadeklarował listy składające się z wartości węzłów i krawędzi. Następnie zdefiniowaliśmy funkcję jako doBeVisited() aby dowiedzieć się, który węzeł zostanie odwiedzony jako następny. Następnie obliczyliśmy całkowitą liczbę węzłów na wykresie i ustaliliśmy początkowe odległości dla każdego węzła. Następnie obliczyliśmy minimalną odległość od węzła źródłowego do węzła docelowego, wykonaliśmy relaksację na sąsiednich węzłach i zaktualizowaliśmy odległości na liście. Następnie wydrukowaliśmy te odległości z listy dla użytkowników.
W rezultacie dla każdego węzła drukowane są wymagane najkrótsze możliwe ścieżki z węzła źródłowego.
Złożoność czasowo-przestrzenna algorytmu Dijkstry
- Złożoność czasowa algorytmu Dijkstry wynosi O(E log V) , gdzie E jest liczbą krawędzi, a V jest liczbą wierzchołków.
- Złożoność przestrzenna algorytmu Dijkstry wynosi O(V), gdzie V jest liczbą wierzchołków.
Zalety i wady algorytmu Dijkstry
Omówmy niektóre zalety algorytmu Dijkstry:
- Jedną z głównych zalet stosowania algorytmu Dijkstry jest to, że ma on niemal liniową złożoność czasową i przestrzenną.
- Możemy użyć tego algorytmu do obliczenia najkrótszej ścieżki z pojedynczego wierzchołka do wszystkich pozostałych wierzchołków oraz z jednego wierzchołka źródłowego do pojedynczego wierzchołka docelowego, zatrzymując algorytm po uzyskaniu najkrótszej odległości dla wierzchołka docelowego.
- Algorytm ten działa tylko w przypadku skierowanych grafów ważonych i wszystkie krawędzie tego wykresu powinny być nieujemne.
Pomimo wielu zalet algorytm Dijkstry ma również pewne wady, takie jak:
- Algorytm Dijkstry przeprowadza ukrytą eksplorację, która zajmuje dużo czasu.
- Algorytm ten nie radzi sobie z ujemnymi krawędziami.
- Ponieważ algorytm ten kieruje się do wykresu acyklicznego, nie może obliczyć dokładnie najkrótszej ścieżki.
- Prowadzenie rejestru odwiedzonych wierzchołków wymaga również konserwacji.
Niektóre zastosowania algorytmu Dijkstry
Algorytm Dijkstry ma różne zastosowania w świecie rzeczywistym, z których niektóre są wymienione poniżej:
Konkluzja
- W powyższym tutorialu, po pierwsze, zrozumieliśmy podstawowe pojęcia Graph wraz z jego typami i zastosowaniami.
- Następnie dowiedzieliśmy się o algorytmie Dijkstry i jego historii.
- Na przykładzie zrozumieliśmy także podstawowe działanie algorytmu Dijkstry.
- Następnie uczyliśmy się, jak napisać kod dla algorytmu Dijkstry za pomocą pseudokodu.
- Zaobserwowaliśmy jego implementację w językach programowania takich jak C, C++, Java i Python, wraz z odpowiednimi wynikami i objaśnieniami.
- Zrozumieliśmy także złożoność czasowo-przestrzenną algorytmu Dijkstry.
- Na koniec omówiliśmy zalety i wady algorytmu Dijkstry oraz niektóre jego zastosowania w życiu codziennym.