how implement dijkstra s algorithm java
Questo tutorial spiega come implementare l'algoritmo di Dijkstra in Java per trovare i percorsi più brevi in un grafico o in un albero con l'aiuto di esempi:
Nel nostro precedente tutorial sui grafici in Java, abbiamo visto che i grafici vengono utilizzati per trovare il percorso più breve tra i nodi oltre ad altre applicazioni.
Per trovare il percorso più breve tra due nodi di un grafo, utilizziamo principalmente un algoritmo noto come ' Algoritmo di Dijkstra '. Questo algoritmo rimane l'algoritmo ampiamente utilizzato per trovare i percorsi più brevi in un grafico o in un albero.
=> Controlla TUTTI i tutorial Java qui
Cosa imparerai:
Algoritmo di Dijkstra in Java
Dato un grafo ponderato e un vertice iniziale (sorgente) nel grafico, l'algoritmo di Dijkstra viene utilizzato per trovare la distanza più breve dal nodo sorgente a tutti gli altri nodi nel grafico.
Come risultato dell'algoritmo di Dijkstra in esecuzione su un grafico, otteniamo l'albero del percorso più breve (SPT) con il vertice sorgente come radice.
Nell'algoritmo di Dijkstra, manteniamo due insiemi o elenchi. Uno contiene i vertici che fanno parte dell'albero dei percorsi più brevi (SPT) e l'altro contiene i vertici che vengono valutati per essere inclusi in SPT. Quindi per ogni iterazione, troviamo un vertice dalla seconda lista che ha il percorso più breve.
Di seguito viene fornito lo pseudocodice per l'algoritmo del percorso più breve di Dijkstra.
miglior software di recupero per Windows 10
Pseudocodice
Di seguito è riportato lo pseudocodice per questo algoritmo.
procedure dijkstra(G, S) G-> graph; S->starting vertex begin for each vertex V in G //initialization; initial path set to infinite path(V) <- infinite previous(V) <- NULL If V != S, add V to Priority Queue PQueue path (S) <- 0 while PQueue IS NOT EMPTY U <- Extract MIN from PQueue for each unvisited adjacent_node V of U tempDistance <- path (U) + edge_weight(U, V) if tempDistance < path (V) path (V) <- tempDistance previous(V) <- U return path(), previous() end Prendiamo ora un grafico di esempio e illustriamo l'algoritmo del percorso più breve di Dijkstra .
Inizialmente, il set SPT (Shortest Path Tree) è impostato su infinito.
Cominciamo con il vertice 0. Quindi, per cominciare, mettiamo il vertice 0 in sptSet.
sptSet = {0, INF, INF, INF, INF, INF}.
Successivamente con il vertice 0 in sptSet, esploreremo i suoi vicini. I vertici 1 e 2 sono due nodi adiacenti di 0 con distanza 2 e 1 rispettivamente.
Nella figura sopra, abbiamo anche aggiornato ogni vertice adiacente (1 e 2) con la rispettiva distanza dal vertice sorgente 0. Ora vediamo che il vertice 2 ha una distanza minima. Quindi aggiungiamo il vertice 2 a sptSet. Inoltre, esploriamo i vicini del vertice 2.
Adesso cerchiamo i vertici con distanza minima e quelli che non ci sono in spt. Scegliamo il vertice 1 con la distanza 2.
Come vediamo nella figura sopra, di tutti i nodi adiacenti di 2, 0 e 1 sono già in sptSet, quindi li ignoriamo. Dei nodi adiacenti 5 e 3, 5 hanno il minor costo. Quindi lo aggiungiamo a sptSet ed esploriamo i suoi nodi adiacenti.
Nella figura sopra, vediamo che ad eccezione dei nodi 3 e 4, tutti gli altri nodi sono in sptSet. Di 3 e 4, il nodo 3 ha il costo minore. Quindi lo mettiamo in sptSet.
Come mostrato sopra, ora abbiamo solo un vertice rimasto, cioè 4 e la sua distanza dal nodo radice è 16. Infine, lo inseriamo in sptSet per ottenere lo sptSet finale = {0, 2, 1, 5, 3, 4} che ci dà la distanza di ogni vertice dal nodo sorgente 0.
Implementazione dell'algoritmo di Dijkstra in Java
L'implementazione dell'algoritmo del percorso più breve di Dijkstra in Java può essere ottenuta in due modi. Possiamo usare le code di priorità e l'elenco di adiacenza oppure possiamo usare matrici e array di adiacenza.
In questa sezione vedremo entrambe le implementazioni.
Utilizzo di una coda prioritaria
In questa implementazione, usiamo la coda di priorità per memorizzare i vertici con la distanza più breve. Il grafico è definito utilizzando l'elenco di adiacenza. Di seguito viene mostrato un programma di esempio.
import java.util.*; class Graph_pq { int dist(); Set visited; PriorityQueue pqueue; int V; // Number of vertices List adj_list; //class constructor public Graph_pq(int V) { this.V = V; dist = new int(V); visited = new HashSet(); pqueue = new PriorityQueue(V, new Node()); } // Dijkstra's Algorithm implementation public void algo_dijkstra(List adj_list, int src_vertex) { this.adj_list = adj_list; for (int i = 0; i adj_list = new ArrayList(); // Initialize adjacency list for every node in the graph for (int i = 0; i Produzione:
Utilizzo della matrice di adiacenza
In questo approccio, utilizziamo la matrice di adiacenza per rappresentare il grafico. Per spt set usiamo array.
Il seguente programma mostra questa implementazione.
import java.util.*; import java.lang.*; import java.io.*; class Graph_Shortest_Path { static final int num_Vertices = 6; //max number of vertices in graph // find a vertex with minimum distance int minDistance(int path_array(), Boolean sptSet()) { // Initialize min value int min = Integer.MAX_VALUE, min_index = -1; for (int v = 0; v Produzione:
Domande frequenti
D # 1) Dijkstra funziona per i grafici non orientati?
Risposta: Se il grafico è diretto o non orientato non ha importanza nel caso dell'algoritmo di Dijkstra. Questo algoritmo si occupa solo dei vertici nel grafo e dei pesi.
D # 2) Qual è la complessità temporale dell'algoritmo di Dijkstra?
Risposta: La complessità temporale dell'algoritmo di Dijkstra è O (V 2). Quando implementato con la coda con priorità minima, la complessità temporale di questo algoritmo si riduce a O (V + E l o g V).
D # 3) Dijkstra è un algoritmo avido?
Risposta: Sì, Dijkstra è un algoritmo avido. Analogamente all'algoritmo di Prim per la ricerca del minimo spanning tree (MST), anche questi algoritmi partono da un vertice radice e scelgono sempre il vertice più ottimale con il percorso minimo.
Q # 4) Dijkstra è DFS o BFS?
Risposta: Non è né l'uno né l'altro. Ma poiché l'algoritmo di Dijkstra utilizza una coda di priorità per la sua implementazione, può essere visto il più vicino a BFS.
D # 5) Dove viene utilizzato l'algoritmo Dijkstra?
Risposta: Viene utilizzato principalmente nei protocolli di routing in quanto aiuta a trovare il percorso più breve da un nodo a un altro nodo.
Conclusione
In questo tutorial, abbiamo discusso l'algoritmo di Dijkstra. Usiamo questo algoritmo per trovare il percorso più breve dal nodo radice agli altri nodi nel grafo o in un albero.
Di solito implementiamo l'algoritmo di Dijkstra utilizzando una coda prioritaria poiché dobbiamo trovare il percorso minimo. Possiamo anche implementare questo algoritmo usando la matrice di adiacenza. Abbiamo discusso entrambi questi approcci in questo tutorial.
Ci auguriamo che troverai utile questo tutorial.
=> Visita qui per vedere la serie di formazione Java per tutti
Lettura consigliata
- Algoritmo di ricerca binaria in Java - implementazione ed esempi
- Bubble Sort in Java - Algoritmi di ordinamento Java ed esempi di codice
- Ordinamento di inserimento in Java - Algoritmo ed esempi di ordinamento di inserimento
- Ordina selezione in Java - Algoritmo di ordinamento selezione ed esempi
- QuickSort in Java - Algoritmo, illustrazione e implementazione
- Tutorial JAVA per principianti: oltre 100 tutorial video Java pratici
- Tutorial Java Reflection con esempi
- Jagged Array in Java - Tutorial con esempi
