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

U usmerenim acikličnim grafovima (DAG) moguće je efikasno naći najduži put između čvorova korišćenjem tehnika:

Topološko sortiranje – određuje pravilan redosled obilaska
Dinamčko programiranje (DP) – čuva najbolja rešenja do trenutka

Za razliku od opštih grafova, gde je najduži put težak problem (NP-Hard), u DAG-u ovaj problem rešavamo u O(N + M).

Osnovna ideja algoritma

Proveriti da li graf ima ciklus (ako ima → nema rešenja)
Napravi topološki poredak
DP niz: dp[x] = dužina najdužeg puta koji se završava u čvoru x
Ide se redom kroz topološki sortirane čvorove i ažurira DP

Prelaz:


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

gde je w(u,v) težina grane (ako su sve jednake, uzimamo 1).

Primer (neuteženi DAG)


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

Jedan najduži put je:
0 → 1 → 2 → 4 → 5 (dužina 4)

Implementacija (neuteženi graf)


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

vector> g;
vector indeg;

int main(){
    int n, m;
    cin >> n >> m;
    g.assign(n, {});
    indeg.assign(n, 0);

    for(int i=0;i> a >> b; // a -> b
        g[a].push_back(b);
        indeg[b]++;
    }

    // Topološko sortiranje (Kahn)
    queue q;
    for(int i=0;i 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);
        }
    }

    // Ako nije DAG
    if(topo.size() != n){
        cout << "Graf ima ciklus - nema resenja";
        return 0;
    }

    // DP
    vector dp(n, 0);

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

    // Najveći dp rezultat
    int ans = *max_element(dp.begin(), dp.end());
    cout << "Najduzi put u DAG-u je: " << ans;
}

Primer sa težinama (weighted DAG)


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

Cilj: maksimalna suma težina na putu.


vector>> g; // (sused, tezina)
vector dp(n, INT_MIN);
dp[start] = 0;

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

Ovo radi zato što u topološkom poretku uvek rešavamo uzroke pre posledica.

Određivanje i putanje, ne samo dužine

Da bismo vratili konkretan put, čuvamo roditelje:


vector parent(n, -1);

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

Zatim rekonstruišemo put od krajnjeg čvora unazad:


int end = max_element(dp.begin(), dp.end()) - dp.begin();
vector path;
for(int x=end; x!=-1; x=parent[x]) path.push_back(x);

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

Česte greške i zamke

❌ Pokušaj najdužeg puta u grafu koji ima ciklus → NP-težak problem
❌ Pokretanje DP bez topološkog poretka → netačni rezultati
❌ Zaboravljeno inicijalizovanje dp i parent
❌ Negativne težine u nedopuštenim algoritmima (npr. Dijkstra)

Zadaci za vežbu

Napisati program koji pronalazi najduži put iz zadatog startnog čvora
Modifikovati algoritam tako da pronalazi najduži put do svakog čvora
Rešiti primer gde težine predstavljaju trajanja zadataka u projektu
Naći kritični put u mreži aktivnosti (povezati sa realnim primerima)

Zaključak

Najduži put u DAG-u je elegantna kombinacija topološkog sortiranja + dinamičkog programiranja.

Korak po korak dolazimo do rešenja jer svaki čvor obrađujemo tek nakon što su svi njegovi "prethodnici" već obrađeni.

□ Sledeća preporučena lekcija: algoritmi_grafovi_dijkstra_kratki_put Djikstra kratki put

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

← Mapa učenja — Grafovi i stabla