Floyd-Warshall algoritması | En kısa yolu bulma | Dinamik programlama

Floyd-Warshall algoritması, çoklu noktalar arasındaki en kısa yol problemini çözmek için kullanılan bir graf algoritmasıdır. Algoritma, bir ağırlıklı graflarda kullanılır ve graf üzerindeki tüm node çiftleri arasındaki en kısa yolları bulmak için kullanılır.

00:00 Giriş
00:34 Algoritma açıklaması
09:45 C# kodu
12:56 Avantajları
14:47 Dezavantajları
17:01 Leetcode soruları

Floyd-Warshall algoritması, dinamik programlama prensibine dayanır. Algoritma, grafdeki tüm node'lar arasındaki en kısa yolları hesaplamak için iteratif bir yöntem kullanır. Bu nedenle bu algoritma, tüm node'ları ve ağırlıklı kenarları içeren bir matris kullanır.

Algoritma, ağırlıklı bir graf'ın matris temsilini kullanarak çalışır.

Çalışma prensibi şu şekildedir:

1. İlk adımda, grafdeki her node arasındaki en kısa mesafeleri temsil etmek için bir matris oluşturulur. Bu matrisin başlangıç değerleri, grafdeki ağırlıklı kenarlarla belirlenen mesafelerdir.

2. Ardından, matrisin her bir hücresi üzerinde döngü yapılır ve bu hücreleri güncellemek için diğer node'lar üzerinde bir döngü daha yapılır. Bu adımda, her hücreye ulaşmak için diğer node'ları kullanarak en kısa mesafeler hesaplanır.

3. İkinci adımdaki iç içe döngülerin her bir turunda, daha kısa bir yol bulunursa bu değerle matrisin hücreleri güncellenir.

4. Son olarak, tüm node'lar üzerindeki bu iç içe döngülerin her turunda matris güncellenir ve sonuç olarak matristeki değerler, tüm node'lar arasındaki en kısa mesafeleri içerir.

Bu şekilde, Floyd-Warshall algoritması, grafdeki tüm node'lar arasındaki en kısa mesafeleri bulur. Algoritma, negatif döngüler içermeyen ağırlıklı graf'larda çalışır ve her bir node için tüm diğer node'lara olan en kısa mesafeleri hesaplar.

Avantajları?

1. Tüm çiftler arasındaki en kısa yolları bulur: Floyd-Warshall algoritması, grafdeki tüm node'lar arasındaki en kısa mesafeleri bulur. Bu, her iki node arasındaki en kısa yolu bilmek istediğiniz durumlarda oldukça kullanışlıdır. Örneğin, bir şehirler ağındaki her şehir arasındaki en kısa yol mesafelerini bulmak için kullanılabilir.

2. Dinamik programlama prensibi kullanır: Algoritma, dinamik programlama prensibine dayanır. Bu, bir alt problemin çözümünü kullanarak daha büyük bir problemin çözümünü elde etmeyi sağlar. Floyd-Warshall algoritması, matris tabanlı bir yaklaşım kullanarak bu alt problemleri çözer ve sonunda tüm en kısa yolları bulur.

3. Negatif ağırlıklara izin verir: Floyd-Warshall algoritması, negatif ağırlıklara sahip ağırlıklı çizgelerle çalışabilir. Bu, bazı diğer en kısa yol algoritmalarının başa çıkamadığı bir avantajdır. Ancak, negatif döngülerin varlığı durumunda algoritmanın doğru sonuçlar üretmeyebileceğini unutmamak önemlidir.

4. Uygulaması basittir: Algoritma, matrisler üzerindeki işlemleri kullanır ve bu nedenle basit bir şekilde uygulanabilir. Özellikle, grafdeki tüm node'lar arasındaki en kısa yolları bulmak için kullanılması durumunda oldukça etkilidir. Matris temelli yaklaşımı nedeniyle, algoritma genellikle programlama dillerinde kolayca uygulanabilir.

5. Hafızayı etkin kullanır: Floyd-Warshall algoritması, dinamik programlama prensibi kullanarak her adımda matrisin hücrelerini günceller. Bu, algoritmanın belleği etkin bir şekilde kullanmasını sağlar ve hafızada daha az yer kaplar.

Dezavantajları?

1. Yüksek zaman karmaşıklığı: Floyd-Warshall algoritması, grafdeki tüm node'lar arasındaki en kısa mesafeleri bulmak için tüm node'lar üzerinde üçlü iç içe döngüler kullanır. Bu nedenle, algoritmanın zaman karmaşıklığı O(n^3) olarak ifade edilir. Bu, graf büyüklüğü arttıkça algoritmanın performansının düşmesine neden olabilir. Büyük graf yapıları için ölçeklenebilirlik açısından dezavantajlı olabilir.

2. Negatif döngülerin varlığında hatalı sonuçlar verebilir: Floyd-Warshall algoritması, negatif döngüler içeren graf yapıları için doğru sonuçlar üretemez. Negatif döngüler, bir node döngü içinde tekrar tekrar gezerek negatif bir ağırlık toplamına yol açar. Algoritma, negatif döngülerin olduğu durumlarda doğru sonuçlar üretemeyebilir ve yanlış en kısa yolları raporlayabilir.

3. Bellek gereksinimi: Floyd-Warshall algoritması, graf'taki tüm node'ler arasındaki en kısa mesafeleri temsil etmek için bir matris kullanır. Bu matrisin boyutu, grafdeki node sayısına bağlı olarak artar. Büyük graf yapıları için bu matris büyük olabilir ve algoritmanın bellek gereksinimini artırabilir.

4. Yalnızca ağırlıklı kenar yani weighted edge'lerde çalışır: Floyd-Warshall algoritması, sadece ağırlıklı kenarlar üzerinde çalışabilir. Ağırlıksız kenalarda veya ağırlıksız bağlantılarda kullanılamaz. Dolayısıyla, yalnızca ağırlıklı kenarların en kısa yollarını bulmak için uygulanabilir.

5. Diğer algoritmalardan daha yavaş olabilir: Floyd-Warshall algoritması, en kısa yolu bulmak için tüm node'lar üzerinde üçlü iç içe döngüler kullanır. Bu, bazı diğer en kısa yol algoritmalarına göre daha yavaş çalışmasına neden olabilir. Özellikle, grafdeki node ve kenar sayısı büyük olduğunda performansı düşebilir.