Informatyka MIMUW

W tej implementacji wszystkie struktury danych są tablicami. Przyjmujemy, że graf jest zadany przez macierz sąsiedztwa \( A[1..n,1..n] \). Zbiór \( R \) jest rerezentowany za pomocą tablicy (wektora charakterystycznego) \( r[1,\ldots,n] \) o wartościach 0-1:

Tablica \( w[1..n] \) służy do obliczania wag najlżejszych ścieżek. Oznaczmy przez \( MinR \) funkcję, której wartością jest wierzchołek w R o najmniejszej wadze \( w \). Jeśli jest więcej niż jeden taki wierzchołek, to wynikiem funkcji może być dowolny z nich. Oto jedna z możliwych implementacji tej funkcji.

function MinR; 
begin 
    min := 0; 
    for i := 1 to n do 
        if  w[i]  <  min then min_v := i; 
    return min_v  
end

Czas działania tej funkcji wynosi \( O(n) \).
Możemy teraz przedstawić pierwszą implementację metody Dijkstry.

Algorytm Metoda Dijkstry - implementacja tablicowa

//Inicjacja 
for v := 1 to n do 
begin 
    r[v] := 1; 
    w[v] := A[v,s]  
end; 
r[s] := 0; 
//właściwe obliczenia 
for i := 1 to n-1 do 
begin
    u := MinR; 
    r[u] := 0; 
    for v := 1 to n do if r[v] = 1 then 
        if w[u] + A[u,v]  <  w[v] then 
            w[v] := w[u] + A[u,v]  
end; 
//dla każdego v \in V, w[v] = w*(v) 

W powyższej implementacji grupy wierszy 2-8, 12-14 oraz 15-18 odpowiadają dokładnie tym samym grupom wierszy w opisie metody Dijkstry. Analiza złożoności czasowej powyższego algorytmu nie nastręcza żadnych trudności. Inicjacja zajmuje czas \( O(n) \), każdy obrót pętli for z wiersza 10 zajmuje także czas \( O(n) \), a zatem cały algorytm działa w czasie \( \Theta(n^2) \). Dla grafów gęstych, czyli zawierających rzędu \( n^2 \) wierzchołków, jest to algorytm optymalny. Zwróćmy także uwagę na jego wyjątkowo prosty i elegancki zapis. Co jednak, gdy zadany graf nie jest grafem gęstym? Czy wówczas możemy obliczać wagi najlżejszych ścieżek szybciej?