Przykładowa implementacja algorytmu Floyda-Warshalla w C#.NET
W którymś z poprzednich wpisów pisałem o zasadzie działania i innych parametrach algorytmu Floyda-Warshalla. Dzisiaj będzie to, co programiści lubią najbardziej: czysty kod. Tak dokładnie mówiąc, prawie czysty, bo pojawi się kilka zdań wyjaśnienia.
Na początek krótkie wyjaśnienie. Wartością wejściową funkcji właściwej będzie tablica dwuwymiarowa, a ściślej mówiąc macierz o takiej samej liczbie kolumn i wierszy. Definicja takiej macierzy zaprezentowana jest poniżej.
int[,] tab = new int[TAB_SIZE, TAB_SIZE];
Zastanówmy się, jak chcielibyśmy używać takiego algorytmu. Pierwszym etapem zawsze będzie przygotowanie danych wejściowych, a następnie przekazanie ich do metody właściwej. W C# nie można tworzyć metod w próżni, tylko trzeba je umieszczać w klasach. Z tych rozważań można wysnuć pierwszy wniosek: klasa będzie się nazywała Floyd, i będzie miała metodę Evaluate przyjmującą dwuwymiarową tablicę. Dla celów przykładu metoda będzie przyjmowała jeszcze jeden argument i będzie to wartość określająca rozmiar macierzy. Kod z zewnątrz klasy może wyglądać następująco:
int[,] t = new int[TAB_SIZE, TAB_SIZE];
for (int i = 0; i < TAB_SIZE; i++)
for (int j = 0; j < TAB_SIZE; j++)
{
t[i, j] = Floyd.INF;
}
t[1, 2] = 5;
t[0, 1] = 2;
Floyd f = new Floyd();
f.Evaluate(TAB_SIZE, t);
Po wykonaniu metody Evaluate powinniśmy mieć dostęp do drugiej metody, która zwróci nam listę listę wierzchołków po drodze z punktu from do punktu to. Jeżeli nie ma połączenia, lista będzie pusta. Chcemy, aby kod służący do pobrania ścieżki wyglądał następująco:
Przejdźmy teraz do implementacji funkcji właściwych z klasy Floyd. Najpierw zdefiniujmy sobie stałe i zmienne, które będą wykorzystywane przez tę klasę:
int[,] next;
int[,] path;
W klasie są tylko trzy pola. Stała INF będzie nam oznaczała symboliczną nieskończoność, czyli brak połączenia lub nieskończenie wielki kosz połączenia. Tablica path to macierz wejściowa, czyli macierz połączeń, natomiast tablica next to tzw. macierz następników, czyli macierz pozwalająca na szybkie określenie ścieżki pomiędzy dwoma dowolnymi punktami.
Implementacja algorytmu Floyda-Warshalla
Nadszedł czas na właściwy algorytm Floyda-Warshalla z rekonstrukcją ścieżek. Kod algorytmu może wyglądać mniej więcej tak, jak poniżej:
next = new int[len, len];
for (int i = 0; i < len; i++)
for (int j = 0; j < len; j++)
if (path[i, j] == INF)
next[i, j] = INF;
else
next[i, j] = i;
for (int k = 0; k < len; k++)
for (int i = 0; i < len; i++)
for (int j = 0; j < len; j++)
if (path[i, k] != INF && path[k, j] != INF &&
path[i, k] + path[k, j] < path[i, j])
{
path[i, j] = path[i, k] + path[k, j];
next[i, j] = k;
}
for (int i = 0; i < len; i++)
if (path[i, i] < 0)
throw new ArgumentException("Negative cycles");
Oczywiście kod należy umieścić w metodzie Evaluate, która jest zadeklarowana następująco:
{
//kod metody
}
Główną częścią algorytmu jest potrójnie zagnieżdżona pętla for, w której wyszukiwane są zamienniki bezpośredniej drogi pomiędzy dwoma wierzchołkami na drogę poprzez inny wierzchołek. Początek ciała metody to przygotowanie macierzy następników w sposób następujący: jeżeli istnieje bezpośrednie połączenie pomiędzy wierzchołkami, wtedy wartością jest indeks pierwszego wierzchołka, w przeciwnym razie INF, czyli nieskończoność. Pojedyncza pętla z warunkiem na końcu ciała metody to sprawdzenie, czy graf nie zawiera cykli ujemnych. W takim przypadku wynik algorytmu będzie nieprawidłowy.
Rekonstrukcja ścieżek
Ostatnim etapem będzie implementacja metody getPath. Kod takiej metody może wyglądać tak, jak poniżej:
{
if (next == null)
return null;
if (next[from, to] == INF)
return new List<int>();
if (from == to)
return new List<int>() { from };
List<int> ret = new List<int>();
getPathRec(ret, from, to);
ret.Add(to);
return ret;
}
To pierwsza, nierekurencyjna część algorytmu rekonstrukcji ścieżki. Zanim akcja zostanie przekazana do części rekurencyjnej sprawdzane jest kilka warunków, między innymi to, czy takie połączenie wogóle istnieje i czy punkty są różne. Jeżeli warunki nie spowodują zakończenia się metody ścieżka rekonstruowana jest za pomocą następującego kodu:
{
int intermediate = next[from, to];
if (intermediate == from)
{
path.Add(from);
return;
}
getPathRec(path, from, intermediate);
getPathRec(path, intermediate, to);
}
Jak to działa? Z macierzy optymalnych decyzji (następników) pobierany jest punkt pośredni na drodze z punktu from (1) do punktu to (2). Jeżeli wartość jest równa pierwszemu punktowi, wtedy mamy pewność, że punkty są połączone bezpośrednio (popatrz na przygotowanie macierzy optymalnych decyzji w algorytmie Floyda-Warshalla). W przeciwnym razie ścieżka składa się z dwóch ścieżek: (1,punkt pośredni) połączonej ze ścieżką (punkt pośredni-2). Żeby uniknąć duplikowania punktów algorytm wstawia tylko pierwszą wartość z pary dwóch bezpośrednich punktów. Takie rozwiązanie sprawia, że po wyjściu z rekurencji nie mamy punktu ostatniego. W tym przypadku jest on doklejany w części nierekurencyjnej, a cała lista zwracana jest jako wynik pełnej operacji.
Brak komentarzy - bądź pierwszy