Choose your language!

---

|

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.

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

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.

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.

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.

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.

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.

Prikaži / sakrij uputstvo

Uputstvo — kako razmišljati

Na prvi pogled može delovati da treba pokušati sve moguće puteve koji kreću iz čvora S.

Međutim, broj puteva u grafu može biti veoma velik, pa takav pristup nije dobar. Zato se oslanjamo na činjenicu da graf nema cikluse.

---

Ključna ideja

U DAG-u možemo čvorove poređati topološki, tako da svaki čvor dolazi pre svih svojih naslednika.

To nam omogućava da koristimo DP:

dp[v] = maksimalna suma težina puta od S do v

Na početku je:

dp[S] = 0

jer do startnog čvora ne prelazimo nijednu granu.

Svi ostali čvorovi su na početku nedostižni.

Intuicija:

Ako do nekog čvora još nismo pronašli validan put, njegovu vrednost držimo kao veoma malu vrednost (NEG_INF ili slično).

---

DP prelaz

Ako postoji grana:

u -> v

težine w, onda možemo pokušati poboljšanje:

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

Ako se vrednost dp[v] poboljšala, pamtimo i:

parent[v] = u

Tako kasnije možemo vratiti konkretnu putanju.

---

Kako vratiti putanju?

Kada dobijemo konačnu vrednost, krenemo od krajnjeg čvora unazad preko niza parent.

Na taj način dobijamo put u obrnutom smeru, pa ga na kraju samo obrnemo.

Ideja:

Kad god se dp[v] poboljša, pamtimo od kog čvora smo došli. Na kraju, umesto da pogađamo put, samo pratimo roditelje unazad.

---

Zašto topološki red?

Topološki red garantuje da pre obrade čvora v već znamo najbolje rezultate za sve njegove prethodnike.

Zato se DP može raditi u jednom prolazu kroz topološki sortirane čvorove.

---

Složenost

O(N + M)

Topološko sortiranje i DP zajedno rade linearno u odnosu na broj čvorova i grana.

Prikaži rešenje

⚠ Pre nego što pogledaš rešenje, pokušaj samostalno!

#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, cilj;
    cin >> n >> m >> start >> cilj;

    // --------------------------------------------------------
    // Graf:
    // g[u] = lista parova (v, w)
    // gde postoji grana u -> v težine w
    // --------------------------------------------------------

    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 za topološko sortiranje
    // --------------------------------------------------------

    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);
        }
    }

    // Ako nismo obradili sve čvorove, graf nije DAG
    if ((int)topo.size() != n) {
        cout << "Graf nije DAG.\n";
        return 0;
    }

    // --------------------------------------------------------
    // DP:
    // dp[v] = maksimalna suma težina puta od starta do v
    // --------------------------------------------------------

    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]) {
            ll kandidat = dp[u] + w;

            if (kandidat > dp[v]) {
                dp[v] = kandidat;
                parent[v] = u;
            }
        }
    }

    // Ako cilj nije dostižan
    if (dp[cilj] == NEG_INF) {
        cout << "Put ne postoji.\n";
        return 0;
    }

    cout << "Najveca tezina puta: " << dp[cilj] << "\n";

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

    vector<int> putanja;
    for (int x = cilj; x != -1; x = parent[x]) {
        putanja.push_back(x);
    }

    reverse(putanja.begin(), putanja.end());

    cout << "Putanja: ";
    for (int x : putanja) {
        cout << x << " ";
    }
    cout << "\n";

    return 0;
}

Objašnjenje rešenja

Pošto je graf DAG, možemo ga topološki sortirati. Tada svaku granu obrađujemo tek nakon što su svi čvorovi koji prethode njenom početku već spremni.

DP vrednost za čvor v predstavlja najbolju sumu puta od startnog čvora do tog čvora. Kad god pronađemo bolji put, ažuriramo i roditelja.

Na kraju dobijamo i dužinu najdužeg puta i konkretnu putanju.

Ključna ideja:

U DAG-u nema vraćanja unazad, pa je jedan prolaz kroz topološki red dovoljan da pronađemo optimalan rezultat.

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.

Prikaži / sakrij uputstvo

Uputstvo — kako razmišljati

Na prvi pogled deluje da treba pokušati sve moguće početke i sve moguće puteve. To bi bilo presporo.

Pošto je graf DAG, možemo ga obraditi pomoću topološkog reda i DP-a.

---

Ključna ideja

Definišemo:

dp[v]

kao dužinu najdužeg puta koji se završava u čvoru v.

Pošto nema unapred zadanog starta, svi čvorovi mogu da budu početak puta, pa ih inicijalno postavljamo na 0.

Intuicija:

Ako do nekog čvora još nije stigao nijedan bolji put, on može da predstavlja put dužine 0 koji počinje samo u tom čvoru.

---

DP prelaz

Za svaku granu u -> v težine w pokušavamo:

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

Kada završimo obradu svih čvorova, odgovor je:

max(dp[v]) za sve v

---

Zašto je topološki red dovoljan?

Topološki red garantuje da kada obrađujemo čvor u, sve vrednosti koje vode u u već su poznate.

Zbog toga jedan prolaz kroz čvorove dovoljan za pravilan DP.

---

Složenost

O(N + M)

Prikaži rešenje

⚠ Pre nego što pogledaš rešenje, pokušaj samostalno!

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

using ll = long long;

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

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

    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]++;
    }

    // --------------------------------------------------------
    // Topološko sortiranje
    // --------------------------------------------------------

    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:
    // dp[v] = najduža dužina puta koji se završava u v
    // --------------------------------------------------------
    //
    // Pošto nema zadatog starta,
    // svako polje može biti početak puta.
    // Zato inicijalizujemo sve vrednosti na 0.
    // --------------------------------------------------------

    vector<ll> dp(n, 0);

    for (int u : topo) {
        for (auto [v, w] : g[u]) {
            dp[v] = max(dp[v], dp[u] + w);
        }
    }

    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, dp[i]);
    }

    cout << ans << '\n';

    return 0;
}

Objašnjenje rešenja

U ovoj varijanti ne tražimo najduži put iz jednog starta, već najveći mogući put bilo gde u DAG-u. Zato svi čvorovi mogu da budu početak.

To je razlog zbog kog DP niz inicijalno punimo nulama. Tako svaki čvor predstavlja validan put dužine 0, a zatim ga po potrebi produžavamo.

Ključna razlika:

Kod zadatog starta koristimo veoma malu vrednost za nedostižne čvorove, a ovde svi čvorovi mogu da budu početak, pa je inicijalizacija sa nulama prirodna.

---

Zašto ovo radi?

Kada dođemo do čvora u, sve njegove moguće prethodne vrednosti su već obrađene u topološkom redosledu.

Zato svaka relaksacija predstavlja lokalno poboljšanje, a kroz ceo graf dobijamo globalni maksimum.

---

Zaključak

Ova varijanta je vrlo čest oblik zadatka kada se traži najduži put u celom DAG-u bez posebnog starta.

Suština ostaje ista: topološki red + DP = efikasno rešenje.

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:

• minimalno vreme završetka celog projekta
• jedan kritični put aktivnosti

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

Prikaži / sakrij uputstvo

Uputstvo — kako razmišljati

Ovaj problem je klasična primena najdužeg puta u DAG-u.

Svaka aktivnost je čvor grafa, a ako aktivnost A mora da se završi pre aktivnosti B, onda postoji grana:

A -> B

---

Ključna ideja

Neka je:

dp[v]

najranije vreme u kojem aktivnost v može da bude završena.

Ako u aktivnost v možemo da dođemo iz aktivnosti u, onda pokušavamo:

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

Koristimo maksimum zato što aktivnost v može da počne tek kada se završe sve aktivnosti od kojih zavisi.

---

Zašto topološki red?

Aktivnosti moramo obrađivati tek kada su obrađene sve njihove prethodne aktivnosti. Zato nam topološko sortiranje daje pravilan redosled obrade.

Intuicija:

Topološki red osigurava da se svaka aktivnost obrađuje tek kada su svi njeni prethodnici već poznati.

---

Kako vratiti kritični put?

Kad god poboljšamo vrednost:

dp[v]

pamtimo:

parent[v] = u

Na kraju krećemo od čvora sa najvećom DP vrednošću i vraćamo se unazad preko niza parent.

---

Složenost

O(N + M)

gde je N broj aktivnosti, a M broj zavisnosti.

Prikaži rešenje

⚠ Pre nego što pogledaš rešenje, pokušaj samostalno!

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

using ll = long long;

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

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

    /*
        duration[i]
        = trajanje aktivnosti i
    */
    vector<ll> duration(n);

    for (int i = 0; i < n; i++) {
        cin >> duration[i];
    }

    /*
        g[u] = lista aktivnosti koje zavise od aktivnosti u
    */
    vector<vector<int>> g(n);

    /*
        indeg[v] = broj prethodnika aktivnosti v
    */
    vector<int> indeg(n, 0);

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;

        g[u].push_back(v);
        indeg[v]++;
    }

    /*
        Kahn-ov algoritam za topološko sortiranje
    */
    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 (int v : g[u]) {
            indeg[v]--;
            if (indeg[v] == 0) {
                q.push(v);
            }
        }
    }

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

    /*
        dp[v]
        = najranije vreme završetka aktivnosti v
    */
    vector<ll> dp(n, 0);

    /*
        parent[v]
        = prethodna aktivnost na kritičnom putu
    */
    vector<int> parent(n, -1);

    /*
        Aktivnosti bez prethodnika mogu da krenu odmah,
        pa im je vreme završetka jednako njihovom trajanju.
    */
    for (int i = 0; i < n; i++) {
        if (indeg[i] == 0) {
            dp[i] = duration[i];
        }
    }

    /*
        DP po topološkom redosledu
    */
    for (int u : topo) {
        for (int v : g[u]) {
            if (dp[v] < dp[u] + duration[v]) {
                dp[v] = dp[u] + duration[v];
                parent[v] = u;
            }
        }
    }

    /*
        Nalazimo kraj kritičnog puta
    */
    int endNode = 0;
    for (int i = 1; i < n; i++) {
        if (dp[i] > dp[endNode]) {
            endNode = i;
        }
    }

    cout << "Minimalno vreme projekta: " << dp[endNode] << "\n";

    /*
        Rekonstrukcija kritičnog puta
    */
    vector<int> path;
    for (int x = endNode; x != -1; x = parent[x]) {
        path.push_back(x);
    }

    reverse(path.begin(), path.end());

    cout << "Kriticni put:\n";
    for (int x : path) {
        cout << x << " ";
    }
    cout << "\n";

    return 0;
}

Objašnjenje rešenja

Graf aktivnosti je DAG, pa možemo da primenimo topološko sortiranje.

Zatim za svaku aktivnost računamo najranije vreme završetka, uzimajući maksimum preko svih prethodnika.

Kada se neka vrednost poboljša, pamtimo i roditelja, kako bismo kasnije mogli da vratimo konkretan kritični put.

Suština:

Kritični put je zapravo najduži put u DAG-u, gde težine čvorova predstavljaju trajanja aktivnosti.

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:

• maksimalnu moguću zaradu
• jedan optimalan put

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

Prikaži / sakrij uputstvo

Uputstvo — kako razmišljati

Ovo je još jedna varijanta najdužeg puta u DAG-u, samo što ovde težine nisu na granama, već predstavljaju zaradu čvorova.

Za svaku lokaciju želimo da znamo koliku najveću zaradu možemo ostvariti kada stignemo do nje.

---

Ključna ideja

Neka je:

dp[v]

maksimalna zarada koju možemo imati kada stignemo u grad v.

Ako postoji put:

u -> v

onda pokušavamo:

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

---

Zašto koristimo veoma malu vrednost?

Na početku većina čvorova još nije dostupna. Zato ih inicijalizujemo kao nedostižne:

dp[i] = -INF

To znači da još nismo pronašli nijedan validan put do tih čvorova.

Intuicija:

Čvor sa vrednošću -INF još nije deo nijedne pronađene putanje. Tek kada stignemo do njega, njegova vrednost postaje validna.

---

Kako se dobija odgovor?

Kada obradimo sve čvorove u topološkom redosledu, najveća vrednost u dp predstavlja maksimalnu zaradu.

Ako želimo i optimalan put, čuvamo i:

parent[v]

Svaki put kada poboljšamo dp[v], pamtimo iz kog čvora smo došli.

---

Složenost

O(N + M)

gde je N broj gradova, a M broj puteva.

Prikaži rešenje

⚠ Obrati pažnju na inicijalizaciju DP niza.

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

using ll = long long;

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

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

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

    /*
        value[i]
        = zarada u gradu i
    */
    vector<ll> value(n);

    for (int i = 0; i < n; i++) {
        cin >> value[i];
    }

    /*
        g[u] = lista gradova do kojih možemo stići iz u
    */
    vector<vector<int>> g(n);
    vector<int> indeg(n, 0);

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;

        g[u].push_back(v);
        indeg[v]++;
    }

    /*
        Topološko sortiranje
    */
    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 (int v : g[u]) {
            indeg[v]--;
            if (indeg[v] == 0) {
                q.push(v);
            }
        }
    }

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

    /*
        dp[v]
        = maksimalna zarada do grada v
    */
    vector<ll> dp(n, NEG);

    /*
        parent[v]
        = prethodni grad na najboljoj putanji
    */
    vector<int> parent(n, -1);

    /*
        Čvorovi bez prethodnika mogu biti početak puta.
    */
    for (int u : topo) {
        if (dp[u] == NEG) {
            dp[u] = value[u];
        }

        for (int v : g[u]) {
            if (dp[u] == NEG) continue;

            ll kandidat = dp[u] + value[v];

            if (kandidat > dp[v]) {
                dp[v] = kandidat;
                parent[v] = u;
            }
        }
    }

    /*
        Najbolji završni grad
    */
    int endNode = 0;
    for (int i = 1; i < n; i++) {
        if (dp[i] > dp[endNode]) {
            endNode = i;
        }
    }

    cout << "Maksimalna zarada: " << dp[endNode] << "\n";

    /*
        Rekonstrukcija puta
    */
    vector<int> path;
    for (int x = endNode; x != -1; x = parent[x]) {
        path.push_back(x);
    }

    reverse(path.begin(), path.end());

    cout << "Optimalan put:\n";
    for (int x : path) {
        cout << x << " ";
    }
    cout << "\n";

    return 0;
}

Objašnjenje rešenja

Ovde najduži put ne predstavlja broj grana, već maksimalnu sumu zarada koju možemo prikupiti kroz čvorove.

Zato DP vrednosti čuvaju najbolju zaradu koja se može ostvariti do svakog grada.

Kada pronađemo bolji prelaz, ažuriramo i roditelja, kako bismo kasnije mogli da vratimo optimalan put.

Ključna ideja:

Topološki red omogućava da svaki grad obradimo tek kada su svi njegovi prethodnici već poznati, pa je DP obrada u jednom prolazu dovoljna.

Sledeća preporučena lekcija:

Dijkstra — najkraći put

Povezane teme i preporučene lekcije

Ako želiš potpuno da savladaš rad sa DAG grafovima, topološkim sortiranjem i dinamičkim programiranjem nad grafovima, preporučuje se da prođeš i sledeće lekcije.

Preporučeni redosled:

1. Topološko sortiranje
2. Detekcija ciklusa u DAG-u
3. SCC komponente (Kosaraju / Tarjan)
4. Najduži put u DAG-u
5. Najkraći putevi (Dijkstra)

Topološko sortiranje

Osnovna tehnika za obradu DAG grafova. Bez topološkog poretka nije moguće pravilno raditi DP nad DAG-om.

Šta ćeš naučiti:

Kahn algoritam, DFS topološko sortiranje, detekciju ciklusa i pravilno procesiranje zavisnosti.

Topološko sortiranje

---

DAG i detekcija ciklusa

Pre nego što pokreneš DP nad grafom, moraš biti siguran da graf nema ciklus.

U ovoj lekciji obrađuje se:

• šta je DAG
• zašto ciklusi prave problem
• detekcija ciklusa pomoću DFS-a
• detekcija ciklusa pomoću Kahn algoritma

DAG i detekcija ciklusa

---

SCC komponente — Kosaraju i Tarjan

Ako graf sadrži cikluse, često ih prvo sabijamo u SCC komponente kako bismo dobili DAG nad komponentama.

Važna ideja:

Mnogi teški problemi nad opštim grafovima postaju mnogo jednostavniji kada se ciklusi sabiju u SCC komponente.

SCC komponente — Kosaraju i Tarjan algoritam

---

Dijkstra — najkraći put

Najduži put u DAG-u i Dijkstra algoritam često se porede, jer oba koriste relaksaciju grana i DP ideju, ali rešavaju različite probleme.

Kod Dijkstre tražimo:

minimum

dok kod najdužeg puta u DAG-u tražimo:

maximum

Dijkstra — najkraći put

---

Dinamičko programiranje nad grafovima

DAG DP je jedan od najvažnijih primera dinamičkog programiranja nad grafovima.

Kasnije se iste ideje pojavljuju u:

• kritičnom putu u projektima
• raspoređivanju zadataka
• maksimalnoj zaradi
• brojanju puteva
• problemima zavisnosti

Suština:

Topološki red rešava problem redosleda, a DP čuva najbolja rešenja. Zajedno daju veoma moćnu tehniku.

Vraćanje na vodič za oblast "Grafovi i stabla"

← Mapa učenja — Grafovi i stabla