Wiki › Thuật toán › Quy hoạch động (DP) › DP trên đồ thị

DP trên đồ thị

huunguyen Updated Tháng sáu 1, 2026

DP trên đồ thị là kỹ thuật áp dụng quy hoạch động lên các đỉnh/cạnh của một đồ thị, thường để tìm đường đi dài nhất / ngắn nhất, đếm số đường đi, hoặc tối ưu một đại lượng dọc theo các đường đi. Thay vì duyệt vét cạn mọi đường đi (có thể nhiều theo cấp số mũ), DP tính mỗi đỉnh đúng một lần dựa trên các đỉnh đã tính trước đó, đưa độ phức tạp về $O (V + E)$ — tuyến tính theo kích thước đồ thị.

Điều kiện cốt lõi để DP áp dụng được là phải tồn tại một thứ tự tính không vòng lặp: khi tính giá trị cho đỉnh $v$ , mọi đỉnh mà $v$ phụ thuộc vào phải đã được tính xong. Trên DAG (đồ thị có hướng không chu trình) thứ tự đó chính là thứ tự tô-pô (topological order).

Ý tưởng / Trực giác

Quy hoạch động cần ba thứ: trạng thái, công thức truy hồi, và thứ tự tính đảm bảo khi điền một ô thì các ô nó phụ thuộc đã sẵn sàng. Với DP trên mảng, thứ tự tự nhiên là $i = 0, 1, 2, \dots$ . Với DP trên đồ thị, "thứ tự" này không hiển nhiên — và đó chính là điểm mấu chốt.

Vì sao DAG dùng được DP còn đồ thị có chu trình thì không? Xét trạng thái $d p [v]$ = đường đi dài nhất kết thúc tại $v$ . Truy hồi:

$d p [v] = {max}_{u \to v} (d p [u] + w (u, v))$

Công thức này nói $d p [v]$ phụ thuộc vào $d p [u]$ của mọi đỉnh $u$ có cạnh vào $v$ . Nếu đồ thị có chu trình $a \to b \to a$ , thì $d p [a]$ cần $d p [b]$ và $d p [b]$ lại cần $d p [a]$ — phụ thuộc vòng tròn, không có thứ tự nào điền được. Ngược lại, trên DAG luôn tồn tại thứ tự tô-pô: sắp các đỉnh thành một hàng sao cho mọi cạnh đều đi từ trái sang phải. Duyệt theo hàng đó, khi tới $v$ thì mọi $u \to v$ nằm bên trái đã được tính. Đó là lý do thứ tự tô-pô làm cho truy hồi hợp lệ.

Khi đồ thị có chu trình: ta "co" mỗi thành phần liên thông mạnh (SCC — Strongly Connected Component, tập đỉnh đôi một đến được nhau) thành một siêu đỉnh. Đồ thị các siêu đỉnh luôn là DAG (vì nếu hai SCC còn tạo chu trình thì chúng đã là cùng một SCC). Thế là ta lại có DAG để chạy DP.

Có hai cách triển khai truy hồi, cho cùng kết quả:

Kéo (pull): tính $d p [v]$ bằng cách lấy max/tổng từ các đỉnh vào $v$ — cần duyệt cạnh ngược, theo đúng thứ tự tô-pô.
Đẩy (push): khi đã có $d p [u]$ , cập nhật cho mọi $v$ mà $u \to v$ . Cách này khớp tự nhiên với việc duyệt danh sách kề xuôi và là cách dùng trong các code dưới đây.

Ví dụ chạy tay

Xét DAG 5 đỉnh, các cạnh có trọng số (tìm đường đi dài nhất xuất phát từ đỉnh 1):

        (3)        (2)
    1 ------> 2 ------> 4
    |         |         ^
 (5)|      (4)|         | (6)
    v         v         |
    3 ------> 5 --------+
        (1)       (7)

Cạnh: $1 \to 2$ (3), $1 \to 3$ (5), $2 \to 4$ (2), $2 \to 5$ (4), $3 \to 5$ (1), $5 \to 4$ (6).

Bước 1 — Tìm thứ tự tô-pô. Một thứ tự hợp lệ: 1, 3, 2, 5, 4 (mọi cạnh đi từ trái sang phải trong danh sách này). Khởi tạo $d p [1] = 0$ , các đỉnh khác $= - \infty$ (chưa với tới).

Bước 2 — Duyệt theo thứ tự, đẩy giá trị sang đỉnh kề. Ô đang xử lý đánh dấu [*].

Xét đỉnh 1 [*]:  đẩy 1->2: dp[2]=max(-inf, 0+3)=3
                 đẩy 1->3: dp[3]=max(-inf, 0+5)=5
| dp:  1=0   2=3   3=5   4=-inf  5=-inf |

Xét đỉnh 3 [*]:  đẩy 3->5: dp[5]=max(-inf, 5+1)=6
| dp:  1=0   2=3   3=5   4=-inf  5=6    |

Xét đỉnh 2 [*]:  đẩy 2->4: dp[4]=max(-inf, 3+2)=5
                 đẩy 2->5: dp[5]=max(6,    3+4)=7   <- cập nhật, 7>6
| dp:  1=0   2=3   3=5   4=5     5=7    |

Xét đỉnh 5 [*]:  đẩy 5->4: dp[4]=max(5,    7+6)=13  <- cập nhật, 13>5
| dp:  1=0   2=3   3=5   4=13    5=7    |

Xét đỉnh 4 [*]:  không có cạnh ra, không làm gì.

Kết quả: đường đi dài nhất từ đỉnh 1 là $d p [4] = 13$ , tương ứng đường $1 \to 2 \to 5 \to 4$ ( $3 + 4 + 6 = 13$ ). Mỗi đỉnh chỉ được "chốt" một lần khi tới lượt trong thứ tự tô-pô, không cần thử lại.

Cài đặt

Đường đi dài nhất trên DAG (topo sort bằng DFS + DP)

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

int n, m;
vector<pair<int,int>> adj[100005]; // adj[u] = { {v, w}, ... }
vector<int> order;                 // thứ tự sau DFS (hậu thứ tự)
bool visited[100005];
long long dp[100005];

void dfs(int u) {
    visited[u] = true;
    for (auto [v, w] : adj[u])
        if (!visited[v]) dfs(v);
    order.push_back(u);            // đẩy vào SAU khi xử lý hết con -> hậu thứ tự
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }

    for (int i = 1; i <= n; i++)
        if (!visited[i]) dfs(i);
    reverse(order.begin(), order.end()); // đảo hậu thứ tự -> thứ tự tô-pô

    // -inf nghĩa là "chưa với tới được từ nguồn"
    fill(dp + 1, dp + n + 1, LLONG_MIN);
    dp[1] = 0;                     // xuất phát từ đỉnh 1

    for (int u : order) {
        if (dp[u] == LLONG_MIN) continue;  // bỏ qua đỉnh chưa với tới
        for (auto [v, w] : adj[u])
            dp[v] = max(dp[v], dp[u] + w);  // đẩy giá trị sang đỉnh kề
    }

    cout << *max_element(dp + 1, dp + n + 1) << "\n";
}

Lưu ý: DFS đẩy đỉnh vào order theo hậu thứ tự (post-order). Đảo ngược hậu thứ tự cho ra thứ tự tô-pô. Cách này chỉ đúng khi đồ thị không có chu trình.

Đếm số đường đi trên DAG

Cùng khung, đổi phép max thành phép cộng (đếm), nhớ lấy modulo:

const long long MOD = 1e9 + 7;
vector<long long> cnt(n + 1, 0);
cnt[src] = 1;                      // có đúng 1 đường rỗng từ nguồn tới chính nó

for (int u : topo_order) {         // duyệt theo thứ tự tô-pô
    for (auto [v, w] : adj[u])
        cnt[v] = (cnt[v] + cnt[u]) % MOD;  // mọi đường tới u kéo dài được tới v
}
// cnt[dst] = số đường đi từ src tới dst

Co SCC để xử lý đồ thị có chu trình (Kosaraju)

vector<int> adj[MAXN], radj[MAXN]; // đồ thị gốc và đồ thị đảo cạnh
bool vis[MAXN];
vector<int> ord;                   // hậu thứ tự của lượt DFS thứ nhất
int scc_id[MAXN];

void dfs1(int u) {                 // DFS trên đồ thị gốc, lấy hậu thứ tự
    vis[u] = true;
    for (int v : adj[u]) if (!vis[v]) dfs1(v);
    ord.push_back(u);
}
void dfs2(int u, int id) {         // DFS trên đồ thị đảo, gán nhãn SCC
    scc_id[u] = id;
    for (int v : radj[u]) if (scc_id[v] == -1) dfs2(v, id);
}

int kosaraju(int n) {
    for (int i = 1; i <= n; i++) if (!vis[i]) dfs1(i);
    memset(scc_id, -1, sizeof(scc_id));
    int num_scc = 0;
    // duyệt đỉnh theo hậu thứ tự GIẢM DẦN trên đồ thị đảo
    for (int i = (int)ord.size() - 1; i >= 0; i--) {
        int u = ord[i];
        if (scc_id[u] == -1) dfs2(u, num_scc++);
    }
    return num_scc; // sau đó: xây DAG các SCC rồi DP như phần trên
}

Sau khi có scc_id[], dồn các đỉnh cùng SCC lại, dựng cạnh giữa các SCC khác nhau để được DAG rút gọn, rồi chạy đúng DP đường đi dài nhất / đếm đường ở trên — lúc này mỗi siêu đỉnh có thể mang theo "lợi ích nội bộ" (vd số đỉnh trong SCC).

Độ phức tạp

Bài toán	Thời gian	Bộ nhớ
DP đường đi dài/ngắn nhất, đếm đường trên DAG	$O (V + E)$	$O (V + E)$
Co SCC (Kosaraju/Tarjan) + DP trên DAG rút gọn	$O (V + E)$	$O (V + E)$
Dijkstra + DP trạng thái mở rộng $K$ chiều	$O (K E \log (K V))$	$O (K V)$

Vì sao $O (V + E)$ : topo sort bằng DFS thăm mỗi đỉnh đúng một lần ( $O (V)$ ) và đi qua mỗi cạnh đúng một lần ( $O (E)$ ). Vòng DP sau đó cũng duyệt mỗi cạnh đúng một lần để đẩy giá trị. Tổng cộng tuyến tính. Bộ nhớ $O (V + E)$ cho danh sách kề, cộng $O (V)$ cho mảng dp[] và mảng visited[].

Với Dijkstra + DP: nhân thêm hệ số $K$ (số chiều trạng thái phụ, vd "đã dùng bao nhiêu lượt đặc biệt") vào cả số nút trong hàng đợi ưu tiên lẫn bộ nhớ.

⚠️ Lỗi thường gặp

Dùng DP khi đồ thị còn chu trình. Nếu đồ thị có hướng mà còn chu trình, không tồn tại thứ tự tô-pô; vòng for (u : order) sẽ cho kết quả sai (thường thiếu, vì một đỉnh trong chu trình bị "chốt" trước khi giá trị thật chảy vào). Triệu chứng: đáp án nhỏ hơn thực tế trên test có chu trình. Cách tránh: kiểm tra chu trình (đếm số đỉnh trong order; nếu $< n$ thì có chu trình) hoặc co SCC trước.
Tràn số khi đếm hoặc cộng trọng số lớn. Số đường đi trên DAG bùng nổ theo cấp số mũ, vượt int rất nhanh — phải dùng long long và lấy modulo từng bước. Đường đi dài nhất với $V$ đỉnh, trọng số tới $10^{9}$ có thể đạt $~ 10^{14}$ , vượt int. Luôn dùng long long cho mảng dp[].
Khởi tạo sai giá trị "không với tới". Với đường đi dài nhất, khởi tạo $- \infty$ (LLONG_MIN) và bỏ qua đỉnh còn $- \infty$ (if (dp[u] == LLONG_MIN) continue;). Quên dòng này sẽ cộng $w$ vào LLONG_MIN gây tràn âm (underflow) và lan giá trị rác ra toàn đồ thị.
Nhầm hậu thứ tự với thứ tự tô-pô. Hậu thứ tự DFS (thứ tự push_back trong dfs) là đảo ngược của thứ tự tô-pô. Quên reverse(order...) sẽ duyệt ngược, khiến mỗi $d p [v]$ được tính khi các đỉnh trước nó chưa sẵn sàng. Triệu chứng: kết quả như thể chưa lan truyền gì.
Sai định nghĩa trạng thái trong DP nhúng Dijkstra. Khi thêm chiều phụ (vd "số lần đổi cạnh đã dùng"), phải so sánh và pop đúng theo dist[u][j] của đúng chiều $j$ ; lẫn lộn các chiều làm thuật toán nhận đường tệ hơn là tối ưu. Luôn kiểm tra if (d > dist[u][j]) continue; với đúng cặp $(u, j)$ lấy ra từ hàng đợi.

Biến thể / Mở rộng

DP với Dijkstra (mở rộng trạng thái). Khi bài kết hợp đường đi ngắn nhất với một biến đếm hữu hạn (vd được phép biến tối đa $k$ cạnh thành miễn phí), nhân trạng thái thành $(u, j)$ với $j$ = số lượt đặc biệt đã dùng:

// dist[u][j] = đường ngắn nhất tới u khi đã dùng j lượt biến cạnh thành 0
vector<vector<long long>> dist(n + 1, vector<long long>(k + 1, LLONG_MAX));
priority_queue<tuple<long long,int,int>,
               vector<tuple<long long,int,int>>, greater<>> pq;
dist[s][0] = 0;
pq.push({0, s, 0});

while (!pq.empty()) {
    auto [d, u, j] = pq.top(); pq.pop();
    if (d > dist[u][j]) continue;          // bản ghi cũ, bỏ qua
    for (auto [v, w] : adj[u]) {
        // dùng cạnh bình thường
        if (dist[u][j] + w < dist[v][j]) {
            dist[v][j] = dist[u][j] + w;
            pq.push({dist[v][j], v, j});
        }
        // dùng 1 lượt đặc biệt: cạnh này thành 0
        if (j < k && dist[u][j] < dist[v][j + 1]) {
            dist[v][j + 1] = dist[u][j];
            pq.push({dist[v][j + 1], v, j + 1});
        }
    }
}
long long ans = *min_element(dist[t].begin(), dist[t].end());

DP trên DAG ngầm (implicit). Đôi khi đồ thị không cho tường minh mà sinh ra từ một quan hệ thứ tự. Ví dụ: công việc $i$ phải làm trước $j$ nếu $a_{i} < a_{j}$ và $b_{i} < b_{j}$ — tìm chuỗi dài nhất chính là LIS hai chiều: sắp theo $a$ , rồi DP trên $b$ .

Đếm/đi đường với ràng buộc, đồ thị nhỏ. Khi $n \leq 20$ , dùng DP bitmask $d p [mask] [u]$ = số đường đi qua đúng tập đỉnh mask, kết thúc tại u (đường Hamilton khi mask đầy). Xem thêm DP bitmask và DP trên cây cho trường hợp đồ thị là cây.

Bài tập luyện

Lịch vắt sữa (milksched) — (Intermediate) Bài nhập môn kinh điển: dựng DAG từ quan hệ phụ thuộc rồi DP theo thứ tự tô-pô để tìm số mức tối thiểu.
Cánh đồng cỏ (grasscow) — (Veteran) Đồ thị có chu trình: co SCC thành DAG rồi DP đường đi dài nhất — đúng quy trình SCC → DAG → DP.
Đếm số đường đi (pathcnt) — (Veteran) Đếm đường đi trên đồ thị, luyện truy hồi cộng-modulo và xử lý thứ tự tính.
Hành trình dài nhất nhỏ nhất (mintrip) — (Veteran) Kết hợp DP trên đồ thị với sắp xếp/tham, củng cố cách thiết kế trạng thái khi cạnh có nhiều thuộc tính.
Đường đi chi phí nhỏ nhất (mincostpath) — (Expert) Nhúng DP vào Dijkstra với trạng thái mở rộng — bài tổng hợp cho biến thể "shortest path + DP".