Floyd-Warshall Algoritması

Bu eğitimde floyd-warshall algoritmasının nasıl çalıştığını öğreneceksiniz. Ayrıca, floyd-warshall algoritmasının çalışma örneklerini C, C ++, Java ve Python'da bulacaksınız.

Floyd-Warshall Algoritması, ağırlıklı bir grafikteki tüm köşe çiftleri arasındaki en kısa yolu bulmaya yönelik bir algoritmadır. Bu algoritma hem yönlendirilmiş hem de yönsüz ağırlıklı grafikler için çalışır. Ancak, negatif döngülü (bir döngüdeki kenarların toplamının negatif olduğu) grafiklerde çalışmaz.

Ağırlıklı grafik, her bir kenarın kendisiyle ilişkilendirilmiş sayısal bir değere sahip olduğu bir grafiktir.

Floyd-Warhshall algoritması, Floyd'un algoritması, Roy-Floyd algoritması, Roy-Warshall algoritması veya WFI algoritması olarak da adlandırılır.

Bu algoritma, en kısa yolları bulmak için dinamik programlama yaklaşımını takip eder.

Floyd-Warshall Algoritması Nasıl Çalışır?

Verilen grafik şöyle olsun:

İlk grafik

Tüm köşe çiftleri arasındaki en kısa yolu bulmak için aşağıdaki adımları izleyin.

  1. N'nin köşe sayısı olduğu bir boyut matrisi oluşturun . Satır ve sütun sırasıyla i ve j olarak indekslenir. i ve j grafiğin köşeleridir. Her hücre A (i) (j), tepe noktasından tepe noktasına olan mesafeyle doldurulur . Tepe noktasından tepe noktasına hiçbir yol yoksa hücre sonsuz olarak bırakılır. Her bir hücreyi ith ve jth köşe arasındaki mesafeyle doldurunA0n*n
    ithjthithjth
  2. Şimdi, matrisi kullanarak bir matris oluşturun . İlk sütun ve ilk satırdaki öğeler olduğu gibi bırakılır. Kalan hücreler aşağıdaki şekilde doldurulur. Kaynaktan hedefe giden en kısa yoldaki ara köşe k olsun. Bu adımda, k ilk köşe noktasıdır. ile doldurulur . Yani, kaynaktan hedefe olan doğrudan mesafe, tepe noktası k üzerinden geçen yoldan daha büyükse, hücre ile doldurulur . Bu adımda, k köşe 1'dir. Bu köşe k üzerinden kaynak tepe noktasından hedef tepe noktasına olan mesafeyi hesaplıyoruz. Bu köşe boyunca kaynak tepe noktasından hedef tepe noktasına olan mesafeyi hesaplayın k Örneğin:A1A0
    A(i)(j)(A(i)(k) + A(k)(j)) if (A(i)(j)> A(i)(k) + A(k)(j))
    A(i)(k) + A(k)(j)

    A1(2, 4)4'e tepe 2 arasında doğrudan mesafeden 4 ve tepe boyunca 4 tepe 2 mesafenin toplam (yani. Tepe 2 ila 1 ve tepe 1 ila 4) yana 7'dir 4 < 7, 4 ile doldurulur.A0(2, 4)
  3. Benzer şekilde kullanılarak oluşturulur . İkinci sütun ve ikinci satırdaki öğeler olduğu gibi bırakılır. Bu adımda, k ikinci tepe noktasıdır (yani tepe 2). Kalan adımlar 2. adımdaki ile aynıdır . Bu köşe 2 üzerinden kaynak tepe noktasından hedef tepe noktasına olan mesafeyi hesaplayınA2A3
  4. Benzer şekilde ve ayrıca yaratılmıştır. Bu köşe boyunca kaynak tepe noktasından hedef tepe noktasına olan mesafeyi hesaplayın 3 Bu tepe noktası boyunca kaynak tepe noktasından hedef tepe noktasına olan mesafeyi hesaplayın 4A3A4
  5. A4 her bir köşe çifti arasındaki en kısa yolu verir.

Floyd-Warshall Algoritması

n = köşe sayısı A = k = 1 ila n için n * n boyutunun matrisi i = 1 ila n için j = 1 ila n A k (i, j) = min (A k-1 (i, j) , A k-1 (i, k) + A k-1 (k, j)) dönüş A

Python, Java ve C / C ++ Örnekleri

Python Java C C ++ 
 # Floyd Warshall Algorithm in python # The number of vertices nV = 4 INF = 999 # Algorithm implementation def floyd_warshall(G): distance = list(map(lambda i: list(map(lambda j: j, i)), G)) # Adding vertices individually for k in range(nV): for i in range(nV): for j in range(nV): distance(i)(j) = min(distance(i)(j), distance(i)(k) + distance(k)(j)) print_solution(distance) # Printing the solution def print_solution(distance): for i in range(nV): for j in range(nV): if(distance(i)(j) == INF): print("INF", end=" ") else: print(distance(i)(j), end=" ") print(" ") G = ((0, 3, INF, 5), (2, 0, INF, 4), (INF, 1, 0, INF), (INF, INF, 2, 0)) floyd_warshall(G)
 // Floyd Warshall Algorithm in Java class FloydWarshall ( final static int INF = 9999, nV = 4; // Implementing floyd warshall algorithm void floydWarshall(int graph()()) ( int matrix()() = new int(nV)(nV); int i, j, k; for (i = 0; i < nV; i++) for (j = 0; j < nV; j++) matrix(i)(j) = graph(i)(j); // Adding vertices individually for (k = 0; k < nV; k++) ( for (i = 0; i < nV; i++) ( for (j = 0; j < nV; j++) ( if (matrix(i)(k) + matrix(k)(j) < matrix(i)(j)) matrix(i)(j) = matrix(i)(k) + matrix(k)(j); ) ) ) printMatrix(matrix); ) void printMatrix(int matrix()()) ( for (int i = 0; i < nV; ++i) ( for (int j = 0; j < nV; ++j) ( if (matrix(i)(j) == INF) System.out.print("INF "); else System.out.print(matrix(i)(j) + " "); ) System.out.println(); ) ) public static void main(String() args) ( int graph()() = ( ( 0, 3, INF, 5 ), ( 2, 0, INF, 4 ), ( INF, 1, 0, INF ), ( INF, INF, 2, 0 ) ); FloydWarshall a = new FloydWarshall(); a.floydWarshall(graph); ) )
 // Floyd-Warshall Algorithm in C #include // defining the number of vertices #define nV 4 #define INF 999 void printMatrix(int matrix()(nV)); // Implementing floyd warshall algorithm void floydWarshall(int graph()(nV)) ( int matrix(nV)(nV), i, j, k; for (i = 0; i < nV; i++) for (j = 0; j < nV; j++) matrix(i)(j) = graph(i)(j); // Adding vertices individually for (k = 0; k < nV; k++) ( for (i = 0; i < nV; i++) ( for (j = 0; j < nV; j++) ( if (matrix(i)(k) + matrix(k)(j) < matrix(i)(j)) matrix(i)(j) = matrix(i)(k) + matrix(k)(j); ) ) ) printMatrix(matrix); ) void printMatrix(int matrix()(nV)) ( for (int i = 0; i < nV; i++) ( for (int j = 0; j < nV; j++) ( if (matrix(i)(j) == INF) printf("%4s", "INF"); else printf("%4d", matrix(i)(j)); ) printf(""); ) ) int main() ( int graph(nV)(nV) = ((0, 3, INF, 5), (2, 0, INF, 4), (INF, 1, 0, INF), (INF, INF, 2, 0)); floydWarshall(graph); )
 // Floyd-Warshall Algorithm in C++ #include using namespace std; // defining the number of vertices #define nV 4 #define INF 999 void printMatrix(int matrix()(nV)); // Implementing floyd warshall algorithm void floydWarshall(int graph()(nV)) ( int matrix(nV)(nV), i, j, k; for (i = 0; i < nV; i++) for (j = 0; j < nV; j++) matrix(i)(j) = graph(i)(j); // Adding vertices individually for (k = 0; k < nV; k++) ( for (i = 0; i < nV; i++) ( for (j = 0; j < nV; j++) ( if (matrix(i)(k) + matrix(k)(j) < matrix(i)(j)) matrix(i)(j) = matrix(i)(k) + matrix(k)(j); ) ) ) printMatrix(matrix); ) void printMatrix(int matrix()(nV)) ( for (int i = 0; i < nV; i++) ( for (int j = 0; j < nV; j++) ( if (matrix(i)(j) == INF) printf("%4s", "INF"); else printf("%4d", matrix(i)(j)); ) printf(""); ) ) int main() ( int graph(nV)(nV) = ((0, 3, INF, 5), (2, 0, INF, 4), (INF, 1, 0, INF), (INF, INF, 2, 0)); floydWarshall(graph); )

Floyd Warshall Algoritma Karmaşıklığı

Zaman Karmaşıklığı

Üç döngü var. Her döngünün sabit karmaşıklıkları vardır. Yani Floyd-Warshall algoritmasının zaman karmaşıklığı .O(n3)

Uzay Karmaşıklığı

Floyd-Warshall algoritmasının uzay karmaşıklığı .O(n2)

Floyd Warshall Algoritma Uygulamaları

  • En kısa yolu bulmak, yönlendirilmiş bir grafiktir
  • Yönlendirilmiş grafiklerin geçişli kapanışını bulmak için
  • Gerçek matrislerin Tersini Bulmak İçin
  • Yönlendirilmemiş bir grafiğin iki taraflı olup olmadığını test etmek için

Ilginç makaleler...