how implement dijkstra s algorithm java
Bu Öğretici, Örnekler yardımıyla bir Grafik veya Ağaçtaki En Kısa Rotaları bulmak için Dijkstra’nın algoritmasının Java’da nasıl uygulanacağını açıklar:
Java'da Grafikler hakkındaki önceki eğitimimizde, diğer uygulamalardan ayrı olarak düğümler arasındaki en kısa yolu bulmak için grafiklerin kullanıldığını gördük.
Bir grafiğin iki düğümü arasındaki en kısa yolu bulmak için çoğunlukla ' Dijkstra Algoritması ”. Bu algoritma, bir grafik veya ağaçtaki en kısa rotaları bulmak için yaygın olarak kullanılan algoritma olarak kalır.
=> TÜM Java Öğreticilerini Buradan Kontrol Edin
Ne öğreneceksin:
Dijkstra’nın Java Algoritması
Ağırlıklı bir grafik ve grafikte bir başlangıç (kaynak) tepe noktası verildiğinde, Dijkstra'nın algoritması, kaynak düğümden grafikteki diğer tüm düğümlere en kısa mesafeyi bulmak için kullanılır.
Dijkstra algoritmasının bir grafik üzerinde çalıştırılmasının bir sonucu olarak, kök olarak kaynak köşe ile en kısa yol ağacını (SPT) elde ederiz.
Dijkstra’nın algoritmasında iki küme veya liste tutuyoruz. Biri en kısa yol ağacının (SPT) bir parçası olan köşeleri içerir ve diğeri SPT'ye dahil edilmek üzere değerlendirilen köşeleri içerir. Bu nedenle, her yineleme için, en kısa yola sahip ikinci listeden bir tepe noktası buluyoruz.
Dijkstra’nın en kısa yol algoritması için sözde kod aşağıda verilmiştir.
Windows 7 için en iyi ücretsiz video dönüştürücü
Sözde kod
Aşağıda bu algoritma için sözde kod verilmiştir.
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 Şimdi örnek bir grafik alalım ve Dijkstra’nın en kısa yol algoritmasını gösterelim .
Başlangıçta, SPT (En Kısa Yol Ağacı) seti sonsuza ayarlanmıştır.
Tepe 0 ile başlayalım. Yani başlangıç noktası 0'ı sptSet'e koyarız.
sptSet = {0, INF, INF, INF, INF, INF}.
Daha sonra sptSet'te köşe 0 ile komşularını keşfedeceğiz. Tepe noktaları 1 ve 2, sırasıyla mesafe 2 ve 1 ile 0 olan iki bitişik düğümdür.
Yukarıdaki şekilde, her bir bitişik tepe noktasını (1 ve 2) kaynak tepe 0'a olan ilgili uzaklıkları ile güncelledik. Şimdi tepe 2'nin minimum uzaklığa sahip olduğunu görüyoruz. Bundan sonra sptSet'e 2. köşe ekliyoruz. Ayrıca, tepe 2'nin komşularını da keşfediyoruz.
Şimdi minimum mesafeli tepe noktasını ve spt'de bulunmayanları arıyoruz. Mesafe 2 ile tepe 1'i seçiyoruz.
Yukarıdaki şekilde gördüğümüz gibi, 2, 0 ve 1'in tüm bitişik düğümlerinden zaten sptSet içindedir, bu yüzden onları görmezden geliyoruz. Bitişik düğümlerden 5 ve 3, 5 en düşük maliyete sahiptir. Bu yüzden onu sptSet'e ekliyoruz ve bitişiğindeki düğümleri keşfediyoruz.
Yukarıdaki şekilde 3 ve 4 nolu düğümler dışında diğer tüm düğümlerin sptSet içinde olduğunu görüyoruz. 3 ve 4 arasında, düğüm 3 en düşük maliyete sahiptir. Bu yüzden sptSet'e koyduk.
Yukarıda gösterildiği gibi, şimdi sadece bir tepe noktamız kaldı, yani 4 ve kök düğümden uzaklığı 16'dır. Son olarak, son sptSet = {0, 2, 1, 5, 3, 4} olan bize her bir tepe noktasının kaynak düğüm 0'a olan uzaklığını verir.
Dijkstra Algoritmasının Java'da Uygulanması
Dijkstra’nın Java’daki en kısa yol algoritmasının uygulanması iki yolla sağlanabilir. Ya öncelik sıralarını ve bitişiklik listesini kullanabiliriz ya da bitişik matris ve dizileri kullanabiliriz.
Bu bölümde her iki uygulamayı da göreceğiz.
Öncelik Kuyruğu Kullanma
Bu uygulamada, en kısa mesafeli köşeleri depolamak için öncelik kuyruğunu kullanıyoruz. Grafik, bitişiklik listesi kullanılarak tanımlanır. Aşağıda örnek bir program gösterilmektedir.
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 Çıktı:
Bitişiklik Matrisini Kullanma
Bu yaklaşımda, grafiği temsil etmek için bitişik matris kullanıyoruz. Spt set için dizileri kullanırız.
Aşağıdaki program bu uygulamayı göstermektedir.
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 Çıktı:
Sıkça Sorulan Sorular
S # 1) Dijkstra, yönlendirilmemiş grafikler için çalışıyor mu?
Cevap: Dijkstra algoritması söz konusu olduğunda grafiğin yönlendirilmiş veya yönlendirilmemiş olması önemli değildir. Bu algoritma yalnızca grafikteki köşeler ve ağırlıklarla ilgilenir.
S # 2) Dijkstra algoritmasının zaman karmaşıklığı nedir?
Cevap: Dijkstra Algoritmasının Zaman Karmaşıklığı O (V 2) 'dir. Minimum öncelik sırası ile uygulandığında, bu algoritmanın zaman karmaşıklığı O (V + E l o g V) olur.
S # 3) Dijkstra açgözlü bir algoritma mı?
Cevap: Evet, Dijkstra açgözlü bir algoritmadır. Prim'in minimum yayılma ağacını (MST) bulma algoritmasına benzer şekilde, bu algoritmalar da bir kök tepe noktasından başlar ve her zaman minimum yolla en uygun tepe noktasını seçer.
S # 4) Dijkstra DFS mi yoksa BFS mi?
Cevap: İkisi de değil. Ancak Dijkstra’nın algoritması, uygulanması için bir öncelik kuyruğu kullandığından, BFS'ye yakın olarak görülebilir.
S # 5) Dijkstra algoritması nerede kullanılır?
Cevap: Bir düğümden diğerine en kısa yolu bulmaya yardımcı olduğu için çoğunlukla yönlendirme protokollerinde kullanılır.
Sonuç
Bu eğiticide Dijkstra’nın algoritmasını tartıştık. Bu algoritmayı, kök düğümden grafikteki veya bir ağaçtaki diğer düğümlere giden en kısa yolu bulmak için kullanırız.
Minimum yolu bulmamız gerektiğinden, genellikle Dijkstra’nın algoritmasını bir Öncelik kuyruğu kullanarak uygularız. Bu algoritmayı bitişiklik matrisini kullanarak da uygulayabiliriz. Bu eğitimde bu iki yaklaşımı da tartıştık.
Bu eğitimi faydalı bulacağınızı umuyoruz.
=> Java Eğitim Serisini Herkes İçin Görmek İçin Burayı Ziyaret Edin
Önerilen Kaynaklar
- Java'da İkili Arama Algoritması - Uygulama ve Örnekler
- Java'da Kabarcık Sıralama - Java Sıralama Algoritmaları ve Kod Örnekleri
- Java'da Ekleme Sıralama - Ekleme Sıralama Algoritması ve Örnekler
- Java'da Seçim Sırala - Algoritmayı ve Örnekleri Sıralama Seçimi
- Java'da QuickSort - Algoritma, İllüstrasyon ve Uygulama
- Yeni Başlayanlar İçin JAVA Eğitimi: 100+ Uygulamalı Java Video Eğitimi
- Örneklerle Java Yansıtma Eğitimi
- Java'da Jagged Array - Örneklerle Eğitim
