how implement dijkstra s algorithm java
Acest tutorial explică cum să implementați algoritmul Dijkstra în Java pentru a găsi cele mai scurte rute într-un grafic sau un arbore cu ajutorul unor exemple:
În tutorialul nostru anterior despre Grafice în Java, am văzut că graficele sunt folosite pentru a găsi cea mai scurtă cale între noduri, în afară de alte aplicații.
Pentru a găsi cea mai scurtă cale între două noduri ale unui grafic, folosim în cea mai mare parte un algoritm cunoscut sub numele de „ Algoritmul lui Dijkstra ”. Acest algoritm rămâne algoritmul utilizat pe scară largă pentru a găsi cele mai scurte rute într-un grafic sau un arbore.
=> Verificați TOATE Tutorialele Java aici
Ce veți învăța:
Algoritmul lui Dijkstra în Java
Având în vedere un grafic ponderat și un vârf de pornire (sursă) în grafic, algoritmul lui Dijkstra este utilizat pentru a găsi cea mai mică distanță de la nodul sursă la toate celelalte noduri din grafic.
Ca rezultat al rulării algoritmului Dijkstra pe un grafic, obținem cel mai scurt arbore de cale (SPT) cu vârful sursă ca rădăcină.
În algoritmul lui Dijkstra, menținem două seturi sau liste. Una conține vârfurile care fac parte din arborele cu cea mai scurtă cale (SPT), iar cealaltă conține vârfuri care sunt evaluate pentru a fi incluse în SPT. Prin urmare, pentru fiecare iterație, găsim un vârf din lista a doua care are cea mai scurtă cale.
Pseudocodul pentru cel mai scurt algoritm al căii Dijkstra este dat mai jos.
întrebări de interviu pentru biroul de asistență de nivel 1
Pseudo cod
Dat mai jos este pseudocodul pentru acest algoritm.
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 Să luăm acum un eșantion de grafic și să ilustrăm cel mai scurt algoritm al căii Dijkstra .
Inițial, setul SPT (Shortest Path Tree) este setat la infinit.
Să începem cu vârful 0. Deci, pentru început, punem vârful 0 în sptSet.
sptSet = {0, INF, INF, INF, INF, INF}.
Apoi, cu vertex 0 în sptSet, îi vom explora vecinii. Vârfurile 1 și 2 sunt două noduri adiacente ale lui 0 cu distanța 2 și respectiv 1.
În figura de mai sus, am actualizat, de asemenea, fiecare vârf adiacent (1 și 2) cu distanța lor respectivă de la vârful sursă 0. Acum vedem că vârful 2 are o distanță minimă. Deci, apoi adăugăm vârful 2 la sptSet. De asemenea, explorăm vecinii vârfului 2.
Acum căutăm vârful cu distanță minimă și pe cele care nu sunt acolo în spt. Alegem vârful 1 cu distanța 2.
După cum vedem în figura de mai sus, din toate nodurile adiacente ale 2, 0 și 1 sunt deja în sptSet, așa că le ignorăm. Din nodurile adiacente 5 și 3, 5 au cel mai mic cost. Așadar, îl adăugăm la sptSet și explorăm nodurile sale adiacente.
În figura de mai sus, vedem că, cu excepția nodurilor 3 și 4, toate celelalte noduri sunt în sptSet. Din 3 și 4, nodul 3 are cel mai mic cost. Așa că am pus-o în sptSet.
Așa cum se arată mai sus, acum mai avem un singur vârf, adică 4 și distanța sa de nodul rădăcină este 16. În cele din urmă, îl punem în sptSet pentru a obține sptSet final = {0, 2, 1, 5, 3, 4} care ne oferă distanța fiecărui vârf de la nodul sursă 0.
Implementarea algoritmului Dijkstra în Java
Implementarea celui mai scurt algoritm al căii Dijkstra în Java poate fi realizată folosind două moduri. Putem folosi fie cozile de priorități și lista de adiacențe, fie putem folosi matricea și matricile de adiacență.
În această secțiune, vom vedea ambele implementări.
Utilizarea unei cozi prioritare
În această implementare, folosim coada prioritară pentru a stoca vârfurile cu cea mai mică distanță. Graficul este definit utilizând lista de adiacență. Un exemplu de program este prezentat mai jos.
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 Ieșire:
Folosind Adjacency Matrix
În această abordare, folosim matricea de adiacență pentru a reprezenta graficul. Pentru setul de spt folosim matrici.
Următorul program arată această implementare.
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 Ieșire:
întrebări frecvente
Q # 1) Funcționează Dijkstra pentru grafice nedirecționate?
Răspuns: Dacă graficul este direcționat sau nedirecționat, nu contează în cazul algoritmului lui Dijkstra. Acest algoritm este preocupat doar de vârfurile din grafic și de greutăți.
Q # 2) Care este complexitatea în timp a algoritmului lui Dijkstra?
Răspuns: Complexitatea în timp a algoritmului lui Dijkstra este O (V 2). Când este implementat cu coada cu prioritate min, complexitatea timpului acestui algoritm se reduce la O (V + E l o g V).
Q # 3) Este Dijkstra un algoritm lacom?
Răspuns: Da, Dijkstra este un algoritm lacom. Similar algoritmului lui Prim de găsire a arborelui minim de întindere (MST), acești algoritmi pornesc și de la un vârf de rădăcină și aleg întotdeauna cel mai optim vârf cu calea minimă.
Q # 4) Este Dijkstra DFS sau BFS?
Răspuns: Nu este nici una, nici alta. Dar, deoarece algoritmul lui Dijkstra folosește o coadă prioritară pentru implementarea sa, acesta poate fi văzut ca aproape de BFS.
Q # 5) Unde este utilizat algoritmul Dijkstra?
Răspuns: Este utilizat mai ales în protocoale de rutare, deoarece ajută la găsirea celei mai scurte căi de la un nod la altul.
Concluzie
În acest tutorial, am discutat despre algoritmul Dijkstra. Folosim acest algoritm pentru a găsi cea mai scurtă cale de la nodul rădăcină la celelalte noduri din grafic sau un arbore.
De obicei, implementăm algoritmul Dijkstra folosind o coadă prioritară, deoarece trebuie să găsim calea minimă. De asemenea, putem implementa acest algoritm folosind matricea de adiacență. Am discutat ambele abordări în acest tutorial.
Sperăm că veți găsi util acest tutorial.
=> Vizitați aici pentru a vedea seria de antrenament Java pentru toți
Lectură recomandată
- Algoritm de căutare binară în Java - Implementare și exemple
- Sortare cu bule în Java - Algoritmi de sortare Java și exemple de cod
- Sortare prin inserție în Java - Algoritm de sortare și exemple
- Sortare selecție în Java - Algoritm sortare selecție și exemple
- QuickSort în Java - Algoritm, Ilustrație și Implementare
- Tutorial JAVA pentru începători: peste 100 de tutoriale video Java practice
- Tutorial de reflecție Java cu exemple
- Matrice Jagged în Java - Tutorial cu exemple
