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
Dzieki za rozjasnienie zagadnienia upsert. wlasnie sie ucze programowania :).
Co się stanie gdy spróbuję wyszukać:
SELECT * FROM NV_Airport WHERE Code='SVO'
SELECT * FROM V_Airport WHERE Code=N'SVO'
(odwrotnie są te N-ki)
Będzie konwersja czy nie znajdzie żadnego rekordu?