Il seguente tutorial ci insegnerà l'algoritmo del percorso più breve di Dijkstra. Comprenderemo il funzionamento dell'algoritmo di Dijkstra con una spiegazione grafica passo passo.
Tratteremo quanto segue:
- Una breve panoramica dei concetti fondamentali del grafico
- Comprendere l'uso dell'algoritmo di Dijkstra
- Comprendere il funzionamento dell'algoritmo con un esempio passo passo
Quindi iniziamo.
Una breve introduzione ai grafici
Grafici sono strutture dati non lineari che rappresentano le 'connessioni' tra gli elementi. Questi elementi sono conosciuti come Vertici , e le linee o gli archi che collegano due vertici qualsiasi nel grafico sono noti come Bordi . Più formalmente, un grafico comprende un insieme di vertici (V) E una serie di bordi (E) . Il grafico è indicato con SOL(V, E) .
Componenti di un grafico
La figura seguente mostra una rappresentazione grafica di un grafico:
Figura 1: Rappresentazione grafica di un grafico
Nella figura sopra, i vertici/nodi sono indicati con cerchi colorati e i bordi sono indicati con le linee che collegano i nodi.
Applicazioni dei grafici
I grafici vengono utilizzati per risolvere molti problemi della vita reale. I grafici vengono utilizzati per rappresentare le reti. Queste reti possono includere reti telefoniche o di circuiti o percorsi in una città.
Ad esempio, potremmo utilizzare i grafici per progettare un modello di rete di trasporti in cui i vertici mostrano le strutture che inviano o ricevono i prodotti e i bordi rappresentano strade o percorsi che li collegano. Quella che segue è una rappresentazione pittorica dello stesso:
Figura 2: Rappresentazione pittorica della rete di trasporti
I grafici vengono utilizzati anche in diverse piattaforme di social media come LinkedIn, Facebook, Twitter e altre. Ad esempio, piattaforme come Facebook utilizzano i grafici per memorizzare i dati dei propri utenti in cui ogni persona è indicata con un vertice e ognuno di essi è una struttura contenente informazioni come ID persona, nome, sesso, indirizzo, ecc.
Tipi di grafici
I grafici possono essere classificati in due tipologie:
- Grafico non orientato
- Grafico diretto
Grafico non orientato: Un grafico con bordi che non hanno una direzione è chiamato grafico non orientato. I bordi di questo grafico implicano una relazione bidirezionale in cui ciascun bordo può essere attraversato in entrambe le direzioni. La figura seguente mostra un semplice grafo non orientato con quattro nodi e cinque archi.
Figura 3: Un semplice grafico non orientato
Grafico diretto: Un grafico con bordi con direzione è chiamato grafico diretto. I bordi di questo grafico implicano una relazione unidirezionale in cui ciascun bordo può essere attraversato solo in un'unica direzione. La figura seguente mostra un semplice grafo diretto con quattro nodi e cinque spigoli.
Figura 4: Un semplice grafico diretto
La lunghezza, la posizione o l'orientamento assoluto dei bordi in un'illustrazione grafica tipicamente non ha significato. In altre parole, possiamo visualizzare lo stesso grafico in modi diversi riorganizzando i vertici o distorcendo i bordi se la struttura sottostante del grafico non si altera.
Cosa sono i grafici ponderati?
Un grafico si dice ponderato se a ciascun bordo viene assegnato un 'peso'. Il peso di un bordo può denotare la distanza, il tempo o qualsiasi cosa che modelli la 'connessione' tra la coppia di vertici che collega.
Ad esempio, possiamo osservare un numero blu accanto a ciascun bordo nella seguente figura del grafico ponderato. Questo numero viene utilizzato per indicare il peso del bordo corrispondente.
Figura 5: Un esempio di grafico ponderato
Un'introduzione all'algoritmo di Dijkstra
Ora che conosciamo alcuni concetti base dei grafici, tuffiamoci nella comprensione del concetto di algoritmo di Dijkstra.
Ti sei mai chiesto come fa Google Maps a trovare il percorso più breve e veloce tra due luoghi?
Bene, la risposta è Algoritmo di Dijkstra . Algoritmo di Dijkstra è un algoritmo grafico che trova la via più breve da un vertice sorgente a tutti gli altri vertici nel grafico (percorso più breve a sorgente singola). È un tipo di algoritmo goloso che funziona solo su grafici ponderati con pesi positivi. La complessità temporale dell'algoritmo di Dijkstra è O(V2) con l'aiuto della rappresentazione della matrice di adiacenza del grafico. Questa volta la complessità può essere ridotta a O((V + E)logV) con l'aiuto di una rappresentazione dell'elenco di adiacenze del grafico, dove IN è il numero di vertici e E è il numero di archi nel grafico.
formatodata.formato java
Storia dell'algoritmo di Dijkstra
L'algoritmo di Dijkstra è stato progettato e pubblicato da Dott. Edsger W. Dijkstra , scienziato informatico, ingegnere informatico, programmatore, saggista scientifico e scienziato di sistema olandese.
Durante un'intervista con Philip L. Frana per le comunicazioni della rivista ACM nel 2001, il dottor Edsger W. Dijkstra ha rivelato:
«Qual è il modo più breve per viaggiare da Rotterdam a Groningen, in generale: da una determinata città a una determinata città? È l'algoritmo per il percorso più breve, che ho progettato in una ventina di minuti. Una mattina stavo facendo shopping ad Amsterdam con la mia giovane fidanzata e, stanchi, ci siamo seduti sulla terrazza del bar per bere una tazza di caffè e stavo pensando se potevo farlo, e poi ho progettato l'algoritmo per il percorso più breve . Come ho detto, è stata un'invenzione di venti minuti. Infatti venne pubblicato nel '59, tre anni dopo. La pubblicazione è ancora leggibile, in effetti è piuttosto carina. Uno dei motivi per cui è così carino è che l'ho disegnato senza carta e matita. Ho appreso in seguito che uno dei vantaggi di progettare senza carta e matita è che sei quasi costretto a evitare tutte le complessità evitabili. Alla fine, quell'algoritmo divenne, con mio grande stupore, uno dei pilastri della mia fama.'
Dijkstra pensò al problema del percorso più breve mentre lavorava come programmatore presso il Centro Matematico di Amsterdam nel 1956 per illustrare le capacità di un nuovo computer noto come ARMAC. Il suo obiettivo era selezionare sia un problema che una soluzione (prodotta dal computer) che le persone senza esperienza informatica potessero comprendere. Ha sviluppato l’algoritmo del percorso più breve e successivamente lo ha eseguito per ARMAC per una mappa dei trasporti vagamente abbreviata di 64 città nei Paesi Bassi (64 città, quindi 6 bit sarebbero sufficienti per codificare il numero della città). Un anno dopo, si è imbattuto in un altro problema da parte degli ingegneri hardware che utilizzavano il computer successivo dell'istituto: ridurre al minimo la quantità di cavo necessaria per collegare i pin sul pannello posteriore della macchina. Come soluzione, riscoprì l'algoritmo chiamato algoritmo dell'albero di copertura minimo di Prim e lo pubblicò nel 1959.
Fondamenti dell'algoritmo di Dijkstra
Di seguito sono riportati i concetti di base dell'algoritmo di Dijkstra:
- L'algoritmo di Dijkstra inizia dal nodo che selezioniamo (il nodo sorgente) ed esamina il grafico per trovare il percorso più breve tra quel nodo e tutti gli altri nodi nel grafico.
- L'algoritmo registra la distanza più breve attualmente riconosciuta da ciascun nodo al nodo sorgente e aggiorna questi valori se trova un percorso più breve.
- Una volta che l'algoritmo ha recuperato il percorso più breve tra la sorgente e un altro nodo, quel nodo viene contrassegnato come 'visitato' e incluso nel percorso.
- La procedura continua finché tutti i nodi del grafico non sono stati inclusi nel percorso. In questo modo, abbiamo un percorso che collega il nodo sorgente a tutti gli altri nodi, seguendo il percorso più breve possibile per raggiungere ciascun nodo.
Comprendere il funzionamento dell'algoritmo di Dijkstra
UN grafico E vertice sorgente sono i requisiti per l'algoritmo di Dijkstra. Questo algoritmo è basato sull’approccio Greedy e quindi trova la scelta ottimale a livello locale (minimi locali in questo caso) in ogni fase dell’algoritmo.
Ogni vertice in questo algoritmo avrà due proprietà definite per esso:
- Proprietà visitata
- Proprietà del percorso
Cerchiamo di comprendere queste proprietà in breve.
Immobile visitato:
- La proprietà 'visited' indica se il nodo è stato visitato o meno.
- Stiamo utilizzando questa proprietà in modo da non rivisitare alcun nodo.
- Un nodo viene contrassegnato come visitato solo quando è stato trovato il percorso più breve.
Proprietà del percorso:
- La proprietà 'path' memorizza il valore del percorso minimo corrente al nodo.
- Il percorso minimo attuale implica la via più breve con cui abbiamo raggiunto questo nodo fino ad ora.
- Questa proprietà viene rivista quando viene visitato un vicino del nodo.
- Questa proprietà è significativa perché memorizzerà la risposta finale per ciascun nodo.
Inizialmente contrassegniamo tutti i vertici, o nodi, non visitati poiché devono ancora essere visitati. Anche il percorso verso tutti i nodi è impostato su infinito a parte il nodo di origine. Inoltre, il percorso del nodo sorgente è impostato su zero (0).
Selezioniamo quindi il nodo di origine e lo contrassegniamo come visitato. Successivamente, accediamo a tutti i nodi vicini al nodo sorgente ed eseguiamo il rilassamento su ogni nodo. Il rilassamento è il processo di riduzione del costo per raggiungere un nodo con l'aiuto di un altro nodo.
Nel processo di rilassamento, il percorso di ciascun nodo viene rivisto al valore minimo tra il percorso corrente del nodo, la somma del percorso al nodo precedente e il percorso dal nodo precedente al nodo corrente.
Supponiamo che p[n] sia il valore del percorso corrente per il nodo n, p[m] sia il valore del percorso fino al nodo m precedentemente visitato e w sia il peso del bordo tra il nodo corrente e quello visitato in precedenza (peso del bordo compreso tra n e m).
In senso matematico, il rilassamento può essere esemplificato come:
p[n] = minimo(p[n], p[m] + w)
Quindi contrassegniamo un nodo non visitato con il percorso minimo come visitato in ogni passaggio successivo e aggiorniamo i percorsi del suo vicino.
Ripetiamo questa procedura finché tutti i nodi nel grafico non saranno contrassegnati come visitati.
Ogni volta che aggiungiamo un nodo all'insieme visitato, anche il percorso verso tutti i nodi vicini cambia di conseguenza.
Se un nodo rimane irraggiungibile (componente disconnesso), il suo percorso rimane 'infinito'. Nel caso in cui la sorgente stessa sia un componente separato, il percorso verso tutti gli altri nodi rimane 'infinito'.
Comprendere l'algoritmo di Dijkstra con un esempio
Quello che segue è il passaggio che seguiremo per implementare l'algoritmo di Dijkstra:
Passo 1: Per prima cosa contrassegneremo il nodo sorgente con una distanza attuale pari a 0 e imposteremo il resto dei nodi su INFINITO.
Passo 2: Imposteremo quindi il nodo non visitato con la distanza corrente più piccola come nodo corrente, supponiamo X.
Passaggio 3: Per ogni vicino N del nodo attuale X: Aggiungeremo quindi la distanza attuale di X con il peso del bordo che congiunge X-N. Se è inferiore alla distanza attuale di N, impostala come la nuova distanza attuale di N.
Passaggio 4: Contrassegneremo quindi il nodo corrente X come visitato.
Passaggio 5: Ripeteremo il processo da 'Passo 2' se nel grafico è rimasto qualche nodo non visitato.
Cerchiamo ora di comprendere l'implementazione dell'algoritmo con l'aiuto di un esempio:
Figura 6: Il grafico dato
- Utilizzeremo il grafico sopra come input, con node UN come fonte.
- Per prima cosa contrassegneremo tutti i nodi come non visitati.
- Stabiliremo il percorso verso 0 al nodo UN E INFINITO per tutti gli altri nodi.
- Ora contrassegneremo il nodo di origine UN come visitato e accedere ai nodi vicini.
Nota: Abbiamo avuto accesso solo ai nodi vicini, non li abbiamo visitati. - Ora aggiorneremo il percorso di node B di 4 con l'aiuto del rilassamento perché il percorso verso il nodo UN È 0 e il percorso da node UN A B È 4 , e il minimo((0 + 4), INFINITO) È 4 .
- Aggiorneremo anche il percorso di node C di 5 con l'aiuto del rilassamento perché il percorso verso il nodo UN È 0 e il percorso da node UN A C È 5 , e il minimo((0 + 5), INFINITO) È 5 . Entrambi i vicini di node UN ora sono rilassati; quindi possiamo andare avanti.
- Ora selezioneremo il successivo nodo non visitato con il percorso minimo e lo visiteremo. Quindi visiteremo node B ed eseguire il rilassamento sui suoi vicini non visitati. Dopo aver eseguito il rilassamento, il percorso verso node C resterà 5 , mentre il percorso verso node E diventerà undici e il percorso di node D diventerà 13 .
- Visiteremo ora node E ed eseguire il rilassamento sui nodi vicini B, D , E F . Poiché solo node F non è visitato, sarà rilassato. Pertanto, il percorso verso node B rimarrà così com'è, cioè 4 , il percorso del nodo D resterà anche 13 e il percorso di node F diventerà 14 (8+6) .
- Ora visiteremo node D , e unico nodo F sarà rilassato. Tuttavia, il percorso verso node F rimarrà invariato, ovvero 14 .
- Poiché solo node F rimane, lo visiteremo ma non effettueremo alcun rilassamento poiché tutti i suoi nodi vicini sono già visitati.
- Una volta visitati tutti i nodi dei grafici il programma terminerà.
Quindi, i percorsi finali che abbiamo concluso sono:
Serie di fibonacci in Java
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)
Pseudocodice per l'algoritmo di Dijkstra
Comprenderemo ora uno pseudocodice per l'algoritmo di Dijkstra.
metodo uguale in Java
- Dobbiamo mantenere un registro della distanza del percorso di ogni nodo. Pertanto, possiamo memorizzare la distanza del percorso di ciascun nodo in un array di dimensione n, dove n è il numero totale di nodi.
- Inoltre, vogliamo recuperare il percorso più breve insieme alla lunghezza di quel percorso. Per superare questo problema, mapperemo ciascun nodo sul nodo che ha aggiornato per ultimo la sua lunghezza del percorso.
- Una volta completato l'algoritmo, possiamo tornare indietro dal nodo di destinazione al nodo di origine per recuperare il percorso.
- Possiamo utilizzare una coda con priorità minima per recuperare il nodo con la distanza di percorso minima in modo efficiente.
Implementiamo ora uno pseudocodice dell'illustrazione sopra:
Pseudocodice:
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]> Spiegazione:
Nello snippet di codice sopra, abbiamo incluso il file stdio.h il file di intestazione ha definito due valori costanti: INF = 9999 E MASSIMO = 10 . Abbiamo dichiarato la prototipazione della funzione e quindi definito la funzione per l'algoritmo di Dijkstra come Algoritmo Dijkstra che accetta tre argomenti: il grafico costituito dai nodi, il numero di nodi nel grafico e il nodo di origine. All'interno di questa funzione abbiamo definito alcune strutture dati come una matrice 2D che funzionerà come Priority Queue per l'algoritmo, un array per mantenere la distanza tra i nodi, un array per mantenere il record dei nodi precedenti, un array per memorizzare le informazioni sui nodi visitati e alcune variabili intere per memorizzare il valore della distanza minima, il contatore, il valore del nodo successivo e altro. Abbiamo quindi utilizzato a ciclo for nidificato per scorrere i nodi del grafico e aggiungerli di conseguenza alla coda di priorità. Abbiamo nuovamente utilizzato il ciclo for per scorrere gli elementi nella coda di priorità a partire dal nodo sorgente e aggiornare le loro distanze. Al di fuori del ciclo, abbiamo impostato la distanza del nodo sorgente come 0 e contrassegnarlo come visitato nel file nodi_visitati[] vettore. Successivamente impostiamo il valore del contatore su uno e utilizziamo il file Mentre ripetere il ciclo attraverso il numero di nodi. All'interno di questo ciclo, abbiamo impostato il valore di distanza_minima COME INF e utilizzato il ciclo for per aggiornare il valore di distanza_minima variabile con il valore minimo da a distanza[] vettore. Abbiamo quindi ripetuto i nodi vicini non visitati del nodo selezionato utilizzando il comando ciclo for ed eseguito il rilassamento. Abbiamo quindi stampato i dati risultanti delle distanze calcolate utilizzando l'algoritmo di Dijkstra.
Nel principale funzione, abbiamo definito e dichiarato le variabili che rappresentano il grafico, il numero di nodi e il nodo sorgente. Alla fine, abbiamo chiamato il Algoritmo Dijkstra() funzione passando i parametri richiesti.
Di conseguenza, per gli utenti vengono stampati i percorsi più brevi possibili richiesti per ogni nodo dal nodo di origine.
Codice per l'algoritmo di Dijkstra in C++
Quella che segue è l'implementazione dell'algoritmo di Dijkstra nel linguaggio di programmazione C++:
File: 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;> Spiegazione:
Nello snippet di codice sopra, abbiamo incluso il file 'iostream' E 'vettore' file di intestazione e definito un valore costante come MAX_INT = 10000000 . Abbiamo quindi utilizzato lo spazio dei nomi standard e abbiamo prototipato il file Algoritmo Dijkstra() funzione. Abbiamo poi definito la funzione principale del programma all'interno, che abbiamo chiamato Algoritmo Dijkstra() funzione. Successivamente, abbiamo dichiarato alcune classi per creare vertici e spigoli. Abbiamo anche prototipato più funzioni per trovare il percorso più breve possibile dal vertice di origine al vertice di destinazione e abbiamo istanziato le classi Vertex ed Edge. Abbiamo quindi definito entrambe le classi per creare i vertici e i bordi del grafico. Abbiamo quindi definito l Algoritmo Dijkstra() funzione per creare un grafico ed eseguire diverse operazioni. All'interno di questa funzione abbiamo dichiarato alcuni vertici e spigoli. Impostiamo quindi il vertice sorgente del grafico e chiamiamo il file Dijkstra() funzione per trovare la distanza più breve possibile e Print_Shortest_Route_To() funzione per stampare la distanza più breve dal vertice di origine al vertice 'F' . Abbiamo quindi definito l Dijkstra() funzione per calcolare le distanze più brevi possibili di tutti i vertici dal vertice sorgente. Abbiamo anche definito alcune altre funzioni per trovare il vertice con la distanza più breve per restituire tutti i vertici adiacenti al vertice rimanente, per restituire la distanza tra due vertici collegati, per verificare se il vertice selezionato esiste nel grafico e per stampare il percorso più breve possibile dal vertice sorgente al vertice destinazione.
Di conseguenza, il percorso più breve richiesto per il vertice 'F' dal nodo di origine viene stampato per gli utenti.
Codice per l'algoritmo di Dijkstra in Java
Quella che segue è l'implementazione dell'algoritmo di Dijkstra nel linguaggio di programmazione Java:
File: 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;> Spiegazione:
Nello snippet di codice sopra, abbiamo definito una classe pubblica come Algoritmo Dijkstra() . All'interno di questa classe, abbiamo definito un metodo pubblico come Algoritmo dijkstra() per trovare la distanza più breve dal vertice di origine al vertice di destinazione. All'interno di questo metodo, abbiamo definito una variabile per memorizzare il numero di nodi. Abbiamo quindi definito un array booleano per memorizzare le informazioni relative ai vertici visitati e un array di interi per memorizzare le rispettive distanze. Inizialmente, abbiamo dichiarato i valori in entrambi gli array come Falso E MAX_VALORE , rispettivamente. Abbiamo anche impostato la distanza del vertice sorgente su zero e utilizzato il metodo ciclo for per aggiornare la distanza tra il vertice di origine e i vertici di destinazione con la distanza minima. Abbiamo quindi aggiornato le distanze dei vertici vicini al vertice selezionato eseguendo il rilassamento e stampato le distanze più brevi per ogni vertice. Abbiamo quindi definito un metodo per trovare la distanza minima dal vertice sorgente al vertice destinazione. Abbiamo quindi definito la funzione principale in cui abbiamo dichiarato i vertici del grafico e istanziato il file Algoritmo Dijkstra() classe. Infine, abbiamo chiamato il Algoritmo dijkstra() metodo per trovare la distanza più breve tra il vertice di origine e i vertici di destinazione.
Di conseguenza, per gli utenti vengono stampati i percorsi più brevi possibili richiesti per ogni nodo dal nodo di origine.
Codice per l'algoritmo di Dijkstra in Python
Quella che segue è l'implementazione dell'algoritmo di Dijkstra nel linguaggio di programmazione Python:
File: 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>
Produzione
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
Spiegazione:
Nello snippet di codice sopra, abbiamo importato il file sistema module e dichiarate le liste costituite dai valori per i nodi e gli spigoli. Abbiamo quindi definito una funzione come esserevisitato() per scoprire quale nodo verrà visitato successivamente. Abbiamo quindi trovato il numero totale di nodi nel grafico e impostato le distanze iniziali per ogni nodo. Abbiamo quindi calcolato la distanza minima dal nodo sorgente al nodo destinazione, eseguito il rilassamento sui nodi vicini e aggiornato le distanze nell'elenco. Abbiamo quindi stampato tali distanze dall'elenco per gli utenti.
Di conseguenza, per gli utenti vengono stampati i percorsi più brevi possibili richiesti per ogni nodo dal nodo di origine.
Complessità temporale e spaziale dell'algoritmo di Dijkstra
- La complessità temporale dell'algoritmo di Dijkstra lo è O(E logV) , dove E è il numero di spigoli e V è il numero di vertici.
- La complessità spaziale dell'algoritmo di Dijkstra è O(V), dove V è il numero di vertici.
Vantaggi e svantaggi dell'algoritmo di Dijkstra
Parliamo di alcuni vantaggi dell'algoritmo di Dijkstra:
- Uno dei vantaggi principali dell'utilizzo dell'algoritmo di Dijkstra è che ha una complessità temporale e spaziale quasi lineare.
- Possiamo utilizzare questo algoritmo per calcolare il percorso più breve da un singolo vertice a tutti gli altri vertici e da un singolo vertice sorgente a un singolo vertice di destinazione interrompendo l'algoritmo una volta ottenuta la distanza più breve per il vertice di destinazione.
- Questo algoritmo funziona solo per grafici ponderati diretti e tutti i bordi di questo grafico dovrebbero essere non negativi.
Nonostante abbia molteplici vantaggi, l'algoritmo di Dijkstra presenta anche alcuni svantaggi, come:
- L'algoritmo di Dijkstra esegue un'esplorazione nascosta che utilizza molto tempo durante il processo.
- Questo algoritmo è impotente nel gestire i fronti negativi.
- Poiché questo algoritmo punta al grafico aciclico, non può calcolare esattamente il percorso più breve.
- Richiede inoltre manutenzione per tenere traccia dei vertici che sono stati visitati.
Alcune applicazioni dell'algoritmo di Dijkstra
L'algoritmo di Dijkstra ha varie applicazioni nel mondo reale, alcune delle quali sono indicate di seguito:
La conclusione
- Nel tutorial sopra, in primo luogo, abbiamo compreso i concetti di base di Graph insieme ai suoi tipi e applicazioni.
- Abbiamo poi appreso dell'algoritmo di Dijkstra e della sua storia.
- Abbiamo anche compreso il funzionamento fondamentale dell'algoritmo di Dijkstra con l'aiuto di un esempio.
- Successivamente, abbiamo studiato come scrivere il codice per l'algoritmo di Dijkstra con l'aiuto dello pseudocodice.
- Abbiamo osservato la sua implementazione in linguaggi di programmazione come C, C++, Java e Python con risultati e spiegazioni adeguati.
- Abbiamo anche compreso la complessità temporale e spaziale dell'algoritmo di Dijkstra.
- Infine, abbiamo discusso i vantaggi e gli svantaggi dell'algoritmo di Dijkstra e alcune delle sue applicazioni nella vita reale.