Algoritma Floyd-Warshall

Dalam tutorial ini, Anda akan mempelajari cara kerja algoritma floyd-warshall. Juga, Anda akan menemukan contoh kerja algoritma floyd-warshall di C, C ++, Java dan Python.

Algoritma Floyd-Warshall adalah algoritma untuk mencari jalur terpendek antara semua pasangan simpul dalam sebuah graf berbobot. Algoritme ini berfungsi untuk grafik berbobot terarah dan tidak terarah. Namun, ini tidak berfungsi untuk grafik dengan siklus negatif (di mana jumlah tepi dalam satu siklus negatif).

Grafik berbobot adalah grafik di mana setiap sisi memiliki nilai numerik yang terkait dengannya.

Algoritma Floyd-Warhshall juga disebut sebagai algoritma Floyd, algoritma Roy-Floyd, algoritma Roy-Warshall, atau algoritma WFI.

Algoritma ini mengikuti pendekatan pemrograman dinamis untuk menemukan jalur terpendek.

Bagaimana Algoritma Floyd-Warshall Bekerja?

Biarkan grafik yang diberikan menjadi:

Grafik awal

Ikuti langkah-langkah di bawah ini untuk menemukan jalur terpendek di antara semua pasangan simpul.

  1. Buat matriks dimensi di mana n adalah jumlah simpul. Baris dan kolom masing-masing diindeks sebagai i dan j. i dan j adalah simpul dari grafik. Setiap sel A (i) (j) diisi dengan jarak dari puncak ke puncak. Jika tidak ada jalur dari simpul ke simpul, sel dibiarkan tak terhingga. Isi setiap sel dengan jarak antara simpul ke-i dan ke-jA0n*n
    ithjthithjth
  2. Sekarang buat matriks menggunakan matriks . Elemen-elemen di kolom pertama dan baris pertama dibiarkan apa adanya. Sel-sel yang tersisa diisi dengan cara berikut. Misalkan k adalah simpul perantara di jalur terpendek dari sumber ke tujuan. Dalam langkah ini, k adalah puncak pertama. diisi dengan . Artinya, jika jarak langsung dari sumber ke tujuan lebih besar dari jalur melalui simpul k, maka sel terisi . Pada langkah ini, k adalah simpul 1. Kami menghitung jarak dari simpul sumber ke simpul tujuan melalui simpul k ini. Hitung jarak dari simpul sumber ke simpul tujuan melalui simpul ini k. Contoh: UntukA1A0
    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), jarak langsung dari simpul 2 ke 4 adalah 4 dan jumlah jarak dari simpul 2 ke 4 melalui simpul (yaitu dari simpul 2 ke 1 dan dari simpul 1 ke 4) adalah 7. Karena 4 < 7, diisi dengan 4.A0(2, 4)
  3. Demikian pula, dibuat menggunakan . Elemen-elemen di kolom kedua dan baris kedua dibiarkan apa adanya. Dalam langkah ini, k adalah puncak kedua (yaitu puncak 2). Langkah-langkah selanjutnya sama seperti pada langkah 2 . Hitung jarak dari simpul sumber ke simpul tujuan melalui simpul 2 iniA2A3
  4. Demikian pula, dan juga dibuat. Hitung jarak dari simpul sumber ke simpul tujuan melalui simpul ini 3 Hitung jarak dari simpul sumber ke simpul tujuan melalui simpul 4 iniA3A4
  5. A4 memberikan jalur terpendek antara setiap pasangan simpul.

Algoritma Floyd-Warshall

n = jumlah simpul A = matriks berdimensi n * n untuk k = 1 ke n untuk i = 1 ke n untuk j = 1 ke n A k (i, j) = min (A k-1 (i, j) , A k-1 (i, k) + A k-1 (k, j)) mengembalikan A

Contoh Python, Java dan C / C ++

Python Java 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); )

Kompleksitas Algoritma Floyd Warshall

Kompleksitas Waktu

Ada tiga putaran. Setiap loop memiliki kompleksitas yang konstan. Jadi, kompleksitas waktu dari algoritma Floyd-Warshall adalah .O(n3)

Kompleksitas Ruang

Kompleksitas ruang dari algoritma Floyd-Warshall adalah .O(n2)

Aplikasi Algoritma Floyd Warshall

  • Untuk menemukan jalur terpendek adalah grafik berarah
  • Untuk menemukan penutupan transitif dari grafik berarah
  • Untuk menemukan Inversi matriks nyata
  • Untuk menguji apakah graf tak berarah adalah bipartit

Artikel yang menarik...