• bilgisayarda, grafiklerde (ozellikle c plus plusta) en kisa yolu bulmak*** icin kullanilan bir algoritmadir. oldukca etkili ve hizlidir.
  • adjacency matrix ile ifade edilen ve vertex sayisi genelde 1000'i gecmeyecek graph'lerde calistirilmalidir. complexity'si o(n^3) oldugucu icin cok buyuk graph'lerde running time patlayabilir. dijkstra'nin shortest path algoritmasindan farki bir vertex'ten digerine en kisa yolu bulmaktansa, butun vertexlerden bir vertex'e en kisa yolu bulmaya yaramasidir. yani dijkstra'nin algoritmasini n kere calistirmak ile floyd warshall'i bir kere calistirmak ayni seydir, ama floyd warshall kucuk graph'lerde kullanilmalidir.

    not: burada n vertex sayisina karsilik geliyor.
  • başlık yöntem şeklinde açılmış ama yöntemden ziyade algoritmadır. dijkstra algoritması nın daha bir değişik versiyonudur, burada hedef en kısa yolu bulmanın yanı sıra belirtilen bütün noktalar arasındaki en kısa yolların bulunmasıdır. yani çıkış ve varış noktasının yanı sıra üzerinden geçilen veya tercih edilmeyen bütün noktalar arasındaki uzaklıkları gösterir.

    ayrıca, dijkstra'dan farklı olarak noktalar negatif veya pozitif değer alabilir.
  • en basit hali ile çalışma mantığını, basitçe c# kodunu, örnek leetcode sorularını, avantaj ve dezavantajlarını anlatmaya çalıştığım shortest path algoritması.

    https://youtu.be/sohgbnlgol8

    bu algoritma dinamik programlama prensibine dayanıyor. algoritma, graf'taki 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.

    çalışma prensibi şu şekilde:

    1. ilk adımda, graf'taki her node arasındaki en kısa mesafeleri temsil etmek için bir matris oluşturulur. bu matrisin başlangıç değerleri, graf'taki 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. ikinci 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.

    avantajları?

    1. tüm node çiftleri arasındaki en kısa yolları bulur: floyd-warshall algoritması, graf'taki 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ı kenarlarla* ç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 önemli.

    4. uygulaması basittir: algoritma, matrisler üzerindeki işlemleri kullanır ve bu nedenle basit bir şekilde uygulanabilir. özellikle, graf'taki 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ı, graf'taki 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ı hesaplayabilir.

    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*'larda çalışır: floyd-warshall algoritması, sadece ağırlıklı kenarlar üzerinde çalışabilir. ağırlıksız kenalarda 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, graf'taki node ve kenar sayısı büyük olduğunda performansı düşebilir.

    https://en.wikipedia.org/…/floyd–warshall_algorithm
    https://www.geeksforgeeks.org/…all-algorithm-dp-16/
    https://brilliant.org/…ki/floyd-warshall-algorithm/
    https://algs4.cs.princeton.edu/…dwarshall.java.html
hesabın var mı? giriş yap