Dijkstra Algoritması
Dijkstra Algorithm for Shortest Path · Ayrıca şöyle bilinir: Dijkstra's algorithm, shortest path algorithm
Edsger W. Dijkstra tarafından 1956'da tanıtılan Dijkstra Algoritması, bilgisayar bilimlerinde tek kaynaklı en kısa yol problemini çözmek için en temel algoritmalardan biridir. Negatif olmayan kenar ağırlıklarına sahip ağırlıklı bir grafikte, bir başlangıç düğümünden diğer tüm düğümlere olan en kısa yolu bulur.
Tam yöntemi oku
Bu bölümü okumak için ücretsiz hesapla giriş yapın.
Yöntem haritası
İlişkili yöntemlerin komşuluğu — keşfetmek için bir düğüm seçin.
Ne zaman kullanılır
Negatif olmayan kenar ağırlıklarına sahip grafiklerde en kısa yolları bulurken Dijkstra algoritmasını uygulayın. Navigasyon sistemleri, ağ yönlendirme ve optimal yollar gerektiren herhangi bir grafik problemi için idealdir. Tüm düğümlere tek kaynaklı en kısa yollar için kullanın. Negatif ağırlıklı grafikler için bunun yerine Bellman-Ford'u kullanın. Çift yönlü arama veya sezgisel rehberlik için A* algoritmasını düşünün.
Güçlü yönler & sınırlılıklar
- Anlaması ve uygulaması kolay, net doğruluk garantileriyle
- Uygun veri yapılarıyla verimli: ikili yığın ile O((V+E)logV), dizi ile O(V²)
- Negatif olmayan ağırlık grafikleri için optimaldir; hesaplanan yolların optimalliğini kanıtlar
- Hem yönlü hem de yönsüz grafiklerde çalışır
- Sayısız uzantı ve ilgili algoritma için temel oluşturur
- Negatif kenar ağırlıklarına sahip grafikleri işleyemez
- Yalnızca bir hedefe değil, tüm düğümlere olan en kısa yolları hesaplar (erken sonlandırılabilse de)
- Sezgisel bilgi mevcut olduğunda A*'dan daha az verimli
- Tüm düğümlerin keşfedilmesini gerektirir; çok seyrek bağlantı için verimsiz
SSS
Dijkstra algoritması neden negatif ağırlıklarda başarısız olur?
Algoritma, bir düğüm kesinleştiğinde, ziyaret edilmemiş düğümler aracılığıyla daha kısa bir yol bulunamayacağını varsayar. Negatif ağırlıklarla, daha uzun bir yol, negatif bir kenar kullanıldığında daha sonra iyileşebilir ve bu varsayımı ihlal eder.
Öncelik kuyruğu için hangi veri yapısı kullanılmalıdır?
İkili yığınlar, hem ekleme hem de çıkarma için O(logV) işlemleri sağlar ve toplam O((V+E)logV) karmaşıklığına yol açar. Fibonacci yığınları O(E+VlogV) elde eder ancak büyük sabit faktörlere sahiptir. Diziler küçük grafikler için iyi çalışır.
Dijkstra algoritması tek bir belirli hedefe giden yolu nasıl bulabilir?
Hedef düğüm seçildiği anda (mesafesi kesinleştiğinde) algoritmayı sonlandırarak gereksiz hesaplamayı önleyin. Alternatif olarak, yürütme sırasında üst işaretçileri koruyarak yolu yeniden oluşturun.
Dijkstra algoritması yönsüz grafiklerde kullanılabilir mi?
Evet, yönsüz grafikler, her yönsüz kenar için her iki yönde kenarlara sahip yönlü grafikler olarak temsil edilebilir ve her biri aynı ağırlığa sahiptir. Algoritma, çift yönlü temsilde aynı şekilde çalışır.
Kaynaklar
- Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271. DOI: 10.1007/BF01386390 ↗
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press. ISBN: 978-0-262-03384-8
Bu sayfayı kaynak gösterin
ScholarGate. (2026, June 3). Dijkstra Algorithm for Shortest Path. ScholarGate. https://scholargate.app/tr/operations-research/dijkstra-algorithm
Hangi yöntem?
Bu yöntemi en yakın akrabalarının yanına koyup yan yana okuyun — kütüphane kitapları masaya serer; seçim sizindir.
- A* Arama AlgoritmasıYöneylem araştırması↔ karşılaştır
- Bellman-Ford AlgoritmasıYöneylem araştırması↔ karşılaştır
- Ford-Fulkerson AlgoritmasıYöneylem araştırması↔ karşılaştır