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. class dane(object):
2.   def __init__(self, v, p, d):
3.     self.odwiedzony = v
4.     self.poprzednik = p
5.     self.dystans = d

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. def szukajMinimum(tab):
2.   min = -1
3.   mindist = sys.maxsize
4.   for i in range(0, len(macierz)):
5.     if ((not tab[i].odwiedzony) and tab[i].dystans < mindist):
6.       min = i
7.       mindist = tab[i].dystans
8.   return min

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. def Dijkstra(macierz, start):
2.   tab = []
3.   for i in range(0, len(macierz)):
4.     tab.append(dane(False, -1, sys.maxsize))
5.   tab[start].dystans = 0
6.   u = start
7.   while(u != -1):
8.     tab[u].odwiedzony = True
9.     for i in range(0, len(macierz)):
10.       if (macierz[u][i] > 0 and tab[u].dystans + macierz[u][i] < tab[i].dystans):
11.         tab[i].dystans = tab[u].dystans + macierz[u][i]
12.         tab[i].poprzednik = u
13.     u = szukajMinimum(tab)
14.   return tab

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

Testowanie funkcji

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

1. n = int(input('Podaj ile węzłów ma graf\n n = '))
2. s = int(input('Podaj węzeł startowy\n s = '))
3. print('Podaj elementy macierzy:')
4. macierz = []
5. for i in range(0, n):
6.   tab = [int(x) for x in input().split()]
7.   macierz.append(tab)
8.  
9. tab = Dijkstra(macierz, s)
10. for i in range(0, n):
11.   wypiszDane(i, tab[i])

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

1. def wypiszDane(i, d):
2.   txt = str(i) + "\t"
3.   if (not d.odwiedzony):
4.     txt += "nieodwiedzony"
5.   else:
6.     if (d.poprzednik == -1):
7.       txt += "brak"
8.     else:
9.       txt += str(d.poprzednik)
10.     txt += "\t" + str(d.dystans)
11.   print(txt);

• Kod źródłowy Implementacja