Floyd-Warshall Algoritması, çizge teorisinde kullanılan ve tüm düğüm çiftleri arasındaki en kısa yolları bulmak için tasarlanmış bir algoritmadır. Bu algoritma, dinamik programlama yaklaşımını kullanır ve hem pozitif hem de negatif ağırlıklı kenarlara sahip çizgelerde çalışabilir (ancak negatif ağırlıklı döngüler içermemelidir). Algoritma, 1962 yılında Robert Floyd ve Stephen Warshall tarafından bağımsız olarak geliştirilmiştir.

Çalışma Prensibi

Floyd-Warshall Algoritması, bir çizgedeki tüm düğüm çiftleri arasındaki en kısa yolları bulmak için kademeli bir yaklaşım kullanır. Algoritma, her adımda bir ara düğüm ekleyerek en kısa yolları günceller.

1- Başlangıç:

• Çizgenin komşuluk matrisi kullanılır. Bu matris, düğümler arasındaki doğrudan kenar ağırlıklarını içerir.
• Eğer iki düğüm arasında doğrudan bir kenar yoksa, mesafe sonsuz (∞) olarak ayarlanır.
• Her düğümün kendisine olan mesafesi 0 olarak belirlenir.

2- Dinamik Programlama Yaklaşımı:

• Algoritma, her bir düğümü ara düğüm olarak kullanır ve tüm düğüm çiftleri arasındaki mesafeleri günceller.
• Her adımda, bir düğüm k ara düğüm olarak seçilir ve tüm (i,j) düğüm çiftleri için şu formül uygulanır: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Burada:

• dist[i][j]: i ve j düğümleri arasındaki mevcut en kısa mesafe.
• dist[i][k]: i ve k düğümleri arasındaki mesafe.
• dist[k][j]: k ve j düğümleri arasındaki mesafe.

3- Tüm Ara Düğümlerin İşlenmesi:

• Algoritma, tüm düğümleri sırayla ara düğüm olarak kullanır ve her adımda mesafeleri günceller.
• Bu işlem, tüm düğümler ara düğüm olarak kullanılana kadar devam eder.

4- Sonuç:

• Algoritma tamamlandığında, dist[i][j] matrisi, tüm (i,j) düğüm çiftleri arasındaki en kısa mesafeleri içerir.

^{Floyd-Warshall Algoritması örneği}

Floyd-Warshall Algoritması Java Kodu

import java.util.*;

class Solution {
    public void shortest_distance(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == -1) {
                    matrix[i][j] = (int)(1e9);
                }
                if (i == j) matrix[i][j] = 0;
            }
        }

        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    matrix[i][j] = Math.min(matrix[i][j],
                                            matrix[i][k] + matrix[k][j]);
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == (int)(1e9)) {
                    matrix[i][j] = -1;
                }
            }
        }
    }
}

public class tUf {
    public static void main(String[] args) {
        int V = 4;
        int[][] matrix = new int[V][V];

        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                matrix[i][j] = -1;
            }
        }

        matrix[0][1] = 2;
        matrix[1][0] = 1;
        matrix[1][2] = 3;
        matrix[3][0] = 3;
        matrix[3][1] = 5;
        matrix[3][2] = 4;

        Solution obj = new Solution();
        obj.shortest_distance(matrix);

        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println("");
        }
    }
} 

Zaman Karmaşıklığı

Floyd-Warshall Algoritması'nın zaman karmaşıklığı O(V3)'tür, burada V düğüm sayısını temsil eder. Bu, algoritmanın büyük çizgelerde yavaş olabileceği anlamına gelir, ancak tüm düğüm çiftleri arasındaki en kısa yolları bulmak için etkili bir yöntemdir.

Sınırlamalar

• Negatif Ağırlıklı Döngüler: Algoritma, negatif ağırlıklı döngüler içeren çizgelerde doğru sonuç vermez.
• Büyük Çizgeler: O(V3) zaman karmaşıklığı nedeniyle, çok büyük çizgelerde verimli değildir.