Sözlük · approach
Dijkstra Algorithm
Edsger Dijkstra'nın (1959) non-negatif kenar ağırlıklı graflarda tek-kaynak shortest path için polinom-zaman algoritması; greedy yaklaşımla öncelik kuyruğundan en küçük geçici-mesafeli düğümü çıkarır, komşuları günceller; binary heap ile O((V+E)logV).
Dijkstra AlgoritmasıDijkstraDijkstra'nın AlgoritmasıDijkstra Shortest Path
Dijkstra Algorithm, Edsger Dijkstra'nın 1959 yılında *Numerische Mathematik* dergisinde yayımladığı iki sayfalık makalede tanımladığı polinom-zaman algoritmasıdır; non-negatif kenar ağırlıklı bir grafta tek-kaynak shortest path probleminin (bir kaynak düğümden tüm diğer düğümlere en kısa yol) çözümüdür. Greedy yaklaşım: her adımda öncelik kuyruğundan ziyaret-edilmemiş düğümler arasında en küçük geçici-mesafeli düğümü çıkar, komşularının mesafelerini günceller (relaxation). Kompleksite: binary heap implementasyonu O((V+E)logV), Fibonacci heap O(E + V logV). Tek-kaynak-tek-hedef varyantında hedefe ulaşılınca durulur; tek-kaynak-tüm-hedefler için tüm graf işlenir. Foundational; sayısız pratik sistemin alt-rutini (ağ yönlendirme protokolleri OSPF, navigasyon, sosyal-ağ uzaklığı, paket-anahtarlama). A* (Hart-Nilsson-Raphael 1968) Dijkstra'nın heuristic-guided varyantı, ülke ölçeği yol ağları için contraction hierarchies (Geisberger 2008) Dijkstra'nın modern preprocessing-tabanlı uzantısı. Negatif kenar olduğunda Dijkstra optimum vermez — Bellman-Ford gerekir. Cormen-Leiserson-Rivest-Stein (2009) *Introduction to Algorithms* öğretim referansıdır.
Örnek
Bir saha-servis operasyonunda teknisyenin müşteri 1'den müşteri 12'ye en kısa süre yolu, şehir-içi yol ağı grafında binary heap-tabanlı Dijkstra ile milisaniyeler içinde hesaplanır; çağrı merkezi gelen acil çağrıya en yakın teknisyeni tek-kaynak-tüm-hedefler Dijkstra varyantı ile tespit eder.