Floyd-Warshallin algoritmi

Tässä opetusohjelmassa opit, kuinka floyd-warshall-algoritmi toimii. Löydät myös toimivia esimerkkejä floyd-warshall-algoritmeista C-, C ++ -, Java- ja Python-versioissa.

Floyd-Warshallin algoritmi on algoritmi lyhimmän polun löytämiseksi kaikkien pisteiden parien välillä painotetussa kuvaajassa. Tämä algoritmi toimii sekä suunnatuille että suuntaamattomille painotetuille kaavioille. Mutta se ei toimi kaavioissa, joissa on negatiiviset syklit (joissa syklin reunojen summa on negatiivinen).

Painotettu kaavio on kaavio, johon jokaiseen reunaan liittyy numeerinen arvo.

Floyd-Warhshall-algoritmia kutsutaan myös nimellä Floydin algoritmi, Roy-Floydin algoritmi, Roy-Warshallin algoritmi tai WFI-algoritmi.

Tämä algoritmi noudattaa dynaamista ohjelmointitapaa löytääksesi lyhyimmät polut.

Kuinka Floyd-Warshallin algoritmi toimii?

Olkoon annettu kaavio:

Alkuperäinen kaavio

Noudata alla olevia vaiheita löytääksesi lyhimmän polun kaikkien kärkiparien välillä.

  1. Luo ulottuvuusmatriisi, jossa n on pisteiden lukumäärä. Rivi ja sarake indeksoidaan vastaavasti i: nä ja j: ksi. i ja j ovat graafin kärjet. Jokainen solu A (i) (j) on täytetty etäisyydellä kärjestä kärkeen. Jos kärjestä kärkeen ei ole polkua , solu jätetään äärettömäksi. Täytä kukin solu i: n ja j: n kärjen välisellä etäisyydelläA0n*n
    ithjthithjth
  2. Luo nyt matriisi matriisin avulla . Ensimmäisen sarakkeen ja ensimmäisen rivin elementit jätetään sellaisenaan. Loput solut täytetään seuraavalla tavalla. Olkoon k lyhin polku lähteestä määränpäähän. Tässä vaiheessa k on ensimmäinen kärki. on täynnä . Toisin sanoen, jos suora etäisyys lähteestä kohteeseen on suurempi kuin kärkipisteen k kautta kulkeva polku, solu täytetään . Tässä vaiheessa k on kärkipiste 1. Laskemme etäisyyden lähdepisteestä kärkipisteeseen kärkipisteen k kautta. Laske etäisyys lähdepisteestä kohdepisteeseen tämän kärkipisteen kautta k Esimerkiksi: 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), suora etäisyys kärjestä 2-4 on 4 ja kärjen 2-4 kärjen läpi kulkevan etäisyyden summa (eli pisteestä 2-1 ja pisteestä 1-4) on 7. Koska 4 < 7, on täytetty 4: llä.A0(2, 4)
  3. Samoin luodaan . Toisen sarakkeen ja toisen rivin elementit jätetään sellaisenaan. Tässä vaiheessa k on toinen kärki (eli kärki 2). Muut vaiheet ovat samat kuin vaiheessa 2 . Laske etäisyys lähdehuipusta kohdepisteeseen tämän kärjen 2 kauttaA2A3
  4. Samoin, ja se on myös luotu. Laske etäisyys lähipisteen ja kärkipisteen välillä tämän kärkipisteen kautta 3 Laske etäisyys lähdepisteen ja kohdepisteen välillä tämän kärkipisteen kautta 4A3A4
  5. A4 antaa lyhimmän polun kunkin huippuparin välillä.

Floyd-Warshallin algoritmi

n = pisteiden lukumäärä A = matriisi, jonka koko on n * n, kun k = 1 - n, kun i = 1 - n, jos j = 1 - n, A k (i, j) = min (A k-1 (i, j) , A k-1 (i, k) + A k-1 (k, j)) palauttaa A: n

Python-, Java- ja C / C ++ -esimerkkejä

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 Warshallin algoritmin monimutkaisuus

Ajan monimutkaisuus

Silmukoita on kolme. Jokaisella silmukalla on jatkuvasti monimutkaisuus. Joten Floyd-Warshall-algoritmin aika monimutkaisuus on .O(n3)

Avaruuden monimutkaisuus

Floyd-Warshall-algoritmin avaruus monimutkaisuus on .O(n2)

Floyd Warshallin algoritmisovellukset

  • Lyhyimmän polun löytäminen on suunnattu kaavio
  • Löytää suunnattujen kuvaajien transitiivinen sulkeminen
  • Löydä todellisten matriisien inversio
  • Sen testaamiseksi, onko suuntaamaton kaavio kaksipuolinen

Mielenkiintoisia artikkeleita...