Αλγόριθμος Floyd-Warshall

Πίνακας περιεχομένων

Πώς λειτουργεί ο αλγόριθμος Floyd-Warshall;
Αλγόριθμος Floyd-Warshall
Παραδείγματα Python, Java και C / C ++
Πολυπλοκότητα του αλγόριθμου Floyd Warshall
Εφαρμογές αλγόριθμου Floyd Warshall

Σε αυτό το σεμινάριο, θα μάθετε πώς λειτουργεί ο αλγόριθμος floyd-warshall. Επίσης, θα βρείτε λειτουργικά παραδείγματα αλγόριθμου floyd-warshall σε C, C ++, Java και Python.

Ο αλγόριθμος Floyd-Warshall είναι ένας αλγόριθμος για την εύρεση της συντομότερης διαδρομής μεταξύ όλων των ζευγών κορυφών σε ένα σταθμισμένο γράφημα. Αυτός ο αλγόριθμος λειτουργεί τόσο για τα κατευθυνόμενα όσο και για μη κατευθυνόμενα σταθμισμένα γραφήματα. Όμως, δεν λειτουργεί για τα γραφήματα με αρνητικούς κύκλους (όπου το άθροισμα των άκρων σε έναν κύκλο είναι αρνητικό).

Ένα σταθμισμένο γράφημα είναι ένα γράφημα στο οποίο κάθε άκρο έχει μια αριθμητική τιμή που σχετίζεται με αυτό.

Ο αλγόριθμος Floyd-Warhshall καλείται επίσης ως αλγόριθμος Floyd, αλγόριθμος Roy-Floyd, αλγόριθμος Roy-Warshall ή αλγόριθμος WFI.

Αυτός ο αλγόριθμος ακολουθεί τη δυναμική προσέγγιση προγραμματισμού για να βρει τις μικρότερες διαδρομές.

Πώς λειτουργεί ο αλγόριθμος Floyd-Warshall;

Αφήστε το δεδομένο γράφημα να είναι:

Αρχικό γράφημα

Ακολουθήστε τα παρακάτω βήματα για να βρείτε τη συντομότερη διαδρομή μεταξύ όλων των ζευγών κορυφών.

Δημιουργήστε έναν πίνακα διαστάσεων όπου n είναι ο αριθμός κορυφών. Η σειρά και η στήλη ευρετηριάζονται ως i και j αντίστοιχα. i και j είναι οι κορυφές του γραφήματος. Κάθε κελί A (i) (j) γεμίζει με την απόσταση από την κορυφή έως την κορυφή. Εάν δεν υπάρχει διαδρομή από κορυφή σε κορυφή, το κελί παραμένει ως άπειρο. Γεμίστε κάθε κελί με την απόσταση μεταξύ της κορυφής ith και jthA⁰n*n
i^thj^thi^thj^th
Τώρα, δημιουργήστε έναν πίνακα χρησιμοποιώντας το matrix . Τα στοιχεία στην πρώτη στήλη και στην πρώτη σειρά παραμένουν ως έχουν. Τα υπόλοιπα κελιά γεμίζονται με τον ακόλουθο τρόπο. Αφήστε το k να είναι η ενδιάμεση κορυφή στη συντομότερη διαδρομή από πηγή προς προορισμό. Σε αυτό το βήμα, το k είναι η πρώτη κορυφή. είναι γεμάτο με . Δηλαδή, εάν η άμεση απόσταση από την πηγή προς τον προορισμό είναι μεγαλύτερη από τη διαδρομή μέσω της κορυφής k, τότε το κελί γεμίζει με . Σε αυτό το βήμα, το k είναι κορυφή 1. Υπολογίζουμε την απόσταση από την κορυφή πηγής έως την κορυφή προορισμού μέσω αυτής της κορυφής k. Υπολογίστε την απόσταση από την κορυφή πηγής έως την κορυφή προορισμού μέσω αυτής της κορυφής k Για παράδειγμα: ΓιαA¹A⁰
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)

A¹(2, 4), η άμεση απόσταση από την κορυφή 2 έως 4 είναι 4 και το άθροισμα της απόστασης από την κορυφή 2 έως 4 έως την κορυφή (δηλαδή από την κορυφή 2 έως 1 και από την κορυφή 1 έως 4) είναι 7. Δεδομένου 4 < 7, γεμίζεται με 4.A⁰(2, 4)
Ομοίως, δημιουργείται χρησιμοποιώντας . Τα στοιχεία στη δεύτερη στήλη και τη δεύτερη σειρά παραμένουν ως έχουν. Σε αυτό το βήμα, το k είναι η δεύτερη κορυφή (δηλ. Η κορυφή 2). Τα υπόλοιπα βήματα είναι τα ίδια όπως στο βήμα 2 . Υπολογίστε την απόσταση από την κορυφή πηγής έως την κορυφή προορισμού μέσω αυτής της κορυφής 2A²A³
Ομοίως, και δημιουργείται επίσης. Υπολογίστε την απόσταση από την κορυφή πηγής έως την κορυφή προορισμού μέσω αυτής της κορυφής 3 Υπολογίστε την απόσταση από την κορυφή πηγής έως την κορυφή προορισμού μέσω αυτής της κορυφής 4A³A⁴
A⁴ δίνει τη συντομότερη διαδρομή μεταξύ κάθε ζεύγους κορυφών.

Αλγόριθμος Floyd-Warshall

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