Tìm đường đi ngắn nhất với cạnh âm và giữa mọi cặp đỉnh

Minh gửi hàng từ kho S đến kho B. Tuyến thẳng có giá 2; tuyến qua A gồm hai chặng giá 5 và -6. Một khoản hoàn tiền tạo ra cạnh âm, nên đi qua A chỉ tốn -1. Minh cũng cần tra chi phí giữa nhiều cặp kho, kể cả khi không có đường nối chúng.

Cạnh âm có thể làm quyết định chốt sớm của Dijkstra sai

Một đường đi (path) nối các đỉnh theo chiều mũi tên. Chi phí là tổng trọng số các cạnh đã đi. Cạnh âm có thể biểu diễn khoản hoàn tiền.

Dijkstra loại chốt sớm có thể chốt B với giá 2 trước khi xử lý A với giá 5. Sau đó đường qua A cho giá -1. Kết luận chốt B đã quá sớm.

direct = 2
via_a = 5 - 6
print(direct, via_a, min(direct, via_a))

2 -1 -1

Không tới được khác với đường đi có giá 0. Ta dùng INF cho trạng thái chưa tới được. Khi dùng số nguyên làm INF, phải chọn nó đủ lớn so với mọi chi phí hữu hạn có thể xuất hiện.

Bellman–Ford cải thiện khoảng cách bằng cách quét cạnh

Nới lỏng (relaxation) cạnh u → v trọng số w là thử đi đến u, rồi đi thêm cạnh đó. Nếu dist[u] + w < dist[v], thay dist[v] bằng giá trị nhỏ hơn. Chỉ thử khi u đã tới được. Nếu không, INF + w với w âm có thể giả thành một khoảng cách hữu hạn.

INF = 10**15
dist = [0, 5, INF]
u, v, w = 1, 2, -6
if dist[u] != INF and dist[u] + w < dist[v]:
    dist[v] = dist[u] + w
print(dist)

[0, 5, -1]

Một lượt của Bellman–Ford quét toàn bộ danh sách cạnh. Giá trị vừa cập nhật có thể được dùng ngay trong lượt. Vì vậy trạng thái từng lượt phụ thuộc thứ tự cạnh, dù kết quả cuối không phụ thuộc thứ tự đó.

Bảng sau xuất phát từ đỉnh 1 và quét bốn cạnh theo đúng thứ tự 3 → 4 (2), 2 → 3 (-4), 1 → 2 (5), 1 → 4 (10):

Sau lượt thứ nhất, ta có đường trực tiếp tới 2 và 4. Lượt thứ hai tìm đường tới 3 giá 1. Lượt thứ ba tìm đường tới 4 giá 3. Nếu các cạnh được xét theo chiều đường đi, thông tin có thể lan trong một lượt.

edges = [(1, 2, 5), (2, 3, -4), (3, 4, 2)]
inf = 10**9
d = [inf, 0, inf, inf, inf]
for u, v, w in edges:
    if d[u] != inf and d[u] + w < d[v]:
        d[v] = d[u] + w
print(d[1:])

[0, 5, 1, 3]

Khi không có chu trình âm tới được, một đường tối ưu có thể bỏ mọi chu trình mà không tăng chi phí. Vì thế tồn tại đường tối ưu không lặp đỉnh và có nhiều nhất n - 1 cạnh.

Chẳng hạn, đường 1 → 2 → 3 → 2 → 4 chứa đoạn khép kín từ 2 trở về 2. Nếu đoạn đó có giá 0 hoặc dương, bỏ nó cho đường 1 → 2 → 4 không đắt hơn. Lặp thao tác cho đến khi không còn đỉnh lặp. Cách lập luận này không áp dụng nếu đoạn khép kín có giá âm.

Sau lượt thứ k, thuật toán đã đạt chi phí không lớn hơn mọi đường có tối đa k cạnh. Lập luận quy nạp xét cạnh cuối sau khi tiền tố đã được tìm trong k - 1 lượt. Cập nhật ngay có thể làm kết quả lan nhanh hơn.

Nếu một lượt không cải thiện gì, lượt sau không thể có cải thiện đầu tiên. Ta được phép dừng sớm.

4 4
3 4 2
2 3 -4
1 2 5
1 4 10

n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]
inf = 10**15
dist = [inf] * (n + 1)
dist[1] = 0
for _ in range(n - 1):
    changed = False
    for u, v, w in edges:
        if dist[u] != inf and dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            changed = True
    if not changed:
        break
print(*(x if x != inf else 'INF' for x in dist[1:]))

0 5 1 3

Đoạn này giả sử không có chu trình âm tới được từ nguồn. Mỗi lượt xét m cạnh và có tối đa n - 1 lượt, nên thời gian là O(nm). Bộ nhớ là O(n + m) nếu tính cả danh sách cạnh. Với 100 đỉnh và 1000 cạnh, có tối đa 99000 lần thử cạnh.

Chu trình âm chỉ phá đáp án của những đỉnh nó có thể ảnh hưởng

Một chu trình âm (negative cycle) có tổng trọng số nhỏ hơn 0. Nếu đi tới chu trình, quay thêm một vòng rồi đi tới đích, chi phí giảm. Khi được phép lặp cạnh, không tồn tại chi phí nhỏ nhất hữu hạn cho đích đó.

Chu trình 2 → 3 → 2 có tổng -3. Đỉnh 4 ở sau chu trình nên có thể đạt chi phí nhỏ tùy ý. Một đỉnh khác không đi tới được từ chu trình vẫn có thể có đáp án hữu hạn. Chu trình ở thành phần không tới được từ nguồn không ảnh hưởng các đường từ nguồn.

Sau n - 1 lượt, xét lại các cạnh có đầu u tới được. Nếu còn cạnh cải thiện thì có chu trình âm tới được từ nguồn. Nếu mọi cạnh trên chu trình âm đều không cải thiện, cộng các bất đẳng thức tương ứng sẽ cho 0 ≤ tổng trọng số âm. Điều này vô lý.

5 4
1 2 2
2 3 -4
3 2 1
4 5 -9

n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]
inf = 10**15
d = [inf] * (n + 1)
d[1] = 0
for _ in range(n - 1):
    for u, v, w in edges:
        if d[u] != inf and d[u] + w < d[v]:
            d[v] = d[u] + w
cycle = any(d[u] != inf and d[u] + w < d[v] for u, v, w in edges)
print('YES' if cycle else 'NO')

YES

Để đánh dấu từng đỉnh bị ảnh hưởng, lấy đỉnh cuối của các cạnh còn cải thiện làm điểm xuất phát. Duyệt tiếp theo chiều cạnh. Mọi đỉnh được đánh dấu có thể nhận chi phí nhỏ tùy ý.

from collections import deque
n = 5
edges = [(1, 2, 2), (2, 3, -4), (3, 2, 1), (3, 4, 2)]
inf = 10**15
d = [inf] * (n + 1)
d[1] = 0
adj = [[] for _ in range(n + 1)]
for u, v, w in edges:
    adj[u].append(v)
for _ in range(n - 1):
    for u, v, w in edges:
        if d[u] != inf and d[u] + w < d[v]:
            d[v] = d[u] + w
bad = [False] * (n + 1)
queue = deque()
for u, v, w in edges:
    if d[u] != inf and d[u] + w < d[v] and not bad[v]:
        bad[v] = True
        queue.append(v)
while queue:
    u = queue.popleft()
    for v in adj[u]:
        if not bad[v]:
            bad[v] = True
            queue.append(v)
print(*(i for i in range(1, n + 1) if bad[i]))

2 3 4

Lượt kiểm tra và duyệt thêm tốn O(n + m). Tổng thời gian vẫn là O(nm). Giá trị d[v] tạm thời của đỉnh bị đánh dấu không phải một đáp án hữu hạn.

Hãy phân biệt ba trạng thái của một đích. Đỉnh chưa tới được không có đường từ nguồn. Đỉnh tới được và không bị đánh dấu có khoảng cách hữu hạn. Đỉnh bị đánh dấu có các đường đi với chi phí giảm mãi. Ba trạng thái này cần ba cách biểu diễn khác nhau nếu đề yêu cầu phân loại.

Việc lấy các đỉnh cuối của cạnh còn cải thiện là đủ để bắt đầu lan truyền. Trên mỗi chu trình âm tới được, phải có ít nhất một cạnh còn cải thiện. Đỉnh cuối cạnh đó nằm trên chu trình. Từ đó, phép duyệt tới mọi đỉnh phía sau chu trình.

Ràng buộc chênh lệch được biểu diễn bằng cạnh có hướng

Giả sử x_i là thời điểm nguyên của mốc i, và một quy định yêu cầu x_v - x_u ≤ w. Viết lại thành x_v ≤ x_u + w. Bất đẳng thức này có cùng dạng điều kiện sau khi nới lỏng cạnh u → v trọng số w.

Nếu một chu trình có tổng trọng số âm, cộng các ràng buộc dọc chu trình cho 0 ≤ một số âm. Do đó hệ vô nghiệm. Để phát hiện chu trình âm ở cả những thành phần không tới được từ 1, thêm một nguồn ảo có cạnh giá 0 đến mọi đỉnh. Việc khởi tạo khoảng cách của mọi đỉnh bằng 0 tương đương các cạnh nguồn ảo đó.

Ngược lại, nếu không có chu trình âm, khoảng cách dist từ nguồn ảo thỏa dist[v] ≤ dist[u] + w trên mọi cạnh. Chọn x_i = dist[i] cho một nghiệm. Vậy hệ có nghiệm khi và chỉ khi không có chu trình âm.

Với hệ có nghiệm, cộng các ràng buộc trên một đường từ 1 tới n cho x_n - x_1 ≤ tổng trọng số đường đó. Vì vậy khoảng cách ngắn nhất từ 1 đến n là một giới hạn trên. Nếu n tới được, giới hạn này đạt được.

Để thấy điều đó, đặt giá trị các đỉnh tới được bằng khoảng cách từ 1. Với những đỉnh còn lại, dùng một nghiệm từ nguồn ảo rồi cộng cùng một hằng số đủ lớn. Không có cạnh từ tập tới được sang tập còn lại. Chọn hằng số đủ lớn cũng thỏa các cạnh theo chiều ngược lại.

Nếu 1 không tới được n, lấy một nghiệm rồi cộng cùng một số tùy ý vào mọi đỉnh không tới được. Các ràng buộc vẫn đúng, còn x_n - x_1 tăng tùy ý. Với n = 1, hiệu luôn bằng 0 nếu hệ có nghiệm.

Ví dụ dưới đây kiểm tra hệ và tìm giới hạn trên. Dữ liệu gồm số biến, số ràng buộc, rồi từng bộ u v w.

3 3
1 2 5
2 3 -2
1 3 7

import sys
n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]
potential = [0] * (n + 1)
for turn in range(n):
    changed = False
    for u, v, w in edges:
        if potential[u] + w < potential[v]:
            potential[v] = potential[u] + w
            changed = True
    if not changed:
        break
    if turn == n - 1:
        print('NO')
        sys.exit()
inf = 10**18
dist = [inf] * (n + 1)
dist[1] = 0
for _ in range(n - 1):
    changed = False
    for u, v, w in edges:
        if dist[u] != inf and dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            changed = True
    if not changed:
        break
print('INF' if dist[n] == inf else dist[n])

3

Hai ràng buộc đầu cho x_3 - x_1 ≤ 3. Giá trị x_1 = 0, x_2 = 5, x_3 = 3 đạt giới hạn đó. Với n ≤ 300 và m ≤ 3000, mỗi lần chạy Bellman–Ford thử tối đa khoảng 900000 cạnh. Hai lần chạy vẫn có độ phức tạp O(nm) và dùng O(n + m) bộ nhớ.

Floyd–Warshall xét lần lượt các đỉnh trung gian

Khi cần trả lời nhiều cặp và số đỉnh nhỏ, Floyd–Warshall lưu ma trận dist. Ban đầu dist[i][j] là cạnh trực tiếp nhỏ nhất, hoặc INF khi chưa có cạnh. Đường đi rỗng từ một đỉnh về chính nó có giá 0. Nếu có nhiều cạnh cùng chiều, giữ cạnh nhỏ nhất; không tự thêm cạnh ngược.

Ở bước k, cho phép k làm đỉnh trung gian. Với mỗi cặp i, j, so sánh đường đã biết với đường ghép từ i tới k rồi tới j. Cả hai nửa phải tới được trước khi cộng.

Vì sao cách này đúng khi không có chu trình âm? Sau bước k - 1, mỗi ô chứa chi phí nhỏ nhất khi chỉ dùng các trung gian đã xét. Đường tối ưu ở bước k hoặc không qua k, hoặc tách được tại k thành hai đoạn dùng trung gian cũ. Công thức chọn giá nhỏ hơn của hai trường hợp. Vì vậy k phải là vòng ngoài cùng.

Mỗi ô của bảng là một hàng của ma trận. Sau khi cho phép đỉnh 2, đường 1 → 2 → 3 giá 2 tốt hơn cạnh trực tiếp giá 10.

Trong bảng này, hàng đầu là đường đi rỗng và các cạnh trực tiếp. Sau khi xét đỉnh 1, chẳng hạn đường 3 → 1 → 2 có giá 7. Khi xét đỉnh 2, khoảng cách từ 1 đến 3 giảm xuống 2. Bảng không coi một ô ∞ là số thật để đem cộng.

Đường đi có thể trực tiếp nối hai đỉnh nên không cần đỉnh trung gian nào. Đường đi từ một đỉnh tới chính nó có thể không dùng cạnh nào. Khởi tạo hai trường hợp này trước khi xét k tạo cơ sở cho lập luận quy nạp.

3 4 3
1 2 8
1 2 4
2 3 -2
3 1 3
1 3
3 2
2 2

n, m, q = map(int, input().split())
inf = 10**15
d = [[inf] * n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
for _ in range(m):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    d[u][v] = min(d[u][v], w)
for k in range(n):
    for i in range(n):
        if d[i][k] == inf:
            continue
        for j in range(n):
            if d[k][j] != inf:
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
for _ in range(q):
    u, v = map(int, input().split())
    ans = d[u - 1][v - 1]
    print(ans if ans != inf else 'INF')

2
7
0

Chương trình giả sử không có chu trình âm. Ba vòng lặp tạo tối đa n³ lần xét, bộ nhớ ma trận là O(n²). Với n = 100, có một triệu bộ ba trước các phép bỏ qua. Với n = 500, có 125 triệu bộ ba, có thể quá chậm trong Python.

Ví dụ có hai cạnh từ 1 đến 2. Phép min giữ giá 4 dù cạnh giá 8 cũng xuất hiện trong dữ liệu. Truy vấn từ 2 đến chính 2 dùng đường rỗng giá 0. Các truy vấn được xử lý sau khi hoàn tất ma trận, nên mỗi truy vấn chỉ cần tra một ô.

Đường chéo âm xác định các cặp không có đáp án hữu hạn

Sau Floyd–Warshall, d[k][k] < 0 cho biết có một đường đóng âm qua k. Cặp (i, j) bị ảnh hưởng đúng khi tồn tại một k như vậy, i đi tới được k, và k đi tới được j.

Chiều đủ: đi từ i tới k, lặp đường đóng âm tùy ý, rồi đi tới j. Chiều cần: chi phí giảm vô hạn đòi hỏi một chu trình âm trên đường từ i tới j. Giá trị số trong ô của cặp bị ảnh hưởng không phải khoảng cách hữu hạn.

inf = 10**12
d = [[0, 1, inf, inf], [inf, 0, -3, inf],
     [inf, 1, 0, 2], [inf, inf, inf, 0]]
for k in range(4):
    for i in range(4):
        for j in range(4):
            if d[i][k] != inf and d[k][j] != inf:
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
for i, j in [(0, 3), (3, 3), (3, 0)]:
    affected = any(d[i][k] != inf and d[k][k] < 0 and d[k][j] != inf for k in range(4))
    print('NEG' if affected else 'INF' if d[i][j] == inf else d[i][j])

NEG
0
INF

NEG là quy ước của ví dụ cho chi phí không bị chặn dưới. Đề thực tế có thể yêu cầu ký hiệu khác. Đỉnh k có đường chéo âm không nhất thiết nằm trực tiếp trên một chu trình đơn âm.

Trong ví dụ, 1 tới được chu trình giữa 2 và 3, rồi từ đó tới 4. Vì vậy cặp đầu nhận NEG. Đỉnh 4 không đi ra được nên đường rỗng 4 đến 4 vẫn có giá 0. Cặp 4 đến 1 không có đường nên nhận INF.

Nếu có nhiều truy vấn, có thể đánh dấu mọi cặp bị ảnh hưởng sau khi tính ma trận. Với từng k có đường chéo âm, đánh dấu các cặp (i, j) mà hai đoạn i → k và k → j đều tồn tại. Việc đánh dấu thêm tối đa O(n³), cùng bậc với Floyd–Warshall.

Chọn thuật toán theo trọng số, số nguồn và kích thước

Đồ thị vô hướng có cạnh âm tạo đường đóng âm nếu được phép đi qua cạnh đó rồi quay lại. Cần đọc kỹ chiều cạnh và quy tắc cho phép lặp.

Lỗi thường gặp

Tóm tắt

Bellman–Ford quét cạnh tối đa n - 1 lượt, sau đó kiểm tra chu trình âm tới được. Floyd–Warshall xét từng đỉnh trung gian, trả lời mọi cặp trong O(n³) thời gian và O(n²) bộ nhớ. Với chu trình âm, cần kiểm tra đường tới chu trình và đường từ chu trình tới đích.

Kiểm tra nhanh

Đọc thêm

• Bellman–Ford: đường đi với trọng số âm.
• Floyd–Warshall: đường đi giữa mọi cặp.