Algorytm Dijkstry

Algorytm

Algorytm Dijkstry pozwala na znalezienie najkrótszych ścieżek z pewnego wierzchołka do wszystkich z niego osiąganych. Jest to przykład algorytmu zachłannego. Wagi grafu muszą być nieujemne.

Algorytm

Algorytm Dijkstry na wejściu wymaga grafu skierowanego lub nieskierowanego o dodatnich wagach krawędzi oraz określenia, który wierzchoek jest początkowy. Na wyjściu algorytm zwróci najkrótszą odległość z punktu początkowego do dowolnego, osiągalnego wierzchołka.

Dla każdego wierzchołka przypisywane są dwie wartości: dystans oraz poprzednik. Początkowo każdy wierzchołek ma dystans nieskończony, a poprzednik jest nieznany. Wyjątkiem jest wierzchołek początkowy dla którego dystans wynosi 0.

Dalszy etap polega na utworzeniu kolejki wszystkich wierzchołków. Nastpnie dopóki kolejka nie jest pusta należy usunąć wierzchołek o najmniejszym kluczu dystansie i zbadać dla niego wszystkie połączone wierzchołki. Jeśli połączenie z wybranego wierzchołka do sąsiada ma łącznie mniejszą wartość niż docelowy wierzchołek to należy zaktualizować dystans oraz sąsiada.

Przykład

Dany jest następujący graf:

Punktem początkowym jest zaznaczony punkt A. W tabeli została przedstawiona aktualna kolejka oraz właściwości poszczególnych obiektów:

Na podstawie uzyskanych wyników można zauważyć, że najkrótsza trasa z A do B nie jest bezpośrednia, a przez wierzchołki E i C. Graf najkrótszych ścieżek z wierzchołka A wygląda następująco:

Implementacja

Założenia

Poniżej zostanie przedstawiony kod implementacji algorytmu Dijkstry oparty o tablicę. Nie jest to rozwiązanie optymalne, ponieważ szukanie minimalnej wartości w pętli jest liniowe O(n) przez co algorytm ostatecznie uzyskuje złożoność kwadratową O(n²). Dla n wierzchołków należy określić macierz n×n, gdzie na pozycji (i, j) znajduje się waga krawędzi łączącej wierzchołki i oraz j.

Oto przykładowy graf i jego reprezentacja macierzowa, którą będzie akceptować funkcja.

Graf

Reprezentacja Macierzowa

Przygotowanie

Dane dotyczące dystansu do wierzchołka, poprzednika oraz czy został już odwiedzony będą przechowywane w specjalnej strukturze danych.

1. struct dane {
2.   int dystans;
3.   int poprzednik;
4.   bool odwiedzony;
5. };

Do prawidłowego działania programu potrzebna jest funkcja szukajMinimum(), która potrafi znaleźć dla następnej iteracji element, który ma najkrótszy dystans. Jest to substyt kolejki priorytetowej. Wynikiem działania funkcji jest numer wierzchołka, który należy wybrać.

1. int szukajMinimum(int n, dane* tab) {
2.   int min = -1;
3.   int mindist = INT_MAX;
4.   for (int i = 0; i < n; i++) {
5.     if (!tab[i].odwiedzony && tab[i].dystans < mindist) {
6.       min = i;
7.       mindist = tab[i].dystans;
8.     }
9.   }
10.   return min;
11. }

Algorytm

Główna funkcja Dijkstra() wymaga podania dwóch argumentów: macierz czyli zapis informacji o poszczególnych krawędziach oraz start - wierzchołek początkowy.

1. dane* Dijkstra(int** macierz, int n, int start) {
2.   dane* tab = new dane[n];
3.   for (int i = 0; i < n; i++) {
4.     tab[i].dystans = (i == start) ? 0 : INT_MAX;
5.     tab[i].odwiedzony = false;
6.     tab[i].poprzednik = -1;
7.   }
8.   int u = szukajMinimum(n, tab);
9.   while (u != -1) {
10.     tab[u].odwiedzony = true;
11.     for (int i = 0; i < n; i++) {
12.       if (macierz[u][i] > 0 && tab[u].dystans + macierz[u][i] < tab[i].dystans) {
13.         tab[i].dystans = tab[u].dystans + macierz[u][i];
14.         tab[i].poprzednik = u;
15.       }
16.     }
17.     u = szukajMinimum(n, tab);
18.   }
19.   return tab;
20. }

(2.) Zadeklaruj nową tablicę, a następnie (3. - 7.) wypełnij ją wartościami początkowymi. (8.) Poszukiwanie rozpocznij od wyróżnionego wierzchołka start. Następnie (9.) w pętli: (10.) odznacz, że aktualny u-ty element został odwiedzony i (11. - 16.) odpowiednio zaktualizuj jego sąsiadów. Na koniec (17.) wyszukaj następny wierzchołek o najmniejszym dystansie, który nie został odwiedzony. Na koniec (19.) zwróć wyliczoną tablicę.

Testowanie funkcji

Program można przetestować przy pomocy poniższego fragmentu kodu:

1. int main() {
2.   int n, s;
3.   cout << "Ile wierzcholkow ma graf?\n n = ";
4.   cin >> n;
5.   cout << "Podaj wierzcholek poczatkowy\n s = ";
6.   cin >> s;
7.   cout << "Podaj macierz:" << endl;
8.   int** macierz = new int*[n];
9.   for (int i = 0; i < n; i++) {
10.     macierz[i] = new int[n];
11.     for (int j = 0; j < n; j++)
12.       cin >> macierz[i][j];
13.   }
14.   dane* tab = Dijkstra(macierz, n, s);
15.   cout << "Wezel\tPoprz.\tDystans" << endl;
16.   for (int i = 0; i < n; i++)
17.     wypiszdane(i, tab[i]);
18.   system("pause");
19.   return 0;
20. }

Do wyświetlania zawrtych w tablicy służy funkcja wypiszDane() przedstawiona poniżej:

1. void wypiszdane(int i, dane d) {
2.   cout << i << "\t";
3.   if (!d.odwiedzony) {
4.     cout << "nieodwiedzony";
5.   } else {
6.     if (d.poprzednik == -1)
7.       cout << "brak";
8.     else cout << d.poprzednik;
9.     cout << "\t" << d.dystans;
10.   }
11.   cout << endl;
12. }

• Kod źródłowy Implementacja