Algoritmi → Grafovi i stabla → DP na DAG-u: broj puteva i najkraći put

DP na DAG-u: broj puteva i najkraći put

Ideja

Ako su čvorovi u topološkom redosledu, onda su u trenutku obrade čvora v svi čvorovi iz kojih se stiže u v već obrađeni. Zato možemo „gurati“ vrednost iz v ka susedima:

Za razliku od Dijkstre, ovo radi i sa negativnim težinama, a najduži put u grafu sa ciklusima je težak problem – u DAG-u je lak. Najduži put je detaljno obrađen u lekciji Najduži put u DAG-u.

Broj puteva

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

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const long long MOD = 1000000007;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> graf(n + 1);
    vector<int> ulazni(n + 1, 0);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graf[u].push_back(v);
        ulazni[v]++;
    }
    // topološki redosled (Kahn)
    vector<int> red;
    queue<int> q;
    for (int v = 1; v <= n; v++) if (ulazni[v] == 0) q.push(v);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        red.push_back(v);
        for (int u : graf[v]) if (--ulazni[u] == 0) q.push(u);
    }
    // DP: br[v] = broj puteva od 1 do v
    vector<long long> br(n + 1, 0);
    br[1] = 1;
    for (int v : red)
        for (int u : graf[v])
            br[u] = (br[u] + br[v]) % MOD;
    cout << br[n] << endl;
    return 0;
}

U drugom primeru od 1 do 5 ima 5 puteva: 1-3-5, 1-2-3-5, 1-3-4-5, 1-2-3-4-5, 1-2-4-5. Broj puteva raste eksponencijalno, zato se računa po modulu 10⁹+7.

Najkraći put sa negativnim težinama

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const long long INF = 1e18;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> graf(n + 1);
    vector<int> ulazni(n + 1, 0);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graf[u].push_back({v, w});
        ulazni[v]++;
    }
    vector<int> red;
    queue<int> q;
    for (int v = 1; v <= n; v++) if (ulazni[v] == 0) q.push(v);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        red.push_back(v);
        for (auto [u, w] : graf[v]) if (--ulazni[u] == 0) q.push(u);
    }
    vector<long long> d(n + 1, INF);
    d[1] = 0;
    for (int v : red) {
        if (d[v] == INF) continue;              // v nije dostižan iz 1
        for (auto [u, w] : graf[v])
            if (d[v] + w < d[u]) d[u] = d[v] + w;
    }
    for (int v = 1; v <= n; v++) cout << (d[v] == INF ? string("INF") : to_string(d[v])) << (v < n ? " " : "\n");
    return 0;
}

Složenost je O(n + m) – brže i od Dijkstre.

Mreža je DAG

Klasičan zadatak „od gornjeg levog do donjeg desnog polja, krećući se samo desno i dole“ je DP na DAG-u: grane idu samo desno i dole, pa ciklusa nema, a redosled „red po red, sleva nadesno“ je topološki. Zato se takvi zadaci rešavaju dvostrukom petljom – vidi DP na mreži.

Zadaci za vežbu

Za svaki zadatak postoji primer, uputstvo i rešenje. Rešenja su provereno tačna na primerima iz teksta.

Proveri znanje