Algorytm Floyda-Warshalla

Opis

Algorytm Floyda-Warshalla pozwala znaleźć dla grafu skierowanego z pewnym wagami krawędzi znaleźć najkrótszą cieżkę pomiędzy dwom wybranymi wierzchołkami przechodząc pomiędzy nimi k innych wierzchołków. Wagi ujemne krawędzi są możliwe, ale pod warunkiem, że graf nie ma ujemnych cykli (wtedy wyniki są niepoprawne).

Algorytm

Algorytm rozpoczyna się od utworzenia pustej macierzy n×n w której zostaną zapisane dane początkowe. Jeśli od wierzchołka i istnieje krawędź do j to na pozycji (i, j) należy zapisać wartość krawędzi oraz poprzednika i. Jeśli jednak dana krawędź nie istnieje to odległość należy ustalić na nieskończoność, a poprzednika na nieustawionego. W rezultacie otrzymuje się macierz najkrótszych ścieżek dla k = 0 wierzchołków pośrednich. Macierz ta będzie identyczna z macierzą wejściową.

Tworzenie kolejnej macierzy k będzie pobierać dane z macierzy poprzedniej k-1. Dla każdego połączenia (i, j) sprawdzane jest czy suma dystansu (i, k) oraz (k, j) jest mniejsza od dystansu zapisanego w polu (i, j). Jeśli warunek jest spełniony to krawędź (i, j) zostaje ustalona na obliczoną sumę, a poprzednik na k. W przypadku, gdy warunek nie jest spełniony to należy skopiować dystans oraz poprzednika.

Przykład

Dla przykładu na poniższym grafie zostanie wykonany algorytm Floyda-Warshalla:

Przykładowy graf

Macierz k = 0 będzie wyglądać następująco:

Macierz k = 1 nie zmienia się. Dla żadnej prawy wybranych wierzchołków nie został spełniony warunek:

Sytuacja zmienia sie dla macierzy k = 2, ponieważ zaktualizowane zostają puste dotychczas wartości dla wierzchołka 3. Jak można zauważyć na grafie jest to wierzchołek najlepiej skomunikowany z innymi. Przykładowo wartość pomiędzy (3, 2) zostaje zaktualizowana, ponieważ:

(3, 1) + (1, 2) = 5 + 4 = 9 co jest mniejsze niż dotychczasowa wartość nieskończoność na tym polu

(3, 1) + (1, 3) = 1 + 5 = 9 co też jest mniejsze niż nieskończoność

Kolejna macierz k = 2 ostatecznie wygląda następująco:

Z tej macierzy możemy odczytać, że chcąc przejść od wierzchołka 3 z powrotem do 3 najkrótsza droga wynosi 6 i prowadzi ona od wierzchołka 3 poprzez 1 oraz 0 z powrotem do wierzchołka 3. Obliczenia kolejnych macierzy można kontynuować, aż do macierz k = 5.

Implementacja

Założenia

Funkcja FloydWarshall() dla podanego grafu zwróci tablicę macierzy, gdzie q-tej pozycji będzie macierz dla k = q. Dla każdego pola macierzy będzie można odczytać dystans do wierzchołka oraz poprzednika. Algorytm nie będzie sprawdzał poprawności danych wejściowych - o tym powinien wiedzieć sam użytkownik. Graf ma zostać przekazany jako macierz. Przykładowo następujący graf:

Graf

ma zostać przekazany w programie jako następująca macierz:

1. 0 0 0 3 0
2. 3 0 4 1 0
3. 0 -1 0 2 0
4. -2 5 0 0 2
5. 0 0 1 0 0

Rozwiązanie

Przechowywanie danych

W celu przechowania danych utworzony zostaje specjalny typ, który dla wybranego wierzchołka pozwoli przechować jego dystans oraz poprzednika.

1. struct dane {
2.   int dyst;
3.   int poprzednik;
4. };

Dodawanie odległości

W trakcie działania algorytmu będą dodawane bardzo różne wartości. W założeniu największa wartość zmiennej to nieskończoność, ale komputer będzie traktował to jako zwykłą liczbę i próbował dodać te dwie wartości. Z tego powodu potrzebna jest specjalna funkcja dodawania dwóch wartości, że jeśli choć jedna z nich jest nieskończonością to na pewno wynikiem będzie nieskończoność.

1. int addSaturate(int x, int y) {
2.   if (x == INT_MAX || y == INT_MAX)
3.     return INT_MAX;
4.   if (INT_MAX - x >= y) {
5.     return x + y;
6.   } else {
7.     return INT_MAX;
8.   }
9. }

Algorytm

Funkcja FloydWarshall() dla podanej macierzy danych szuka k kolejnych macierz, które będą wyznaczać najkrótsze ścieżki o k pośrednich wierzchołkach.

1. dane*** FloydWarshall(int** macierz, int n, int k) {
2.   dane*** wynik = new dane**[k];
3.   for (int q = 0; q < k; q++) {
4.     wynik[q] = new dane*[n];
5.     for (int i = 0; i < n; i++)
6.       wynik[q][i] = new dane[n];
7.   }
9.   for (int i = 0; i < n; i++) {
10.     for (int j = 0; j < n; j++) {
11.       if (macierz[i][j] != 0) {
12.         wynik[0][i][j].dyst = macierz[i][j];
13.         wynik[0][i][j].poprzednik = i;
14.       } else {
15.         wynik[0][i][j].dyst = INT_MAX;
16.         wynik[0][i][j].poprzednik = -1;
17.       }
18.     }
19.   }
21.   for (int q = 1; q < k; q++) {
22.     for (int i = 0; i < n; i++) {
23.       for (int j = 0; j < n; j++) {
24.         int dyst = addSaturate(wynik[q - 1][i][q - 1].dyst, wynik[q - 1][q - 1][j].dyst);
25.         if (dyst < wynik[q - 1][i][j].dyst) {
26.           wynik[q][i][j].dyst = dyst;
27.           wynik[q][i][j].poprzednik = q - 1;
28.         } else {
29.           wynik[q][i][j].dyst = wynik[q - 1][i][j].dyst;
30.           wynik[q][i][j].poprzednik = wynik[q - 1][i][j].poprzednik;
31.         }
32.       }
33.     }
34.   }
36.   return wynik;
37. }

(2. - 7.) Deklaracja struktury danych do zapisu informacji. Jest to trójwymiarowa tablica, gdzie pierwszy wymiar to numer macierzy, drugi to numer wiersza, a ostatni kolumny. Następnie (9. - 18.) tworzona jest macierz k = 0 od której zależeć będą dalsze obliczenia. Dalej (20. - 33.) wypełniane są kolejne macierze na podstawie poprzednich. Na koniec (35.) zwrócony zostaje wynik.

Testowanie funkcji

W celu przetestowania kodu można skorzystać z poniższego fragmentu kodu, który wczyta od użytkownika potrzebne dane, a na koniec wypisze wszystkie obliczone macierze:

1. int main() {
2.   int n, k;
3.   cout << "Ile wierzcholkow ma graf?\n n = ";
4.   cin >> n;
5.   cout << "Ile punktow posrednich?\n k = ";
6.   cin >> k;
7.   cout << "Podaj macierz:" << endl;
8.   int** macierz = new int*[n];
9.   for (int i = 0; i < n; i++) {
10.     macierz[i] = new int[n];
11.     for (int j = 0; j < n; j++)
12.       cin >> macierz[i][j];
13.   }
14.   dane*** wynik = FloydWarshall(macierz, n, k);
15.   for (int q = 0; q < k; q++) {
16.     cout << "[ k = " << q << " ]\n";
17.     for (int i = 0; i < n; i++) {
18.       for (int j = 0; j < n; j++)
19.         wypiszDane(wynik[q][i][j]);
20.       cout << endl;
21.     }
22.     cout << "\n\n";
23.   }
24.   system("pause");
25.   return 0;
26. }

• Kod źródłowy Implementacja