Menu

Jak zaimplementować algorytm Dijkstry w Javie

  • Główny
  • Inny
  • Jak zaimplementować algorytm Dijkstry w Javie

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

Algorytm Dijkstry w Javie

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 .

algorytm najkrótszej ścieżki

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.

sąsiednie węzły

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.

sąsiedni wierzchołek

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.

wierzchołek z minimalną odległością

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.

sąsiednie węzły 2, 0

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.

węzły 3 i 4

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:

kolejka priorytetowa - wyjście

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:

Macierz sąsiedztwa - wyjście

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

^