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. class dane:
2.   def __init__(self):
3.     self.dyst = 0;
4.     self.poprzednik = -1;

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. def addSaturate(x, y):
2.   if (x == sys.maxsize or y == sys.maxsize):
3.     return sys.maxsize
4.   if (sys.maxsize - x >= y):
5.     return x + y
6.   else:
7.     return sys.maxsize

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. def FloydWarshall(macierz, n, k):
2.   wynik = [[[dane() for i in range(n)] for j in range(n)] for q in range(k)]
4.   for i in range(n):
5.     for j in range(n):
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 = sys.maxsize
11.         wynik[0][i][j].poprzednik = -1
13.   for q in range(1, k):
14.     for i in range(n):
15.       for j in range(n):
16.         dyst = addSaturate(wynik[q - 1][i][q - 1].dyst, wynik[q - 1][q - 1][j].dyst)
17.         if (dyst < wynik[q - 1][i][j].dyst):
18.           wynik[q][i][j].dyst = dyst
19.           wynik[q][i][j].poprzednik = q - 1
20.         else:
21.           wynik[q][i][j].dyst = wynik[q - 1][i][j].dyst
22.           wynik[q][i][j].poprzednik = wynik[q - 1][i][j].poprzednik
24.   return wynik;

(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. - 12.) tworzona jest macierz k = 0 od której zależeć będą dalsze obliczenia. Dalej (14. - 24.) wypełniane są kolejne macierze na podstawie poprzednich. Na koniec (26.) 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. n = int(input("Ile wierzchołków ma graf?\n n = "))
2. k = int(input("Ile punktów pośrednich?\n k = "))
3. print("Podaj macierz:")
4. macierz = [[0 for i in range(n)] for j in range(n)]
5. for i in range(n):
6.   data = [int(x) for x in input().split()]
7.   for j in range(n):
8.     macierz[i][j] = int(data[j])
9. wynik = FloydWarshall(macierz, n, k);
10. for q in range(k):
11.   print("[ k = " + str(q) + " ]")
12.   for i in range(n):
13.     for j in range(n):
14.       wypiszDane(wynik[q][i][j]);
15.     print()
16.   print('\n')

• Kod źródłowy Implementacja