DP na DAG-ovima — Primene
Kod grafova bez ciklusa (DAG — Directed Acyclic Graph) možemo primeniti
dinamičko programiranje ali u specijalnom redosledu:
→ topološkom poretku
→ čvorove obrađujemo tek nakon što su obrađeni svi njegovi prethodnici
Ovo je moguće zato što DAG nema cikluse, pa ne može da se desi da funkcija odluke zavisi sama od sebe.
Topološki poredak (podsetnik)
Sortiranje čvorova tako da za svaku usmerenu granu u → v važi da je u pre v.
Primer topološkog poretka: A, C, B, E, D
Implementacija — Kahn (BFS):
queue<int> q;
for (int i = 0; i < n; i++)
if (indegree[i] == 0) q.push(i);
vector<int> topo;
while (!q.empty()){
int u = q.front(); q.pop();
topo.push_back(u);
for (int v: graf[u]){
indegree[v]--;
if (indegree[v] == 0) q.push(v);
}
}
Napomena: ako na kraju topo.size() != n → graf ima ciklus!
1️⃣ Najduži put u DAG-u
Kod običnih grafova ovaj problem je NP-težak, ali kod DAG-a možemo efikasno!
Ideja:
• topološki poredak
• za svaki čvor pamtimo najbolji rezultat (DP)
• za svaku ivicu u → v ažuriramo dp[v]
Primer (ASCII)
(0) → (1) → (3)
\ ↘
\ (4)
↘
(2) → (5)
const int INF = -1e9;
vector<int> dp(n, INF);
dp[start] = 0;
for (int u : topo){
if (dp[u] == INF) continue;
for (int v : graf[u]){
dp[v] = max(dp[v], dp[u] + 1);
}
}
Rezultat: najveća udaljenost (po broju ivica) od start do svakog čvora.
2️⃣ Brojanje putanja između dva čvora
Brojimo sve različite putanje od start do ostalih čvorova.
Ako želimo mod → koristimo MOD = 1'000'000'007
long long MOD = 1000000007;
vector<long long> ways(n, 0);
ways[start] = 1;
for (int u : topo){
for (int v : graf[u]){
ways[v] = (ways[v] + ways[u]) % MOD;
}
}
□ Ako je ways[target] = 0 → ne postoji put.
Minimalan broj ivica (najkraći put)
Ne koristimo DP nego samo:
vector<int> dist(n, INF);
dist[start] = 0;
for (int u : topo){
for (int v : graf[u]){
dist[v] = min(dist[v], dist[u] + 1);
}
}
3️⃣ Najkraći put u DAG-u (težine)
Ako graf ima težine i nema ciklusa — rešivo je brže nego Dijkstra!
vector<int> dist(n, INF);
dist[start] = 0;
for (int u : topo){
for (auto [v,w] : graf[u]){
if (dist[u] + w < dist[v]){
dist[v] = dist[u] + w;
}
}
}
⏱️ vreme: O(V + E)
Zadaci za vežbu
- Izračunati broj putanja između dva čvora u DAG-u, mod 1e9+7.
- Naći najduži put od 0 do n-1.
- Naći najkraći put u DAG-u sa težinama (može biti negativnih).
- Dat je DAG — izračunati za svaki čvor broj ulaznih i izlaznih putanja.
- Takmičarski stil: ulaz iz fajla, izlaz u fajl (I/O šablon po uzoru na IOI).
Zaključak
✔️ DAG-ovi su specijalni grafovi koji omogućavaju primenu dinamičkog programiranja.
✔️ Kombinacijom topološkog sortiranja i DP-a dobijamo snažan alat za rešavanje problema.
✔️ Najduži put, najkraći put i brojanje putanja postaju linearno rešivi.
□ Sledeće preporučeno: Critical Path Method (napredno)