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 const int INF = 1000000;
public int[,] Graph { get; set; }
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:
{
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:
Rys 1. Przykładowy graf wejściowy algorytmu Dijkstry.
A teraz popatrzmy na przykład użycia:
{
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.
Komentarze: