Spis treści:

Kategoria:AlgorytmyC#


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_SIZE = Rozmiar;
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 TAB_SIZE = 3;
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:

List<int> floydPath = f.getPath(0, 2);

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ę:

public const int INF = int.MaxValue;
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:

this.path = path;
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:

public void Evaluate(int len, int[,] path)
{
    //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:

public List<int> getPath(int from, int to)
{
    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:

private void getPathRec(List<int> path, int from, int to)
{
    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.

Kategoria:AlgorytmyC#

, 2013-12-20

Brak komentarzy - bądź pierwszy

Dodaj komentarz
Wyślij
Ostatnie komentarze
chcę dodać kolumnę, która będzie połączeniem dwóch innych istniejących już kolumn, jak powinien wyglądać scrypt?
Przydałyby się jeszcze 2 rzeczy do cz. 3 i byłoby superanckie.
1. Na starcie sortuje wg jakiejś kolumny i tam jest już strzałeczka. Widok takiej strzałeczki daje znać użytkownikowi, że taką tabele można sortować, a na razie pojawia się ona tylko po kliknięciu.
2. Uwzględnienie polskich znaków, bo np. przy sortowaniu Nazwisk i Imion jest to bardzo uciążliwe.
Ogólnie bardzo fajnie i prosto.
PS. Jest ten artykuł z jQuery już dostępny.
bardo ciekawe , można dzięki takim wpisom dostrzec wędkę..
Bardzo dziękuję za jasne tłumaczenie z dobrze dobranym przykładem!