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.
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:
najlepsze oprogramowanie do odzyskiwania danych dla systemu Windows
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
