Algoritma Floyd-Warshall

Dalam tutorial ini, anda akan belajar bagaimana algoritma floyd-warshall berfungsi. Anda juga akan mendapat contoh algoritma floyd-warshall yang berfungsi di C, C ++, Java dan Python.

Algoritma Floyd-Warshall adalah algoritma untuk mencari jalan terpendek antara semua pasangan bucu dalam graf berwajaran. Algoritma ini berfungsi untuk grafik berwajaran terarah dan tidak terarah. Tetapi, ia tidak berfungsi untuk grafik dengan kitaran negatif (di mana jumlah tepi dalam satu kitaran adalah negatif).

Graf berwajaran adalah grafik di mana setiap pinggir mempunyai nilai berangka yang berkaitan dengannya.

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

Algoritma ini mengikuti pendekatan pengaturcaraan dinamik untuk mencari jalan terpendek.

Bagaimana Algoritma Floyd-Warshall Berfungsi?

Biarkan graf yang diberikan adalah:

Graf awal

Ikuti langkah di bawah untuk mencari jalan terpendek antara semua pasangan bucu.

  1. Buat matriks dimensi di mana n ialah bilangan bucu. Baris dan lajur diindeks sebagai i dan j masing-masing. i dan j adalah bucu graf. Setiap sel A (i) (j) diisi dengan jarak dari bucu ke bucu. Sekiranya tidak ada jalan dari bucu ke bucu, sel dibiarkan sebagai tak terhingga. Isi setiap sel dengan jarak antara bucu ith dan jthA0n*n
    ithjthithjth
  2. Sekarang, buat matriks menggunakan matriks . Unsur-unsur di lajur pertama dan baris pertama dibiarkan sebagaimana adanya. Sel selebihnya diisi dengan cara berikut. Biarkan k menjadi bucu pertengahan di jalan terpendek dari sumber ke destinasi. Dalam langkah ini, k adalah bucu pertama. dipenuhi dengan . Maksudnya, jika jarak langsung dari sumber ke tujuan lebih besar daripada jalur melalui bucu k, maka sel diisi dengan . Dalam langkah ini, k adalah bucu 1. Kami mengira jarak dari bucu sumber ke bucu destinasi melalui bucu k ini. Hitungkan jarak dari titik sumber ke titik tujuan melalui bucu ini k Contohnya: 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 bucu 2 ke 4 adalah 4 dan jumlah jarak dari bucu 2 hingga 4 hingga bucu (iaitu dari bucu 2 hingga 1 dan dari bucu 1 hingga 4) adalah 7. Oleh kerana 4 < 7, diisi dengan 4.A0(2, 4)
  3. Begitu juga, dibuat menggunakan . Unsur-unsur di lajur kedua dan baris kedua dibiarkan sebagaimana adanya. Dalam langkah ini, k adalah bucu kedua (iaitu bucu 2). Langkah selebihnya sama seperti pada langkah 2 . Hitung jarak dari bucu sumber ke bucu destinasi melalui bucu 2 iniA2A3
  4. Begitu juga, dan juga diciptakan. Hitung jarak dari bucu sumber ke bucu tujuan melalui bucu ini 3 Hitung jarak dari bucu sumber ke bucu tujuan ke bucu tujuan melalui bucu ini 4A3A4
  5. A4 memberikan jalan terpendek antara setiap pasangan bucu.

Algoritma Floyd-Warshall

n = tiada titik A = matriks dimensi n * n untuk k = 1 hingga n untuk i = 1 hingga n untuk j = 1 hingga n A k (i, j) = min (A k-1 (i, j) , A k-1 (i, k) + A k-1 (k, j)) pulangkan A

Contoh Python, Java dan C / C ++

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

Kerumitan Algoritma Floyd Warshall

Kerumitan Masa

Terdapat tiga gelung. Setiap gelung mempunyai kerumitan yang berterusan. Jadi, kerumitan masa algoritma Floyd-Warshall adalah .O(n3)

Kerumitan Ruang

Kerumitan ruang algoritma Floyd-Warshall adalah .O(n2)

Aplikasi Algoritma Floyd Warshall

  • Untuk mencari jalan terpendek adalah graf yang diarahkan
  • Untuk mencari penutupan transitif graf yang diarahkan
  • Untuk mencari Pembalikan matriks sebenar
  • Untuk menguji sama ada graf yang tidak diarahkan adalah bipartit

Artikel menarik...