Günümüzde Matematik · Günümüz
En kısa yol nasıl bulunur? Dijkstra algoritması ve graflar
Bir haritada iki nokta arasındaki en kısa yolu bulmak, bir graf üzerinde çözülen bir matematik problemidir. Edsger Dijkstra'nın 1956'da tasarladığı algoritmayı altı düğümlü kendi örneğimizle adım adım izliyor, neden doğru çalıştığını gösteriyoruz.
Yazan: matematikce editörlüğü 6 dk okuma
Yol tarifi aldığınızda uygulama birkaç saniye içinde size bir güzergâh önerir. Aradaki kavşakların, sokakların ve alternatif yolların sayısını düşününce bu şaşırtıcıdır. Bütün olasılıkları tek tek denemek neredeyse imkânsız olduğuna göre, en kısa yol nasıl bulunuyor?
Bu sorunun matematikteki adı en kısa yol problemidir ve graflar üzerinde çözülür. Bu problemin en tanınmış çözümlerinden biri, Hollandalı bilgisayar bilimci Edsger Dijkstra’nın 1956’da tasarladığı algoritmadır. Bu yazıda kendi küçük haritamızı bir grafa çevirecek, algoritmayı bir tablo üzerinde adım adım çalıştıracak ve neden her zaman doğru cevabı verdiğini göreceğiz. Belirli bir uygulamanın hangi yöntemi kullandığını ise bilmediğimiz için iddia etmeyeceğiz.
Haritadan grafa
Bir haritanın ayrıntıları çoğu zaman en kısa yol sorusu için gereksizdir. Önemli olan, hangi noktaların birbirine bağlı olduğu ve bağlantıların ne kadar uzun sürdüğüdür. Kavşakları nokta, yolları çizgi olarak çizdiğimizde bir graf elde ederiz. Noktalara düğüm, çizgilere kenar denir. Her kenara yazılan sayıya da ağırlık denir. Ağırlık kilometre, dakika ya da yakıt olabilir.
Bir yeri noktalar ve çizgilerle soyutlama fikri yeni değildir. Euler, 18. yüzyılda Königsberg köprüleri problemini tam da bu yolla çözmüş ve graf kuramının temelini atmıştı. Bu hikâyeyi Euler ve Königsberg köprüleri yazımızda okuyabilirsiniz.
Bütün yolları denemek neden yetmez?
İlk akla gelen yöntem, olası bütün yolları listeleyip en kısasını seçmektir. Küçük bir grafta bu işe yarar. Ama yol sayısı çok hızlı büyür.
Bir örnekle görelim. Kare bir mahalle ızgarasında sol alt köşeden sağ üst köşeye yalnızca sağa ve yukarı giderek ulaşmak istediğimizi düşünelim. 10 × 10’luk bir ızgarada 20 adımın 10’unu “sağa” olarak seçmemiz gerekir. Bu, 20’nin 10’lu kombinasyonu kadar yol demektir: 184 756. Izgara 20 × 20 olduğunda yol sayısı 137 846 528 820’ye, yani yüz milyarı aşan bir sayıya çıkar. Üstelik gerçek yollarda geri dönmek ve dolanmak da mümkündür. Daha akıllıca bir yönteme ihtiyacımız var.
Dijkstra’nın fikri
Dijkstra, Amsterdam’daki Matematik Merkezi’nde programcı olarak çalışırken yeni ARMAC bilgisayarının yeteneklerini, bilgisayarcı olmayanların da anlayabileceği bir problemle göstermek istedi. Kendi anlatımına göre algoritmayı nişanlısıyla bir kafe terasında otururken yaklaşık yirmi dakikada tasarladı. Algoritma ancak 1959’da kısa bir makaleyle yayımlandı.
Fikir, başlangıç noktasından dışarıya doğru, en yakından en uzağa, halka halka ilerlemektir:
- Başlangıç düğümünün mesafesini 0, diğer bütün düğümlerinkini sonsuz (∞) kabul et.
- Henüz kesinleşmemiş düğümler arasından mesafesi en küçük olanı seç ve mesafesini kesinleştir.
- Bu düğümün komşularına bak. Seçilen düğümün üzerinden bir komşuya gitmek, o komşu için bilinen mesafeden daha kısaysa, komşunun mesafesini güncelle.
- Hedef kesinleşene ya da bütün düğümler bitene kadar 2. adıma dön.
Adım adım örnek
Kendi küçük grafımızda A, B, C, D, E ve F adlı altı düğüm var. Kenarlar ve ağırlıkları (örneğin dakika olarak) şöyle:
- A–B: 4, A–C: 2, C–B: 1
- B–D: 5, C–D: 8, C–E: 10
- D–E: 2, D–F: 6, E–F: 3
A’dan F’ye en kısa yolu arıyoruz. Tabloda her satır, bir düğümün kesinleştiği anı gösteriyor. Hücrelerde o anda bilinen en kısa mesafeler var; kesinleşen değerler kalın yazılmıştır.
| Adım | Kesinleşen | A | B | C | D | E | F |
|---|---|---|---|---|---|---|---|
| 0 | başlangıç | 0 | ∞ | ∞ | ∞ | ∞ | ∞ |
| 1 | A | 0 | 4 | 2 | ∞ | ∞ | ∞ |
| 2 | C | 0 | 3 | 2 | 10 | 12 | ∞ |
| 3 | B | 0 | 3 | 2 | 8 | 12 | ∞ |
| 4 | D | 0 | 3 | 2 | 8 | 10 | 14 |
| 5 | E | 0 | 3 | 2 | 8 | 10 | 13 |
| 6 | F | 0 | 3 | 2 | 8 | 10 | 13 |
Adımları açıklayalım:
- 1. adım: A kesinleşir. Komşuları B’ye 4, C’ye 2 mesafe yazılır.
- 2. adım: En küçük mesafe C’dedir (2). C üzerinden B’ye 2 + 1 = 3 ile gidilir; bu 4’ten kısa olduğu için B güncellenir. D’ye 2 + 8 = 10, E’ye 2 + 10 = 12 yazılır.
- 3. adım: En küçük mesafe B’dedir (3). B üzerinden D’ye 3 + 5 = 8 ile gidilir; 10’dan kısa olduğu için D güncellenir.
- 4. adım: D kesinleşir (8). E’ye 8 + 2 = 10 ile gidilir ve 12 güncellenir. F’ye 8 + 6 = 14 yazılır.
- 5. adım: E kesinleşir (10). F’ye 10 + 3 = 13 ile gidilir ve 14 güncellenir.
- 6. adım: F kesinleşir. En kısa mesafe 13’tür.
Yolu bulmak için her güncellemede “bu düğüme nereden gelindiğini” not etmek yeterlidir. Sondan geriye izlersek F ← E ← D ← B ← C ← A, yani en kısa yol A → C → B → D → E → F olur: 2 + 1 + 5 + 2 + 3 = 13.
İlginç bir ayrıntı: A’dan B’ye doğrudan giden 4 birimlik bir yol vardı. Ama C üzerinden dolanmak 3 birimle daha kısaydı. Algoritma bunu kendiliğinden fark etti.
Neden doğru çalışır?
Algoritmanın kalbi 2. adımdır. Kesinleşmemiş düğümler arasında mesafesi en küçük olanı seçtiğimizde, o düğüme daha kısa bir yol bulunamayacağından nasıl emin olabiliriz?
Daha kısa bir yol olduğunu varsayalım. Bu yol başlangıçtan çıkar ve bir noktada kesinleşmemiş bir düğüme girmek zorundadır. Ama o düğümün mesafesi, seçtiğimiz düğümün mesafesinden küçük değildir; aksi hâlde onu seçerdik. Kenar ağırlıkları negatif olmadığı için, yolun kalan kısmı toplamı yalnızca artırabilir. O hâlde bu yol seçtiğimiz mesafeden kısa olamaz. Varsayımımız çelişkiye düştü.
Bu ispat, ağırlıkların negatif olmamasına dayanır. Negatif ağırlık varsa algoritma yanılabilir. Örneğin A–B: 2, A–C: 3 ve C’den B’ye tek yönlü −2 ağırlıklı bir kenar olsun. Algoritma B’yi 2 mesafeyle hemen kesinleştirir. Oysa A → C → B yolunun toplamı 3 − 2 = 1’dir. Harita üzerindeki mesafe ve süreler negatif olmadığı için bu durum yol bulmada genellikle sorun yaratmaz.
Gerçek haritalar daha büyük
Bir ülkenin yol ağı milyonlarca düğüm içerebilir. Dijkstra algoritması yine doğru çalışır, ama hedeften uzak yönlere de eşit özenle yayıldığı için gereğinden fazla düğüme bakar. Bu yüzden pratikte çeşitli iyileştirmeler kullanılır.
Bunlardan biri, 1968’de Peter Hart, Nils Nilsson ve Bertram Raphael’in tanıttığı A* algoritmasıdır. A*, her düğüm için başlangıçtan oraya olan mesafeye, hedefe kalan mesafenin iyimser bir tahminini de ekler. Örneğin kuş uçuşu mesafe hiçbir zaman gerçek yol mesafesinden uzun olamayacağı için güvenli bir tahmindir. Böylece arama hedefe doğru yönelir. Büyük yol ağları için önceden hesaplanmış bilgileri kullanan başka teknikler de geliştirilmiştir.
Ayrıca gerçek sistemlerde ağırlıklar sabit değildir. Trafik yoğunluğu, yol çalışmaları ya da saat, bir kenarın süresini değiştirebilir.
Neden önemli?
En kısa yol problemi yalnızca haritalarda değil, bilgisayar ağlarında, lojistik planlamada, oyunlardaki karakterlerin hareketinde ve robotların yol bulmasında da karşımıza çıkar. Graf dili, birbirinden çok farklı görünen bu soruları aynı matematikle çözmemizi sağlar.
Bu yazıdaki fikirler lise matematiğiyle de bağlantılıdır. Izgaradaki yolları saymak için kullandığımız kombinasyon, TYT ve AYT’deki permütasyon ve kombinasyon konusunun parçasıdır. Algoritmanın doğruluğunu gösterirken kullandığımız çelişkiyle ispat da mantık konusunun güçlü bir aracıdır. Konu listesine ne öğrettiğimizi anlattığımız sayfadan bakabilirsiniz. Bir problemin algoritmayla çözülmesinin ne demek olduğu sorusunun kökleri ise Turing makinesi yazımızda anlatılıyor.
Kapanış
Dijkstra algoritması, en kısa yolu bulmak için bütün yolları denemek zorunda olmadığımızı gösterir. En yakından en uzağa doğru sabırla ilerlemek ve her adımda bilinen en iyi değeri güncellemek yeterlidir. Bir kafe terasında yirmi dakikada tasarlanan bu fikir, yarım asrı aşkın süredir graf problemleri çözenlerin temel araçlarından biri olmaya devam ediyor.