DERS 18
Hepinize Günaydın. Erken ve aydınlık bir saatte hepinizi burada görmekten mutluyum. Araştırma Görevlilerinin sayısının öğrencilerinkini geçeceği günleri sayıyorum. Bir gün bu olacak. Tanıdık bir hikayeye geri dönüyoruz. Bu Yıldız Savaşları / İkinci Bölüm Empire Strikes Back. Son defa, rakibimiz, “grafik” bir problem ile karşımıza çıkmıştı. Bir kaynağımız vardı, yönlendirilmiş bir grafiğimiz ve kenarların üzerinde ağırlıklar vardı ve hiçbiri de negatif değillerdi. Ve mutluluk hüküm sürüyordu. Ve Dijkstra’nın algoritmasını tasarımlayarak, tek kaynaklı enkısa yollarda, s ‘ den diğer her köşeye enkısa yol ağırlığını en etkin şekilde bularak, İmparatorluğa karşı galip gelmiştik.
Bugün ise, Ölüm Yıldızı arşivinden bize yeni bir şaşırtıcı oyun çıkarıyor: Potensiyel olarak, negatif ağırlıklarımız var. Ve özellikle negatif ağırlık çevrimleri ile bir şekilde uğraşmak zorunda kalacağız. Ve bir negatif ağırlık çevrimimiz olduğunda, ortalıkta tekrar, tekrar ve tekrar dolaşabildiğimizi ve zaman içinde de gittikçe daha gerilere gidebildiğimizi görmüştük. Ve geçmişte canımızın istediği kadar geri gidebiliyoruz. Ve bu nedenle enkısa yol diye birşey olmuyor, çünkü hangi yolu alırsanız ondan daha kısasını elde edebiliyorsunuz. Böylece bugün bu konuyu işlerken, Dijkstra kadar hızlı olmayan ama ondan daha basit olan, Bellman – Ford adlı yeni bir algoritmayı göreceğiz.
Bu yeni algoritma, negatif ağırlıklara izin veriyor ve ümit ettiğiniz kadar çok sayıda olmamakla birlikte, bir anlamda negatif ağırlık çevrimlerine de yer veriyor. Bu nedenle şüphesiz devamı için de yer ayırmamız gerekiyor. Pekala, tahmin edeceğiniz gibi, Bellman-Ford algoritması iki kişi tarafından keşfedilmiş bir algoritma olup, enkısa yol ağırlıklarını hesaplıyor. Ama ağırlıklar hakkında herhangi varsayımda bulunmuyor. Ağırlıklar tamamen rastgele ve enkısa yol ağırlıklarını hesaplıyor. Şu simgelemi unutmayın: Delta (s, v), s’den v’ye enkısa yol ağırlığıdır. s’ye kaynak köşesi deniliyordu. yani (-6)
