Najduži put u DAG-u (DP + topološko sortiranje)


U usmerenim acikličnim grafovima (DAG) možemo efikasno pronaći najduži put (maksimalan broj grana ili maksimalnu ukupnu težinu) koristeći kombinaciju topološkog sortiranja i dinamičkog programiranja.

Topološko sortiranje nam daje redosled u kome čvorove možemo obrađivati, a dinamičko programiranje čuva najbolji rezultat za svaku tačku obrade.

Za razliku od opštih usmerenih grafova, gde je problem najdužeg prostog puta težak i ne može se rešiti ovim jednostavnim pristupom, u DAG-u ovaj problem rešavamo u linearnom vremenu.

To je jedna od najlepših primena topološkog reda: čvorove obrađujemo tek kada su svi njihovi prethodnici već spremni.


DAG graf pre i posle topološkog sortiranja sa prikazanim topološkim redosledom čvorova
Topološko sortiranje ne menja graf, već pronalazi redosled u kome svaki čvor dolazi pre svojih naslednika.

Šta zapravo tražimo?


Kod problema najdužeg puta želimo da pronađemo putanju koja ima najveću ukupnu dužinu.

U zavisnosti od zadatka, možemo tražiti najduži put iz unapred zadatog početnog čvora ili najduži put u celom DAG grafu.

Dužina može da znači:

  • broj grana na putu (neuteženi graf)
  • zbir težina grana (težinski graf)

Na primer, u sledećem DAG grafu: 


0 → 1 → 3
 \   ↘
  ↘   2 → 4 → 5

Postoji više mogućih puteva od čvora 0: 


0 → 1 → 3
0 → 1 → 2 → 4
0 → 1 → 2 → 4 → 5

Od svih njih zanima nas onaj koji je najduži.

Važno:

Kod DAG grafova možemo efikasno pronaći najduži put jer ne postoje ciklusi koji bi omogućili beskonačno produžavanje putanje.

U praksi se ovaj problem pojavljuje kada želimo da odredimo:

  • najduži lanac zavisnosti između zadataka
  • minimalno vreme završetka projekta
  • najduži sled kurseva sa preduslovima
  • najduži niz operacija u procesu proizvodnje

DAG graf sa označenim najdužim putem od čvora 0 do čvora 5
Primer DAG grafa u kome se najduži put može pronaći pomoću topološkog sortiranja i DP-a.

Osnovna ideja algoritma


Kod DAG-a ne moramo da se vraćamo unazad niti da pokušavamo sve puteve. Dovoljno je da čvorove uredimo tako da svaki čvor dolazi pre svojih naslednika. Taj redosled dobijamo topološkim sortiranjem.

Zatim definišemo DP niz: 


dp[v]

gde dp[v] predstavlja dužinu najdužeg puta koji se završava u čvoru v, posmatrano u topološkom redosledu.

Ako postoji grana u -> v, onda možemo da pređemo iz u u v i dobijemo: 


dp[v] = max(dp[v], dp[u] + w(u, v))

gde je w(u, v) težina grane. Ako je graf neutežen, onda je w(u, v) = 1.

Važna intuicija:

Topološki red garantuje da kada obrađujemo čvor u, svi putevi koji ulaze u u već su bili obrađeni. Zato je jedna prolazna DP obrada dovoljna.

Korak po korak ažuriranje dp niza u DAG grafu
DP vrednosti se propagiraju duž grana u topološkom redosledu.

Dve varijante problema


Važno je razlikovati dve česte verzije zadatka.

1. Najduži put u celom DAG-u — početni čvor nije unapred zadat. 2. Najduži put iz zadatog startnog čvora — traži se put koji kreće iz jedne tačno određene tačke.

U prvoj varijanti obično računamo najduži put koji se završava u svakom čvoru i na kraju uzimamo maksimum. U drugoj varijanti startni čvor inicijalizujemo sa nulom, a ostale čvorove sa veoma malom vrednošću.

Kod neuteženog DAG-a to znači: 


dp[start] = 0

dok su svi ostali čvorovi inicijalno nedostižni.



Primer neuteženog DAG-a



0 → 1 → 3
 \   ↘   ↘
  ↘   2 → 4 → 5

Jedan najduži put je:

0 → 1 → 2 → 4 → 5

Dužina puta je 4, jer sadrži četiri grane.

Ovde nije bitno samo pronaći bilo koji put, već onaj sa najvećim brojem grana.



Implementacija: neuteženi DAG



#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    // --------------------------------------------------------
    // Graf i ulazni stepeni čvorova
    // --------------------------------------------------------
    //
    // g[u] = lista svih čvorova do kojih postoji grana u -> v
    // indeg[v] = broj ulaznih grana u v
    //
    // Ovaj niz nam treba za Kahn-ov algoritam.
    // --------------------------------------------------------

    vector<vector<int>> g(n);
    vector<int> indeg(n, 0);

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;   // grana a -> b
        g[a].push_back(b);
        indeg[b]++;
    }

    // --------------------------------------------------------
    // Kahn-ov algoritam za topološko sortiranje
    // --------------------------------------------------------
    //
    // U red stavljamo sve čvorove sa indeg = 0.
    // To su čvorovi koji nemaju prethodnike.
    // --------------------------------------------------------

    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (indeg[i] == 0)
            q.push(i);
    }

    vector<int> topo;

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        topo.push_back(u);

        // Uklanjamo sve grane iz u
        for (int v : g[u]) {
            indeg[v]--;
            if (indeg[v] == 0)
                q.push(v);
        }
    }

    // --------------------------------------------------------
    // Ako nismo obradili sve čvorove,
    // graf nije DAG.
    // Ovaj algoritam je namenjen samo DAG-u.
    // --------------------------------------------------------

    if ((int)topo.size() != n) {
        cout << "Graf nije DAG, pa ovaj algoritam nije primenljiv.\n";
        return 0;
    }

    // --------------------------------------------------------
    // DP:
    // dp[v] = dužina najdužeg puta koji se završava u v
    // --------------------------------------------------------
    //
    // Pošto je graf neutežen, svaki prelaz dodaje 1.
    // Inicijalno svi čvorovi mogu da budu početak puta,
    // pa krećemo od 0.
    // --------------------------------------------------------

    vector<int> dp(n, 0);
    vector<int> parent(n, -1);

    for (int u : topo) {
        for (int v : g[u]) {
            if (dp[v] < dp[u] + 1) {
                dp[v] = dp[u] + 1;
                parent[v] = u;
            }
        }
    }

    // --------------------------------------------------------
    // Tražimo najveću vrednost dp[n]
    // --------------------------------------------------------

    int end = 0;
    for (int i = 1; i < n; i++) {
        if (dp[i] > dp[end])
            end = i;
    }

    cout << "Najduzi put u DAG-u je: " << dp[end] << "\n";

    // --------------------------------------------------------
    // Rekonstrukcija puta
    // --------------------------------------------------------

    vector<int> path;
    for (int x = end; x != -1; x = parent[x]) {
        path.push_back(x);
    }
    reverse(path.begin(), path.end());

    cout << "Putanja: ";
    for (int x : path) cout << x << " ";
    cout << "\n";

    return 0;
}

Napomena:

Ova varijanta računa najduži put u celom DAG-u. Ako želiš najduži put iz jednog konkretnog startnog čvora, inicijalizacija je malo drugačija.


Primer sa težinama



0 -5→ 1 -2→ 3
 \    ↘
  3     7
   ↘     ↘
    2 -1→ 4 -4→ 5

U težinskoj varijanti cilj je pronaći put sa najvećom ukupnom sumom težina.

Važna činjenica:

Negativne težine nisu problem za ovaj algoritam, jer graf nema cikluse. To je potpuno drugačije od najkraćeg puta, gde negativne težine mogu biti problem.

Ako postoji startni čvor, onda koristimo: 


dp[start] = 0

a sve ostale čvorove inicijalizujemo kao nedostižne.



Implementacija: najduži put iz zadatog startnog čvora



#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const ll NEG_INF = -(1LL << 60);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, start;
    cin >> n >> m >> start;

    // --------------------------------------------------------
    // Težinski graf: g[u] sadrži parove (v, w)
    // gde je w težina grane u -> v
    // --------------------------------------------------------

    vector<vector<pair<int,int>>> g(n);
    vector<int> indeg(n, 0);

    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        g[a].push_back({b, w});
        indeg[b]++;
    }

    // --------------------------------------------------------
    // Kahn-ov algoritam
    // --------------------------------------------------------

    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (indeg[i] == 0)
            q.push(i);
    }

    vector<int> topo;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topo.push_back(u);

        for (auto [v, w] : g[u]) {
            indeg[v]--;
            if (indeg[v] == 0)
                q.push(v);
        }
    }

    if ((int)topo.size() != n) {
        cout << "Graf nije DAG.\n";
        return 0;
    }

    // --------------------------------------------------------
    // DP za startni čvor
    // --------------------------------------------------------
    //
    // start je jedini čvor sa vrednošću 0.
    // Ostali su nedostižni dok ih ne poboljšamo.
    // --------------------------------------------------------

    vector<ll> dp(n, NEG_INF);
    vector<int> parent(n, -1);

    dp[start] = 0;

    for (int u : topo) {
        if (dp[u] == NEG_INF) continue;

        for (auto [v, w] : g[u]) {
            if (dp[v] < dp[u] + w) {
                dp[v] = dp[u] + w;
                parent[v] = u;
            }
        }
    }

    // --------------------------------------------------------
    // Najveći rezultat od svih dostižnih čvorova
    // --------------------------------------------------------

    int end = start;
    for (int i = 0; i < n; i++) {
        if (dp[i] > dp[end])
            end = i;
    }

    cout << "Maksimalna suma: " << dp[end] << "\n";

    // --------------------------------------------------------
    // Rekonstrukcija puta
    // --------------------------------------------------------

    vector<int> path;
    for (int x = end; x != -1; x = parent[x]) {
        path.push_back(x);
    }
    reverse(path.begin(), path.end());

    cout << "Putanja: ";
    for (int x : path) cout << x << " ";
    cout << "\n";

    return 0;
}

Kako rekonstruišemo najduži put?


Do sada smo naučili kako da izračunamo dužinu najdužeg puta u DAG grafu. Međutim, u praksi često želimo i da saznamo koji čvorovi čine taj put.

Zbog toga pored niza dp uvodimo i dodatni niz: 


parent[v]

Niz parent pamti odakle smo došli do čvora v kada smo pronašli trenutno najbolji put.

Drugim rečima: 


parent[v] = prethodni čvor na najboljem putu do v

Kada tokom relaksacije pronađemo bolji put do nekog čvora, ažuriramo i dp i parent. 


if (dp[v] + 1 > dp[to]) {
    dp[to] = dp[v] + 1;
    parent[to] = v;
}
Važna ideja:

dp čuva dužinu najboljeg puta, a parent čuva informaciju kako da taj put vratimo nazad.

Na primer, ako nakon završetka algoritma dobijemo: 


parent[1] = 0
parent[2] = 1
parent[3] = 1
parent[4] = 2
parent[5] = 4

i ako je čvor 5 kraj najdužeg puta, onda rekonstrukciju radimo tako što krećemo od njega i pratimo parent pokazivače unazad: 


5 → 4 → 2 → 1 → 0

Pošto je put dobijen unazad, na kraju samo obrnemo redosled: 


0 → 1 → 2 → 4 → 5

Tako dobijamo konkretan najduži put, a ne samo njegovu dužinu.

Povratak kroz parent pokazivače od krajnjeg do početnog čvora u DAG grafu
Parent niz omogućava rekonstrukciju konkretnog najdužeg puta nakon završetka DP algoritma.
Kada je parent niz potreban?

Ako zadatak traži samo dužinu puta, dovoljan je dp niz. Ako zadatak traži i ispis samog puta, potreban je i parent niz.

Zbog toga se u grafovskim DP zadacima često koristi obrazac: 


dp[]      → najbolji rezultat
parent[]  → rekonstrukcija rešenja

Ovaj isti princip se često koristi i u drugim algoritmima, na primer kada želimo da rekonstruišemo put nakon Dijkstrinog algoritma.



Objašnjenje varijante sa težinama(weithed)

Ovde je ideja ista, samo svaka grana ima svoju težinu. Pošto graf nema cikluse, negativne težine ne predstavljaju problem.

Kada obradimo čvor u topološkom redosledu, svi njegovi prethodnici su već obrađeni, pa svaki pokušaj relaksacije dolazi u pravom trenutku.

Važno:

Za najduži put u DAG-u ne koristimo Dijkstru. Dijkstra je algoritam za najkraći put, i to pod posebnim uslovima. Ovde nam je potreban DAG + topološki red + DP.


Kako vratiti konkretan put?


Ako želimo samo dužinu najdužeg puta, dovoljno je da pratimo DP vrednosti. Ali ako želimo i samu putanju, čuvamo roditelja čvora iz kog smo poslednji put poboljšali vrednost.

Ideja:

Kad god dp[v] postane veći, pamtimo parent[v] = u. Na kraju krećemo od krajnjeg čvora unazad i dobijamo ceo put.

To je standardna tehnika rekonstrukcije u DP problemima.



Česte greške i zamke


Jedna od najčešćih grešaka je pokušaj da se najduži put traži i u grafu koji ima ciklus. Tada ovaj jednostavan algoritam više nije dovoljan.

Druga česta greška je pokretanje DP-a bez topološkog poretka. Tada možemo obraditi čvor pre nego što su svi njegovi prethodnici spremni, pa rezultat postaje netačan.

Savet:

Ako graf nije DAG, prvo moraš da rešiš problem ciklusa ili da koristiš potpuno drugačiji pristup.


Zadaci za vežbu


Dobro je da prvo probaš najduži put iz zadatog startnog čvora, a zatim varijantu u kojoj se traži globalni maksimum u celom DAG-u. To su dve najčešće forme ovog zadatka.

Posle toga, zanimljivo je rešavati i probleme koji modeluju:

kritični put u projektu, trajanja aktivnosti, zavisnosti zadataka i maksimalnu zaradu kroz DAG.

Poređenje DAG grafa i usmerenog grafa sa ciklusom
DP po topološkom poretku funkcioniše samo u DAG grafovima bez ciklusa.

Zaključak


Najduži put u DAG-u je veoma lep primer kako se topološko sortiranje i dinamičko programiranje savršeno dopunjuju.

Topološki red daje pravilan poredak obrade, a DP čuva najbolji rezultat za svaki čvor. Zbog toga ceo problem možemo rešiti linearno, bez proveravanja svih mogućih puteva.

Suština:

U DAG-u se najduži put ne traži silom kroz sve puteve, već pametnim redosledom obrade.

Infografik koji prikazuje DAG graf sa označenim najdužim putem pomoću topološkog sortiranja i dinamičkog programiranja. Gornji deo prikazuje originalni usmereni aciklični graf sa više mogućih puteva, dok donji deo prikazuje topološki poredak čvorova i izračunavanje DP vrednosti. Najduži put je označen zelenom bojom, a kraći alternativni put crvenom bojom.
Slika 1: Vizuelni prikaz algoritma za pronalaženje najdužeg puta u DAG grafu pomoću topološkog sortiranja i dinamičkog programiranja. Zelenom bojom označen je najduži put, dok je crvenom prikazan kraći put radi poređenja. Donji deo slike prikazuje topološki redosled obrade čvorova i propagaciju DP vrednosti kroz graf.

Zadaci za samostalno rešavanje


Zadatak 1: Najduži put iz startnog čvora


Dat je usmereni aciklični graf (DAG) sa N čvorova i M grana. Svaka grana ima pozitivnu težinu.

Za dati početni čvor S potrebno je odrediti maksimalnu moguću sumu težina puta koji polazi iz tog čvora. Takođe, treba ispisati i jednu konkretnu najdužu putanju.

Ako postoji više najdužih putanja, dovoljno je ispisati bilo koju od njih.

Važno:

Graf je DAG, što znači da nema cikluse. Zato možemo koristiti topološko sortiranje i dinamičko programiranje.

Zadatak 2: Najduži put u celom DAG-u


Dat je usmereni aciklični graf (DAG) sa N čvorova i M grana. Svaka grana ima težinu.

Potrebno je pronaći dužinu najdužeg puta u celom grafu, odnosno puta koji može da počne i završi u bilo kojim čvorovima.

Dovoljno je ispisati samo dužinu najdužeg puta, bez same putanje.

Napomena:

Ovde startni čvor nije unapred zadat. Zato svaki čvor može biti potencijalni početak puta.

Zadatak 3: Kritični put u projektu


Veliki projekat sastoji se od N aktivnosti. Svaka aktivnost ima određeno trajanje i može da počne tek kada se završe sve aktivnosti od kojih zavisi.

Zavisnosti između aktivnosti formiraju usmeren aciklični graf (DAG), jer nije moguće da aktivnost indirektno zavisi sama od sebe.

Potrebno je odrediti:

Kritični put predstavlja niz aktivnosti čije ukupno trajanje određuje ukupno trajanje projekta.


Zadatak 4: Maksimalna zarada kroz mrežu gradova


Dato je N gradova povezanih jednosmernim putevima. Svaki grad ima određenu zaradu koju možemo ostvariti ako ga posetimo.

Dozvoljeno je kretanje samo u smeru puteva, a graf je garantovano DAG.

Potrebno je odrediti:

Kada posetimo grad, njegovu zaradu možemo uzeti samo jednom.