how implement dijkstra s algorithm java
V tomto výučbe sa dozviete, ako implementovať Dijkstraov algoritmus v Jave na nájdenie najkratších ciest v grafe alebo strome pomocou príkladov:
V našom staršom výučbe Grafy v Jave sme videli, že grafy sa používajú na nájdenie najkratšej cesty medzi uzlami okrem iných aplikácií.
Aby sme našli najkratšiu cestu medzi dvoma uzlami grafu, väčšinou používame algoritmus známy ako „ Dijkstraov algoritmus “. Tento algoritmus zostáva často používaným algoritmom na vyhľadanie najkratších trás v grafe alebo strome.
=> Skontrolujte VŠETKY návody Java tu
Čo sa dozviete:
Dijkstraov algoritmus v Jave
Ak vezmeme vážený graf a počiatočný (zdrojový) vrchol v grafe, použije sa Dijkstrov algoritmus na nájdenie najkratšej vzdialenosti od zdrojového uzla ku všetkým ostatným uzlom v grafe.
Výsledkom spustenia Dijkstraovho algoritmu v grafe je získanie stromu najkratšej cesty (SPT) so zdrojovým vrcholom ako root.
V Dijkstrovom algoritme udržiavame dve množiny alebo zoznamy. Jeden obsahuje vrcholy, ktoré sú súčasťou stromu s najkratšou cestou (SPT), a druhý obsahuje vrcholy, ktoré sa vyhodnocujú na zahrnutie do SPT. Preto pre každú iteráciu nájdeme vrchol z druhého zoznamu, ktorý má najkratšiu cestu.
Pseudokód pre algoritmus najkratšej cesty Dijkstra je uvedený nižšie.
čo je súbor 7z?
Pseudokód
Ďalej je uvedený pseudokód pre tento algoritmus.
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
Pozrime sa teraz na ukážkový graf a ilustrujme Dijkstrovu najkratšiu cestu .
Spočiatku je sada SPT (strom s najkratšou cestou) nastavená na nekonečno.
Začnime vrcholom 0. Takže na začiatok vložíme vrchol 0 do sptSet.
sptSet = {0, INF, INF, INF, INF, INF}.
Ďalej s vrcholom 0 v sptSet preskúmame jeho susedov. Vrcholy 1 a 2 sú dva susedné uzly 0 so vzdialenosťou 2, respektíve 1.
Na vyššie uvedenom obrázku sme tiež aktualizovali každý susedný vrchol (1 a 2) o ich príslušnú vzdialenosť od zdrojového vrcholu 0. Teraz vidíme, že vrchol 2 má minimálnu vzdialenosť. Ďalej pridáme vrchol 2 do súboru sptSet. Tiež skúmame susedov vrcholu 2.
Teraz hľadáme vrchol s minimálnou vzdialenosťou a tie, ktoré tam nie sú, v spt. Vyberieme vrchol 1 so vzdialenosťou 2.
Ako vidíme na obrázku vyššie, zo všetkých susedných uzlov 2, 0 a 1 sa už nachádza v sptSet, takže ich ignorujeme. Z priľahlých uzlov 5 a 3 majú 5 najmenšie náklady. Takže ho pridáme do súboru sptSet a preskúmame jeho susedné uzly.
Na vyššie uvedenom obrázku vidíme, že okrem uzlov 3 a 4 sú všetky ostatné uzly v sptSet. Z 3 a 4 má uzol 3 najmenšie náklady. Takže sme to vložili do sptSet.
Ako je uvedené vyššie, teraz nám zostáva iba jeden vrchol, tj. 4 a jeho vzdialenosť od koreňového uzla je 16. Nakoniec ho vložíme do súboru sptSet, aby sme dostali konečný sptSet = {0, 2, 1, 5, 3, 4}, ktorý nám dáva vzdialenosť každého vrcholu od zdrojového uzla 0.
Implementácia Dijkstraovho algoritmu v Jave
Implementáciu Dijkstraovho najkratšieho algoritmu cesty v Jave je možné dosiahnuť dvoma spôsobmi. Môžeme použiť prioritné fronty a zoznam susedstiev, alebo môžeme použiť maticu a polia susedstva.
V tejto časti uvidíme obe implementácie.
Používanie prioritného frontu
V tejto implementácii používame prioritnú frontu na ukladanie vrcholov s najkratšou vzdialenosťou. Graf je definovaný pomocou zoznamu susednosti. Ukážkový program je uvedený nižšie.
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 Výkon:

Pomocou matice susedstva
V tomto prístupe používame na znázornenie grafu maticu susednosti. Pre množinu spt používame polia.
Nasledujúci program ukazuje túto implementáciu.
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 Výkon:

často kladené otázky
Otázka 1) Funguje Dijkstra na neorientované grafy?
Odpoveď: To, či je graf nasmerovaný alebo neorientovaný, v prípade Dijkstraovho algoritmu nezáleží. Tento algoritmus sa týka iba vrcholov v grafe a váh.
Otázka 2) Aká je časová zložitosť Dijkstrovho algoritmu?
Odpoveď: Časová zložitosť Dijkstrovho algoritmu je O (V 2). Keď sa implementuje do frontu minimálnej priority, časová zložitosť tohto algoritmu sa zníži na O (V + E l og V).
Otázka 3) Je Dijkstra chamtivý algoritmus?
Odpoveď: Áno, Dijkstra je chamtivý algoritmus. Podobne ako Primov algoritmus hľadania minimálneho rozloženého stromu (MST), aj tieto algoritmy vychádzajú z koreňového vrcholu a vždy zvolia najoptimálnejší vrchol s minimálnou cestou.
Otázka 4) Je Dijkstra DFS alebo BFS?
Odpoveď: Nie je to ani jedno, ani druhé. Ale keďže Dijkstrov algoritmus používa na svoju implementáciu prioritný rad, dá sa na neho pozerať tak blízko ako k BFS.
Otázka č. 5) Kde sa používa algoritmus Dijkstra?
Odpoveď: Používa sa väčšinou pri smerovacích protokoloch, pretože pomáha nájsť najkratšiu cestu z jedného uzla do druhého.
Záver
V tomto tutoriáli sme diskutovali o Dijkstrovom algoritme. Tento algoritmus používame na nájdenie najkratšej cesty od koreňového uzla k ostatným uzlom v grafe alebo strome.
Algoritmus Dijkstra zvyčajne implementujeme pomocou frontu priorít, pretože musíme nájsť minimálnu cestu. Tento algoritmus môžeme implementovať aj pomocou matice susednosti. O obidvoch týchto prístupoch sme hovorili v tomto tutoriále.
Dúfame, že vám tento návod pomôže.
=> Navštívte tu a pozrite si sériu školení Java pre všetkých
Odporúčané čítanie
- Algoritmus binárneho vyhľadávania v prostredí Java - implementácia a príklady
- Bubble Sort In Java - Algoritmy a triedenie kódov Java
- Triedenie vloženia v Jave - Algoritmus a príklady triedenia vloženia
- Výberové triedenie v Jave - Algoritmus a výberové triedenie výberu
- QuickSort In Java - Algoritmus, ilustrácia a implementácia
- Výukový program JAVA pre začiatočníkov: viac ako 100 praktických výučbových programov Java Video
- Výukový program Java Reflection s príkladmi
- Jagged Array In Java - návod s príkladmi