how implement dijkstra s algorithm java
Ten samouczek wyjaśnia, jak zaimplementować algorytm Dijkstry w Javie, aby znaleźć najkrótsze trasy na wykresie lub drzewie za pomocą przykładów:
W naszym wcześniejszym samouczku dotyczącym wykresów w Javie widzieliśmy, że wykresy służą do znajdowania najkrótszej ścieżki między węzłami poza innymi aplikacjami.
Aby znaleźć najkrótszą ścieżkę między dwoma węzłami wykresu, najczęściej używamy algorytmu znanego jako „ Algorytm Dijkstry ”. Algorytm ten pozostaje szeroko stosowanym algorytmem do znajdowania najkrótszych tras na wykresie lub w drzewie.
=> Sprawdź WSZYSTKIE samouczki Java tutaj
Czego się nauczysz:
Algorytm Dijkstry w Javie
Biorąc pod uwagę wykres ważony i początkowy (źródłowy) wierzchołek na wykresie, algorytm Dijkstry jest używany do znalezienia najkrótszej odległości od węzła źródłowego do wszystkich pozostałych węzłów na wykresie.
W wyniku działania algorytmu Dijkstry na wykresie otrzymujemy drzewo najkrótszej ścieżki (SPT) z wierzchołkiem źródłowym jako korzeniem.
W algorytmie Dijkstry utrzymujemy dwa zbiory lub listy. Jeden zawiera wierzchołki, które są częścią drzewa o najkrótszej ścieżce (SPT), a drugi zawiera wierzchołki, które są oceniane jako uwzględnione w SPT. Dlatego dla każdej iteracji znajdujemy wierzchołek z drugiej listy, który ma najkrótszą ścieżkę.
Pseudokod algorytmu najkrótszej ścieżki Dijkstry podano poniżej.
najlepsze oprogramowanie do odzyskiwania danych dla systemu Windows
Pseudo kod
Poniżej podano pseudokod tego algorytmu.
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 Weźmy teraz przykładowy wykres i zilustrujmy algorytm najkrótszej ścieżki Dijkstry .
Początkowo SPT (Shortest Path Tree) jest ustawione na nieskończoność.
Zacznijmy od wierzchołka 0. Na początek umieścimy wierzchołek 0 w sptSet.
sptSet = {0, INF, INF, INF, INF, INF}.
Następnie z wierzchołkiem 0 w sptSet zbadamy jego sąsiadów. Wierzchołki 1 i 2 to dwa sąsiednie węzły 0 w odległości odpowiednio 2 i 1.
Na powyższym rysunku zaktualizowaliśmy również każdy sąsiedni wierzchołek (1 i 2) o ich odpowiednią odległość od wierzchołka źródłowego 0. Teraz widzimy, że wierzchołek 2 ma minimalną odległość. Następnie dodajemy wierzchołek 2 do sptSet. Badamy także sąsiadów wierzchołka 2.
Teraz szukamy wierzchołków z minimalną odległością i tych, których nie ma w spt. Wybieramy wierzchołek 1 z odległością 2.
Jak widać na powyższym rysunku, spośród wszystkich sąsiednich węzłów 2, 0 i 1 są już w sptSet, więc je ignorujemy. Spośród sąsiednich węzłów 5 i 3, 5 ma najmniejszy koszt. Więc dodajemy go do sptSet i badamy jego sąsiednie węzły.
Na powyższym rysunku widzimy, że z wyjątkiem węzłów 3 i 4, wszystkie inne węzły znajdują się w sptSet. Spośród 3 i 4 węzeł 3 ma najmniejszy koszt. Więc umieściliśmy go w sptSet.
Jak pokazano powyżej, teraz mamy tylko jeden wierzchołek, tj. 4, a jego odległość od węzła głównego wynosi 16. Na koniec umieszczamy go w sptSet, aby uzyskać ostateczny sptSet = {0, 2, 1, 5, 3, 4}, daje nam odległość każdego wierzchołka od węzła źródłowego 0.
Implementacja algorytmu Dijkstry w Javie
Implementację algorytmu najkrótszej ścieżki Dijkstry w Javie można osiągnąć na dwa sposoby. Możemy albo użyć kolejek priorytetowych i listy sąsiedztwa, albo możemy użyć macierzy sąsiedztwa i tablic.
W tej sekcji zobaczymy obie implementacje.
Korzystanie z kolejki priorytetowej
W tej implementacji używamy kolejki priorytetowej do przechowywania wierzchołków o najkrótszej odległości. Wykres jest definiowany za pomocą listy sąsiedztwa. Przykładowy program przedstawiono poniżej.
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 Wynik:
Korzystanie z macierzy sąsiedztwa
W tym podejściu do przedstawienia wykresu używamy macierzy sąsiedztwa. Do zbioru spt używamy tablic.
Poniższy program przedstawia tę realizację.
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 Wynik:
Często Zadawane Pytania
P # 1) Czy Dijkstra działa dla wykresów nieukierunkowanych?
Odpowiedź: To, czy wykres jest skierowany, czy nie, nie ma znaczenia w przypadku algorytmu Dijkstry. Ten algorytm dotyczy tylko wierzchołków grafu i wag.
Pytanie 2) Jaka jest złożoność czasowa algorytmu Dijkstry?
Odpowiedź: Złożoność czasowa algorytmu Dijkstry wynosi O (V 2). W przypadku realizacji z kolejką o minimalnym priorytecie złożoność czasowa tego algorytmu sprowadza się do O (V + E l o g V).
Pytanie 3) Czy Dijkstra to zachłanny algorytm?
Odpowiedź: Tak, Dijkstra to chciwy algorytm. Podobnie do algorytmu Prim znajdowania minimalnego drzewa rozpinającego (MST), te algorytmy również zaczynają się od wierzchołka głównego i zawsze wybierają najbardziej optymalny wierzchołek z minimalną ścieżką.
Pytanie 4) Czy Dijkstra DFS czy BFS?
Odpowiedź: Nie jest. Ale ponieważ algorytm Dijkstry wykorzystuje do implementacji kolejkę priorytetową, można go postrzegać jako zbliżony do BFS.
P # 5) Gdzie jest używany algorytm Dijkstry?
Odpowiedź: Jest używany głównie w protokołach routingu, ponieważ pomaga znaleźć najkrótszą ścieżkę z jednego węzła do drugiego.
Wniosek
W tym samouczku omówiliśmy algorytm Dijkstry. Używamy tego algorytmu, aby znaleźć najkrótszą ścieżkę od węzła głównego do innych węzłów na wykresie lub w drzewie.
Zwykle implementujemy algorytm Dijkstry za pomocą kolejki Priority, ponieważ musimy znaleźć minimalną ścieżkę. Możemy również zaimplementować ten algorytm za pomocą macierzy sąsiedztwa. Omówiliśmy oba te podejścia w tym samouczku.
Mamy nadzieję, że ten samouczek okaże się pomocny.
=> Odwiedź tutaj, aby zobaczyć serię szkoleń Java dla wszystkich
rekomendowane lektury
- Algorytm wyszukiwania binarnego w Javie - implementacja i przykłady
- Sortowanie bąbelkowe w języku Java - algorytmy sortowania i przykłady kodu w języku Java
- Sortowanie przez wstawianie w Javie - Algorytm sortowania przez wstawianie i przykłady
- Sortowanie przez wybór w Javie - Algorytm sortowania przez wybór i przykłady
- QuickSort in Java - algorytm, ilustracja i implementacja
- Samouczek JAVA dla początkujących: ponad 100 praktycznych samouczków wideo Java
- Samouczek dotyczący refleksji w języku Java z przykładami
- Postrzępiona tablica w Javie - samouczek z przykładami
