---
title: L1Z5 AISD
---

## Algorytmy i struktury danych
### Lista 1, zadanie 5

==Marek Padlewski, 299778==

:::info
Ułóż algorytm, który dla zadanego acyklicznego grafu skierowanego $G$ znajduje długość najdłuższej drogi w $G$. Następnie zmodyfikuj swój algorytm tak, by wypisywał drogi o największej długości (jeśli jest kilka takich dróg, to Twój algorytm powinien wypisać dowolną z nich).
:::

#### Idea
1. Wykonajmy sortowanie topologiczne grafu $G$. Wynik sorotwania zapiszmy w tablicy `T[]`.
2. Stwórzmy tablicę `D[]` w której dla każdego wierzchołka $v \in G$ będziemy przechowywać wartość równą aktualnie najdłuższej drodze do $v$. Na początku wartości te będą równe zero.
3. Przejdźmy tablicę `T[]` i dla każdego wierzchołka $v$, przechodząc po wszystkich $u$, gdzie $u$ należy do zbioru wierzchołków, do których istnieje krawędź wychodząca z $v$, aktualizujmy wartość zamieszczoną w `D[u]`. $D[u] = max(D[u], D[v] + 1)$. Jako że bierzemy zawsze maksimum z wpisanej wcześniej wartości lub z wartości powstałej poprzez dodanie 1 do wartości znajdującej się w poprzednim wierzchołku na drodze, da nam to na koniec maksymalną możliwą drogę.
4. Przejdźmy po tablicy `D[]` i wypiszmy $max(D[i])$, czyli naszą długość drogi o największej długości.

##### Algorytm

int findMaxLength(){
    unsigned int n = number_of_vertices;
    T[n] = topological_sort(G);
    int D[n];

    //ustawiamy początkową wartość w D[] na 0
    for (int i = 0 ; i < n ; i++)
        D[i] = 0;
    
    for (auto v : T){
        for (auto u : neighbours[v]){
            D[u] = max(D[u], D[v] + 1);
        }
    }

    int result = 0;
    for (auto value : D)
        result = max(result, value);
    
    return result;
}

#### Modyfikacja
1. Zamiast przechowywać w tablicy `D[]` jedynie wartości aktualnie najdłuższej drogi wchodzącej do danego wierzchołka, możemy przechowywać parę `p`, w której `p.first` będzie równy aktualnie najdłuższej drodze do $v$, a `p.second` będzie równy $id$ wierzchołka z którego przyszliśmy do $v$. Na początku wartości `p.first` będą równe zero.
2. Następnie wystarczy zaczynając od wierzchołka z największą zapisaną długością drogi, odwzorować kolejne kroki, przechodząc od jednego wierzchołka do drugiego.

##### Algorytm zmodyfikowany

void find(){
    unsigned int n = number_of_vertices;
    T[n] = topological_sort(G);
    int D[n];

    //ustawiamy początkową wartość w D[] na 0
    for (int i = 0 ; i < n ; i++)
        D[i].first = 0;
    
    for (auto v : T){
        for (auto u : neighbours[v]){
            if (v.first + 1 > u.first){
                u.first = v.first + 1;
                u.second = v; 
                //przypisujemy id wierzchołka v
            }
        }
    }

    int result = 0;
    for (auto value : D)
        result = max(result, value);
    
    for (int i = 0 ; i < n ; i++){
        if(D[i].first == result){
            //wywołujemy funkcję wypisującą drogę
            //od wierzchołka z największą wartością
            print(i);
            break;
        }
    }
}

void print(int i){
    if (D[i].second == null)
        //gdy dojdziemy do końca drogi
        std::cout << i << " ";
    else
        //wypisanie drogi w odpowiedniej kolejności
        std::cout << print(D[i].second) << " " << i;
        
}

#### Złożonośc czasowa
* Sortowanie topologiczne: $O(n + m)$
* Przejście po wszystkich wierzchołkach i ich sąsiadach: $O(n + m)$
* Przejście po tablicy `D[]` w poszukiwaniu wyniku oraz wypisanie drogi: $O(n)$

#### Złożonośc pamięciowa
* Wszystkie tablice są rozmiaru adekwatnego do liczby wierzchołków w $G$, tak więc: $O(n)$