Spis treści:

Kategoria:AlgorytmyC#


Algorytm Dijkstry, czyli wyszukiwanie najkrótszej drogi pomiędzy dwoma wierzchołkami

Problem najkrótszej ścieżki

Nie trzeba chyba po raz kolejny powtarzać, jak wielkie znaczenie praktyczne ma rozwiązanie postawionego w temacie problemu. Jakiś czas temu przedstawiłem sposób implementacji algorytmu bardzo podobnego: był to algorytm Floyda-Warshalla. Tym, którzy jeszcze się z tamtym algorytmem nie zapoznali, zachęcam do przeczytania artykułu Algorytm Floyda-Warshalla, czyli wyszukiwanie najkrótszej drogi pomiędzy każdą parą wierzchołków. Opisane są tam między innymi zagadnienia związanie z tablicową reprezentacją grafu. Z takiej tablicowej reprezentacji będę korzystał również w przedstawionej później implementacji algorytmu Dijkstry. Dla tych, których interesuje tylko żywy kod algorytmu Floyda-Warshalla, odsyłam od razu do pełnej implementacji pod tym adresem: Przykładowa implementacja algorytmu Floyda-Warshalla w C#.NET.

Czym się różni Dijkstra od Floyda-Warshalla

Pytanie postawione w nagłówku może się niektórym wydać dziwne, ale pojawia się dość często. Algorytm Floyda-Warshalla pozwala wyliczyć ścieżki dla każdej pary wierzchołków (tak prawdę mówiąc wyliczany jest graf poprzedników, dzięki któremu obliczanie ścieżek możliwe jest przy pomocy prostego algorytmu o złożoności liniowej). Algorytm Dijkstra służy do wyliczania ścieżek pomiędzy dwoma wybranymi punktami. Nie muszę chyba przekonywać, że wyliczenie jednej ścieżki pomiędzy punktami jest szybsze od wyliczenia wszystkich ścieżek - algorytm Dijkstra ma złożoność O(n2), natomiast Floyda-Warshalla O(n3). Co więcej - algorytm Dijkstra w zdecydowanej większości przypadków może się zakończyć przedwcześnie, osiągając realnie złożoność znacznie niższą niż O(n2). To samo stwierdzenie nie dotyczy algorytmu Floyda-Warshalla.

Inne są też miejsca, gdzie te algorytmy znajdują zastosowanie: jeżeli graf jest jeden, a szukamy wielu dróg (np. wtedy, gdy posiadamy mapę miast - mapa pozostaje niezmienna). Raz przeliczony graf może nam służyć dożywotnio, o ile tylko nic się w nim nie zmieniło. Algorytm Dijkstra stosujemy tam, gdzie graf może się zmieniać, a drogi wyliczane są rzadko. Nic nie stoi na przeszkodzie, aby stworzyć pewnego rodzaju bufor, pamięć podręczną gotowych już wyników dla konkretnych par wierzchołków i w przypadku pytania o podobne drogi wyszukiwać tam gotowych rozwiązań - jest to jednak temat na całkiem inny wpis i wykracza nieco poza samo zastosowanie algorytmu.

Implementacja algorytmu w C#

Wiem, że są tacy, którzy czekają tylko na kod. Przyjrzyjmy się zatem przykładowej implementacji zaprezentowanej poniżej:

public class Dijkstra
{
    public const int INF = 1000000;
    public int[,] Graph { getset; }
    public Dijkstra(int[,] graph)
    {
        Graph = graph;
    }

    public int[] GetPath(int SRC, int DEST)
    {
        int graphSize = Graph.GetLength(0);
        int[] dist = new int[graphSize];
        int[] prev = new int[graphSize];
        int[] nodes = new int[graphSize];

        for (int i = 0; i < dist.Length; i++)
        {
            dist[i] = prev[i] = INF;
            nodes[i] = i;
        }

        dist[SRC] = 0;
        do
        {
            int smallest = nodes[0];
            int smallestIndex = 0;
            for (int i = 1; i < graphSize; i++)
            {
                if (dist[nodes[i]] < dist[smallest])
                {
                    smallest = nodes[i];
                    smallestIndex = i;
                }
            }
            graphSize--;
            nodes[smallestIndex] = nodes[graphSize];

            if (dist[smallest] == INF || smallest == DEST)
                break;

            for (int i = 0; i < graphSize; i++)
            {
                int v = nodes[i];
                int newDist = dist[smallest] + Graph[smallest, v];
                if (newDist < dist[v])
                {
                    dist[v] = newDist;
                    prev[v] = smallest;
                }
            }
        } while (graphSize > 0);
        return ReconstructPath(prev, SRC, DEST);
    }
}

Rekonstrukcja ścieżki

To, co otrzymujemy w wyniku działania algorytmu Dijkstry nie jest ścieżką - jest to, podobnie jak w przypadku algorytmu Floyda-Warshalla, tablica poprzedników. Aby otrzymać ścieżkę należy posłużyć się bardzo prostym algorytmem uzupełniającym. Popatrzmy na przykładową implementację użytej w algorytmie metody ReconstructPath:

public int[] ReconstructPath(int[] prev, int SRC, int DEST)
{
    int[] ret = new int[prev.Length];
    int currentNode = 0;
    ret[currentNode] = DEST;
    while (ret[currentNode] != INF && ret[currentNode] != SRC)
    {
        ret[currentNode + 1] = prev[ret[currentNode]];
        currentNode++;
    }
    if (ret[currentNode] != SRC)
        return null;
    int[] reversed = new int[currentNode+1];
    for (int i = currentNode; i >= 0; i--)
        reversed[currentNode - i] = ret[i];
    return reversed;
}

Przykład użycia algorytmu

Popatrzmy na rozpatrywany graf:

Przykładowy graf wejściowy algorytmu Dijkstry
Rys 1. Przykładowy graf wejściowy algorytmu Dijkstry.

A teraz popatrzmy na przykład użycia:

class Program
{
        
    static void Main(string[] args)
    {
        int INF = Dijkstra.INF;
        int[,] graph = new int[,]{
            {INF,   1, INF, INF,   6},
            {  4, INF,   1, INF,   8},
            {INF, INF, INF,   2, INF},
            {INF, INF, INF, INF,   1},
            {INF,   5, INF, INF, INF}};

        int SRC = 4;
        int DEST = 0;
        var dijkstra = new Dijkstra(graph);
        var path = dijkstra.GetPath(SRC, DEST);
    }
}

Wynikiem działania powyższego kodu, zapisanym w zmiennej path, będzie tablica elementów 4, 1, 0. Muszę jeszcze wspomnieć o rozbieżnościach w numeracji: przyjęło się, że wierzchołki grafu na rysunkach oznacza się kolejnymi liczbami naturalnymi (bez zera). Tablice w C# indeksowane są od 0. Mam nadzieję, że nikomu to nie przeszkodzi w analizie i zrozumieniu przykładu. Myślę, że przerobienie algorytmu tak, aby wierzchołki podawane były od 1 do N, zamiast od 0 do N-1 (podobnie rezultat) nie nastręczy problemów.

Pobierz kod aplikacji z algorytmem Dijkstry - Dijkstra-algorithm.zip
Archiwum zawiera wszystkie pliki niezbędne do skompilowania i uruchomienia aplikacji.

Kategoria:AlgorytmyC#

, 2013-12-20

Komentarze:

dijkstra (2015-01-17 16:06:13)
Nie wiem czy jeszcze aktualne ale gdy daje SRC = 0 a DST = 1 to sciezke znajduje bez problemu, natomiast gdy dam DST = 0 a SRC = 1 to algorytm nie dziala, wiesz czym jest to spowodowane?
PD (2015-01-21 15:34:26)
Dla pokazanego przykładu i kodu obie ścieżki odnajdywane są bez problemu. Algorytm przetwarza grafy skierowane i być może w tym tkwi problem. To, że istnieje przejście 0-1 nie oznacza wcale, że istnieje przejście 1-0. Przejścia symetryczne mogą mieć również różne wagi (koszty). Bez konkretnego przykładu trudno powiedzieć co jest nie tak.
Dodaj komentarz
Wyślij
Ostatnie komentarze
bardo ciekawe , można dzięki takim wpisom dostrzec wędkę..
Bardzo dziękuję za jasne tłumaczenie z dobrze dobranym przykładem!
Dzieki za te informacje. były kluczowe
Dobrze wyjaśnione, dzięki !