Алгоритм Флойда-Варшалла

У цьому підручнику ви дізнаєтесь, як працює алгоритм floyd-warshall. Крім того, ви знайдете робочі приклади алгоритму floyd-warshall в C, C ++, Java та Python.

Алгоритм Флойда-Варшалла - це алгоритм пошуку найкоротшого шляху між усіма парами вершин у зваженому графіку. Цей алгоритм працює як для спрямованих, так і для неорієнтованих зважених графіків. Але це не працює для графіків з від’ємними циклами (де сума ребер у циклі від’ємна).

Зважений графік - це графік, у якому кожне ребро має пов'язане з ним числове значення.

Алгоритм Флойда-Уорхшалла також називають алгоритмом Флойда, алгоритмом Роя-Флойда, алгоритмом Роя-Варшалла або алгоритмом WFI.

Цей алгоритм використовує підхід динамічного програмування для пошуку найкоротших шляхів.

Як працює алгоритм Флойда-Варшалла?

Нехай даний графік буде:

Початковий графік

Виконайте наведені нижче дії, щоб знайти найкоротший шлях між усіма парами вершин.

  1. Створіть матрицю розмірності, де n - кількість вершин. Рядок і стовпець індексуються як i та j відповідно. i і j - вершини графіка. Кожна комірка A (i) (j) заповнена відстанню від вершини до вершини. Якщо немає шляху від вершини до вершини, клітинку залишають як нескінченність. Заповніть кожну клітинку відстанню між i-ю та j-ю вершинамиA0n*n
    ithjthithjth
  2. Тепер створіть матрицю за допомогою матриці . Елементи в першому стовпці та першому рядку залишаються такими, якими вони є. Решта комірок заповнюються наступним чином. Нехай k - проміжна вершина найкоротшого шляху від джерела до пункту призначення. На цьому кроці k - перша вершина. заповнюється . Тобто, якщо пряма відстань від джерела до пункту призначення більша за шлях через вершину k, тоді комірка заповнена . На цьому кроці k є вершиною 1. Ми обчислюємо відстань від вихідної вершини до вершини призначення через цю вершину k. Обчисліть відстань від вихідної вершини до вершини призначення через цю вершину k Наприклад: ForA1A0
    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), пряма відстань від вершини 2 до 4 дорівнює 4, а сума відстані від вершини 2 до 4 через вершину (тобто від вершини 2 до 1 і від вершини 1 до 4) дорівнює 7. Оскільки 4 < 7, заповнюється 4.A0(2, 4)
  3. Аналогічним чином створюється за допомогою . Елементи у другому стовпці та другому рядку залишаються такими, якими вони є. На цьому кроці k - друга вершина (тобто вершина 2). Решта кроків такі ж, як у кроці 2 . Обчисліть відстань від вихідної вершини до вершини призначення через цю вершину 2A2A3
  4. Подібним чином, і також створюється. Розрахувати відстань від вихідної вершини до вершини призначення через цю вершину 3 Розрахувати відстань від вихідної вершини до вершини призначення через цю вершину 4A3A4
  5. A4 дає найкоротший шлях між кожною парою вершин.

Алгоритм Флойда-Варшалла

n = кількість вершин A = матриця розмірності n * n для k = 1 до n для i = 1 до n для j = 1 до n A k (i, j) = min (A k-1 (i, j) , A k-1 (i, k) + A k-1 (k, j)) повернення A

Приклади Python, Java та 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); )

Складність алгоритму Флойда Варшалла

Складність часу

Є три петлі. Кожен цикл має постійні складності. Отже, часова складність алгоритму Флойда-Варшалла є .O(n3)

Складність простору

Космічна складність алгоритму Флойда-Варшалла є .O(n2)

Застосування алгоритму Флойда Варшалла

  • Щоб знайти найкоротший шлях, це спрямований графік
  • Знайти транзитивне замикання спрямованих графіків
  • Знайти інверсію дійсних матриць
  • Для перевірки того, чи є неорієнтований графік дводольним

Цікаві статті...