Tìm chu trình âm trong đồ thị (Finding a negative cycle in the graph)¶
Bạn được cho một đồ thị có trọng số có hướng $G$ với $N$ đỉnh và $M$ cạnh. Tìm bất kỳ chu trình nào có trọng số âm trong đó, nếu tồn tại một chu trình như vậy.
Trong một cách phát biểu bài toán khác, bạn phải tìm tất cả các cặp đỉnh có đường đi với trọng số nhỏ tùy ý giữa chúng.
Thuận tiện để sử dụng các thuật toán khác nhau để giải quyết hai biến thể này của bài toán, vì vậy chúng tôi sẽ thảo luận về cả hai ở đây.
Sử dụng thuật toán Bellman-Ford (Using Bellman-Ford algorithm)¶
Thuật toán Bellman-Ford cho phép bạn kiểm tra xem có tồn tại một chu trình trọng số âm trong đồ thị hay không, và nếu có, hãy tìm một trong những chu trình này.
Các chi tiết của thuật toán được mô tả trong bài viết về thuật toán Bellman-Ford. Ở đây chúng tôi sẽ chỉ mô tả ứng dụng của nó cho bài toán này.
Cài đặt tiêu chuẩn của Bellman-Ford tìm kiếm một chu trình âm có thể truy cập được từ một đỉnh bắt đầu $v$; tuy nhiên, thuật toán có thể được sửa đổi để chỉ tìm bất kỳ chu trình âm nào trong đồ thị. Để làm điều này, chúng ta cần đặt tất cả khoảng cách $d[i]$ thành 0 và không phải vô cùng — như thể chúng ta đang tìm kiếm đường đi ngắn nhất từ tất cả các đỉnh cùng một lúc; tính hợp lệ của việc phát hiện chu trình âm không bị ảnh hưởng.
Thực hiện $N$ lần lặp thuật toán Bellman-Ford. Nếu không có thay đổi nào trong lần lặp cuối cùng, không có chu trình trọng số âm trong đồ thị. Ngược lại, lấy một đỉnh mà khoảng cách đến nó đã thay đổi, và đi từ nó qua các tổ tiên của nó cho đến khi tìm thấy chu trình. Chu trình này sẽ là chu trình trọng số âm mong muốn.
Cài đặt (Implementation)¶
struct Edge {
int a, b, cost;
};
int n;
vector<Edge> edges;
const int INF = 1000000000;
void solve() {
vector<int> d(n, 0);
vector<int> p(n, -1);
int x;
for (int i = 0; i < n; ++i) {
x = -1;
for (Edge e : edges) {
if (d[e.a] + e.cost < d[e.b]) {
d[e.b] = max(-INF, d[e.a] + e.cost);
p[e.b] = e.a;
x = e.b;
}
}
}
if (x == -1) {
cout << "No negative cycle found.";
} else {
for (int i = 0; i < n; ++i)
x = p[x];
vector<int> cycle;
for (int v = x;; v = p[v]) {
cycle.push_back(v);
if (v == x && cycle.size() > 1)
break;
}
reverse(cycle.begin(), cycle.end());
cout << "Negative cycle: ";
for (int v : cycle)
cout << v << ' ';
cout << endl;
}
}
Sử dụng thuật toán Floyd-Warshall (Using Floyd-Warshall algorithm)¶
Thuật toán Floyd-Warshall cho phép giải quyết biến thể thứ hai của bài toán - tìm tất cả các cặp đỉnh $(i, j)$ không có đường đi ngắn nhất giữa chúng (tức là tồn tại một đường đi có trọng số nhỏ tùy ý).
Một lần nữa, các chi tiết có thể được tìm thấy trong bài viết Floyd-Warshall, và ở đây chúng tôi chỉ mô tả ứng dụng của nó.
Chạy thuật toán Floyd-Warshall trên đồ thị.
Ban đầu $d[v][v] = 0$ cho mỗi $v$.
Nhưng sau khi chạy thuật toán $d[v][v]$ sẽ nhỏ hơn $0$ nếu tồn tại một đường đi có độ dài âm từ $v$ đến $v$.
Chúng ta có thể sử dụng điều này để tìm tất cả các cặp đỉnh không có đường đi ngắn nhất giữa chúng.
Chúng ta lặp qua tất cả các cặp đỉnh $(i, j)$ và đối với mỗi cặp, chúng ta kiểm tra xem chúng có đường đi ngắn nhất giữa chúng hay không.
Để làm điều này, hãy thử tất cả các khả năng cho một đỉnh trung gian $t$.
$(i, j)$ không có đường đi ngắn nhất, nếu một trong các đỉnh trung gian $t$ có $d[t][t] < 0$ (tức là $t$ là một phần của chu trình trọng số âm), $t$ có thể truy cập được từ $i$ và $j$ có thể truy cập được từ $t$.
Khi đó đường đi từ $i$ đến $j$ có thể có trọng số nhỏ tùy ý.
Chúng ta sẽ ký hiệu điều này bằng -INF.
Cài đặt (Implementation)¶
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
for (int t = 0; t < n; ++t) {
if (d[i][t] < INF && d[t][t] < 0 && d[t][j] < INF)
d[i][j] = - INF;
}
}
}