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.   public int dyst;
3.   public 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. static int addSaturate(int x, int y) {
2.   if (x == int.MaxValue || y == int.MaxValue)
3.     return int.MaxValue;
4.   if (int.MaxValue - x >= y) {
5.     return x + y;
6.   } else {
7.     return int.MaxValue;
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. static dane[,,] FloydWarshall(int[,] macierz, int n, int k) {
2.   dane[,,] wynik = new dane[k, n, n];
4.   for (int i = 0; i < n; i++) {
5.     for (int j = 0; j < n; j++) {
6.       if (macierz[i, j] != 0) {
7.         wynik[0, i, j].dyst = macierz[i, j];
8.         wynik[0, i, j].poprzednik = i;
9.       } else {
10.         wynik[0, i, j].dyst = int.MaxValue;
11.         wynik[0, i, j].poprzednik = -1;
12.       }
13.     }
14.   }
16.   for (int q = 1; q < k; q++) {
17.     for (int i = 0; i < n; i++) {
18.       for (int j = 0; j < n; j++) {
19.         int dyst = addSaturate(wynik[q - 1, i, q - 1].dyst, wynik[q - 1, q - 1, j].dyst);
20.         if (dyst < wynik[q - 1, i, j].dyst) {
21.           wynik[q, i, j].dyst = dyst;
22.           wynik[q, i, j].poprzednik = q - 1;
23.         } else {
24.           wynik[q, i, j].dyst = wynik[q - 1, i, j].dyst;
25.           wynik[q, i, j].poprzednik = wynik[q - 1, i, j].poprzednik;
26.         }
27.       }
28.     }
29.   }
31.   return wynik;
32. }

(2.) 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 (4. - 14.) tworzona jest macierz k = 0 od której zależeć będą dalsze obliczenia. Dalej (16. - 29.) wypełniane są kolejne macierze na podstawie poprzednich. Na koniec (31.) 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. static void Main(string[] args) {
2.   Console.Write("Ile wierzchołków ma graf?\n n = ");
3.   int n = Convert.ToInt32(Console.ReadLine());
4.   Console.Write("Ile punktów pośrednich?\n k = ");
5.   int k = Convert.ToInt32(Console.ReadLine());
6.   Console.WriteLine("Podaj macierz:");
7.   int[,] macierz = new int[n, n];
8.   for (int i = 0; i < n; i++) {
9.     string[] dane = Console.ReadLine().Split(' ');
10.     for (int j = 0; j < n; j++)
11.       macierz[i, j] = Convert.ToInt32(dane[j]);
12.   }
13.   dane[,,] wynik = FloydWarshall(macierz, n, k);
14.   for (int q = 0; q < k; q++) {
15.     Console.WriteLine("[ k = {0} ]", q);
16.     for (int i = 0; i < n; i++) {
17.       for (int j = 0; j < n; j++)
18.         wypiszDane(wynik[q, i, j]);
19.       Console.WriteLine();
20.     }
21.     Console.Write("\n\n");
22.   }
23.   Console.ReadKey();
24. }

• Kod źródłowy Implementacja