Tìm đường đi ít tốn phí bằng Dijkstra

Lan cần chuyển tài liệu từ phòng A đến phòng D. Chuyến trực tiếp tốn 100 phút, còn đi qua B và C tốn 2 phút mỗi chặng. Lan muốn biết đường nào có tổng thời gian nhỏ nhất, kể cả khi đường đó có nhiều chặng hơn.

Tổng chi phí quyết định đường đi tốt nhất

Mỗi phòng là một đỉnh (vertex), mỗi chuyến là một cạnh có hướng (directed edge). Con số trên cạnh là trọng số (weight), ở đây là thời gian đi chuyến đó. Tổng trọng số của các cạnh tạo thành chi phí của đường đi.

Đường A → D chỉ có một cạnh nhưng tốn 100. Đường A → B → C → D có ba cạnh và tốn 6. BFS ở Bài 38 tối ưu số cạnh khi mỗi cạnh có cùng chi phí, nên không giải được yêu cầu này bằng cách đếm chặng.

Đoạn sau tính chi phí của hai lựa chọn từ dữ liệu đã cho:

direct = [100]
via = [2, 2, 2]
print(sum(direct), sum(via))

100 6

Kết quả cho thấy tổng của đường qua B và C nhỏ hơn. Một đường nhiều cạnh vẫn có thể rẻ hơn nếu từng cạnh đủ nhẹ.

Đường đi ngắn nhất (shortest path) là đường có tổng trọng số nhỏ nhất trong các đường hợp lệ từ nguồn tới đích. Nếu nguồn chính là đích, đường không dùng cạnh có chi phí 0. Nếu không có đường tới đích, ta cần thông báo riêng thay vì coi chi phí là 0.

Dijkstra tìm khoảng cách ngắn nhất từ một nguồn khi mọi cạnh trong đồ thị có trọng số không âm. Trọng số 0 hợp lệ. Một cạnh âm có thể tạo đường tốt hơn sau khi thuật toán đã chốt một đỉnh, làm lập luận của thuật toán mất hiệu lực.

Đồ thị có hướng hay vô hướng đều dùng được khi các hướng đi được biểu diễn đúng. Các phòng không cần cùng liên thông với nguồn. Những phòng không tới được cần kết quả riêng.

Nếu tất cả cạnh cùng một chi phí dương, đường ít cạnh nhất cũng có tổng phí nhỏ nhất. Khi đó BFS thường đơn giản hơn. Nếu phí thay đổi theo tuyến, cần so sánh tổng phí của các đường.

Chẳng hạn, các cạnh S → A giá 2, S → B giá 5 và B → A giá -10 cho thấy nguy cơ đó. Nếu chốt A ở mức 2 trước B, sau đó đường qua B có giá -5. Với cạnh âm, xem Bellman–Ford ở Bài 41; không áp dụng quy tắc chốt của Dijkstra.

Thử cải thiện khoảng cách qua từng cạnh

Gọi dist[v] là chi phí nhỏ nhất đã tìm thấy từ nguồn tới v. Ban đầu dist[start] = 0; các đỉnh còn lại có giá trị vô cực vì chưa tìm thấy đường. Giá trị này là thông tin tạm thời, chưa phải cam kết rằng đường hiện tại tối ưu.

Nới lỏng cạnh (relaxation) là thử đi tới v bằng đường đã biết tới u, rồi qua cạnh u → v có trọng số w. Nếu dist[u] + w nhỏ hơn dist[v], ta thay khoảng cách cũ bằng giá trị mới.

Với đường tới u giá 4, cạnh giá 3 và giá cũ của v là 10, đoạn sau thực hiện một lần nới lỏng:

dist_u, weight, dist_v = 4, 3, 10
candidate = dist_u + weight
if candidate < dist_v:
    dist_v = candidate
print(dist_v)

7

Kết quả là 7: đường qua u rẻ hơn đường cũ. Nếu tổng mới bằng 10, ta giữ giá cũ vì chưa tìm được đường rẻ hơn. Dùng phép so sánh nghiêm ngặt còn tránh thêm vô hạn bản ghi khi có chu trình trọng số 0.

Thử hai cạnh dẫn tới cùng một đỉnh để thấy vì sao thứ tự phát hiện đường không quyết định kết quả:

best = float('inf')
for candidate in [12, 5]:
    if candidate < best:
        best = candidate
    print(best)

12
5

Giá trị giảm từ 12 xuống 5. Mỗi lần giảm đều ứng với một đường có thật, vì ta chỉ cộng trọng số vào một đường đã tìm thấy. Không có cạnh nối tới đỉnh nào thì khoảng cách của đỉnh đó vẫn là vô cực.

Vô cực biểu thị chưa biết đường, chứ không phải một giá vé cần cộng. Thuật toán chỉ nới lỏng từ một đỉnh đã được lấy ra với chi phí hữu hạn. Mỗi ứng viên vì vậy tương ứng với một đường có thật từ nguồn.

Nếu có hai cạnh cùng nối u với v, cạnh thứ hai có thể cải thiện giá của cạnh thứ nhất. Hai đường đi qua nhiều đỉnh cũng có thể dẫn đến cùng một nơi với giá khác nhau. Vì thế thấy v lần đầu chưa đủ để kết luận khoảng cách cuối cùng.

Hàng đợi ưu tiên chọn đỉnh gần nhất chưa chốt

Hàng đợi ưu tiên (priority queue) cho phép lấy bản ghi có khóa nhỏ nhất. Trong Python, heapq lưu một đống nhị phân (binary heap); bộ đôi (distance, vertex) được so sánh theo khoảng cách trước. Nếu hai khoảng cách bằng nhau, nhãn đỉnh quyết định thứ tự lấy; cả hai thứ tự đều hợp lệ.

Đoạn sau đưa ba bản ghi vào đống rồi lấy từng bản ghi ra:

import heapq
heap = [(8, 4), (3, 2), (3, 1)]
heapq.heapify(heap)
while heap:
    print(heapq.heappop(heap))

(3, 1)
(3, 2)
(8, 4)

Hai bản ghi giá 3 được lấy trước bản ghi giá 8. Trong hai bản ghi bằng giá, đỉnh 1 đứng trước đỉnh 2. Không nên đặt đỉnh trước khoảng cách trong bộ đôi, vì khi đó đống ưu tiên nhãn thay vì chi phí.

Khi tìm được đường mới, ta thêm bản ghi mới mà không xóa bản ghi cũ trong đống. Lúc lấy (d, u), nếu d != dist[u], đường trong bản ghi đã bị thay thế và ta bỏ qua nó. Dòng kiểm tra này giảm công việc lặp; chỉ dừng tại đích sau khi đã bỏ qua bản ghi cũ.

Xét đồ thị sau, xuất phát ở đỉnh 1. Mũi tên cho phép đi đúng chiều; cạnh giá 0 cũng có thể được sử dụng.

Ban đầu chỉ có (0, 1). Sau khi lấy 1, ta biết đường tới 2 giá 2 và tới 3 giá 5. Lấy 2 rồi cải thiện 3 xuống 3, đồng thời tìm được đường tới 4 giá 6. Lấy 3 tiếp theo sẽ cải thiện 4 xuống 4.

Bảng dưới được tạo bằng chương trình để theo dõi những lần lấy bản ghi còn hiệu lực:

Khi bản ghi (5, 3) được lấy sau đó, dist[3] đã là 3 nên bản ghi 5 bị bỏ. Tương tự, bản ghi 6 của đỉnh 4 không làm thay đổi đáp án 4.

Vì sao một bản ghi còn hiệu lực được chốt đúng? Giả sử có một đường rẻ hơn tới u chưa được tìm thấy. Trên đường đó, xét cạnh đầu tiên đi từ đỉnh đã xử lý sang đỉnh chưa xử lý. Khi xử lý đầu cạnh ấy, thuật toán đã tạo một ứng viên không lớn hơn tổng đường giả định, vì các cạnh còn lại không âm. Ứng viên ấy phải được lấy trước u, mâu thuẫn với việc u là bản ghi nhỏ nhất. Do đó khoảng cách vừa lấy là tối ưu.

Cài đặt đồ thị và xử lý đỉnh không tới được

Một danh sách kề (adjacency list) lưu tại g[u] các cặp (v, w) của cạnh đi ra từ u. Với cạnh vô hướng, thêm cả hai chiều. Các cạnh song song được phép tồn tại; mỗi cạnh đều được thử độc lập.

Chương trình dưới đọc n m s, rồi m cạnh có hướng. Nó in khoảng cách từ s tới mọi đỉnh, dùng -1 cho đỉnh không tới được:

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

import heapq

n, m, s = map(int, input().split())
g = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v, w = map(int, input().split())
    g[u].append((v, w))

dist = [float('inf')] * (n + 1)
dist[s] = 0
heap = [(0, s)]
while heap:
    d, u = heapq.heappop(heap)
    if d != dist[u]:
        continue
    for v, w in g[u]:
        nd = d + w
        if nd < dist[v]:
            dist[v] = nd
            heapq.heappush(heap, (nd, v))

print(*[-1 if x == float('inf') else x for x in dist[1:]])

0 2 3 4 -1

Đỉnh 4 nhận giá 4, còn đỉnh 5 nhận -1 vì không có đường từ nguồn. Không thay vô cực bằng một hằng số tùy ý nhỏ hơn đường hợp lệ. Python hỗ trợ số nguyên lớn; float('inf') tiện dùng để đánh dấu chưa tới được.

Mỗi lần xử lý một đỉnh hợp lệ, ta xét các cạnh đi ra của nó. Mỗi cạnh tạo nhiều nhất một lần cải thiện tại thời điểm được xét. Với n đỉnh và m cạnh có hướng, cài đặt thêm bản ghi này dùng O(n + m) bộ nhớ và O(n + m log(m + 1)) thời gian. Với đồ thị đơn, thường viết O((n + m) log n).

Ví dụ n = 10000, m = 40000 có khoảng 40000 lần xét cạnh, cùng tối đa cỡ 40001 lần thêm vào đống. Kích thước đống có thể theo số cạnh khi có nhiều cạnh song song. Vì vậy cách quét mọi đỉnh để tìm giá nhỏ nhất, tốn O(n² + m), kém phù hợp hơn trên đồ thị thưa lớn.

Nếu đề hỏi nhiều nguồn khác nhau, một lần chạy chỉ giải quyết nguồn đã chọn. Bạn cần xét số nguồn và giới hạn dữ liệu trước khi quyết định chạy lại. Mảng khoảng cách cũ thuộc nguồn cũ, nên cần khởi tạo lại cho nguồn mới.

Mảng g có n + 1 danh sách vì ví dụ đánh số từ 1. Vị trí 0 không đại diện cho một trạm nên không xuất hiện trong đầu ra. Với dữ liệu đánh số từ 0, hãy đổi kích thước và các chỉ số cho thống nhất ngay từ khi đọc.

Lưu đỉnh trước để khôi phục một đường đi

Khi cạnh u → v thật sự cải thiện dist[v], đặt parent[v] = u. Sau khi thuật toán chạy xong, lần theo parent từ đích về nguồn rồi đảo danh sách. Nếu đích chưa tới được, không lần ngược từ nó.

Đoạn sau lưu đường cho một đồ thị nhỏ, trong đó có hai cạnh dẫn tới cùng đích:

import heapq
g = [[], [(2, 5), (3, 1)], [(4, 1)], [(2, 1), (4, 9)], []]
dist = [float('inf')] * 5
parent = [-1] * 5
dist[1] = 0
heap = [(0, 1)]
while heap:
    d, u = heapq.heappop(heap)
    if d != dist[u]:
        continue
    for v, w in g[u]:
        nd = d + w
        if nd < dist[v]:
            dist[v] = nd
            parent[v] = u
            heapq.heappush(heap, (nd, v))
path = []
v = 4
if dist[v] != float('inf'):
    while v != -1:
        path.append(v)
        v = parent[v]
    path.reverse()
print(dist[4], *path)

3 1 3 2 4

Kết quả đi qua 3 rồi 2 trước khi tới 4. Cạnh trực tiếp từ 1 tới 2 được phát hiện trước, nhưng đường qua 3 rẻ hơn và thay parent[2]. Với nhiều đường cùng chi phí, cách cập nhật nghiêm ngặt giữ một đường được phát hiện trước; nó không hứa đường có thứ tự từ điển nhỏ nhất.

Bạn có thể kiểm tra đường đã in bằng cách xét từng cặp đỉnh liên tiếp. Mỗi cặp phải có cạnh đúng chiều trong dữ liệu. Tổng trọng số các cạnh đã chọn phải bằng khoảng cách cuối cùng.

Khi có cạnh song song với các trọng số khác nhau, danh sách đỉnh không cho biết rõ cạnh nào đã chọn. Nếu đề cần in mã cạnh, hãy lưu thêm mã cạnh khi cập nhật parent. Đề chỉ yêu cầu khoảng cách thì không cần mảng này.

Nếu chỉ cần khoảng cách tới một đích, có thể dừng ngay khi lấy bản ghi còn hiệu lực của đích. Không dừng ngay khi vừa thêm đích vào đống: lần phát hiện đầu có thể chưa tối ưu. Nếu nguồn bằng đích, bản ghi nguồn được lấy với chi phí 0 và đường chỉ gồm nguồn.

Đoạn sau kiểm tra trường hợp nguồn cũng là đích khi khôi phục:

source = target = 2
parent = [-1, -1, -1]
path = []
v = target
while v != -1:
    path.append(v)
    v = parent[v]
path.reverse()
print(*path)

2

Đường gồm đúng đỉnh 2 và không có cạnh nào. Chương trình không cần tìm đỉnh đứng trước nguồn.

Xem ô lưới như đỉnh và phí vào ô như trọng số

Giả sử mỗi ô có phí không âm. Từ một ô, bạn được đi lên, xuống, trái hoặc phải nếu ô mới nằm trong bảng. Phí của một bước là giá trị của ô đến; trong ví dụ này không tính phí ô xuất phát. Quy ước này phải ghi rõ trong đề, vì đề khác có thể tính cả ô đầu.

Lưới 3 × 3 dưới đây có ô giữa rất đắt. Đường đi cần cân nhắc tổng phí, không chỉ số bước.

Ta không cần tạo sẵn toàn bộ cạnh: từ tọa độ hiện tại, thử bốn hướng. Đống chứa (cost, row, col) và dist[row][col] lưu chi phí tốt nhất. Khi lấy đích với bản ghi còn hiệu lực, chương trình có thể dừng:

import heapq
grid = [[1, 1, 1], [1, 9, 1], [1, 1, 1]]
rows, cols = len(grid), len(grid[0])
dist = [[float('inf')] * cols for _ in range(rows)]
dist[0][0] = 0
heap = [(0, 0, 0)]
while heap:
    d, r, c = heapq.heappop(heap)
    if d != dist[r][c]:
        continue
    if (r, c) == (rows - 1, cols - 1):
        break
    for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        nr, nc = r + dr, c + dc
        if 0 <= nr < rows and 0 <= nc < cols:
            nd = d + grid[nr][nc]
            if nd < dist[nr][nc]:
                dist[nr][nc] = nd
                heapq.heappush(heap, (nd, nr, nc))
print(dist[rows - 1][cols - 1])

4

Kết quả là 4: đi bốn bước qua các ô giá 1 và tránh ô giữa giá 9. Nếu lưới chỉ có một ô, không cần bước nào nên chi phí là 0 theo quy ước này. Nếu ô bị chặn, hãy kiểm tra điều kiện chặn trước khi nới lỏng; ví dụ trên không có ô bị chặn.

Với R × C ô, mỗi ô có tối đa bốn cạnh đi ra. Số cạnh vì vậy không quá 4RC; thời gian là O(RC log(RC)), bộ nhớ O(RC). Một bảng 100 × 100 có 10000 ô và không quá 40000 lượt xét hướng hợp lệ. Mô hình hóa ô thành đỉnh giúp áp dụng cùng chứng minh như đồ thị thông thường.

Đếm các đường ngắn nhất khi trọng số dương

Giả sử bạn cần biết có bao nhiêu đường cùng đạt chi phí nhỏ nhất. Ngoài dist[v], hãy lưu ways[v] là số đường tốt nhất đang biết tới v. Ban đầu ways[start] = 1, ứng với đường rỗng tại nguồn.

Khi một cạnh tạo khoảng cách nhỏ hơn, các đường cũ tới đích không còn tối ưu. Ta thay ways[v] bằng ways[u]. Nếu khoảng cách mới bằng khoảng cách đang biết, ta cộng ways[u] vào ways[v]. Mỗi cạnh song song được tính là một lựa chọn riêng.

Đồ thị sau có hai đường từ 1 tới 4, mỗi đường có tổng phí 3:

import heapq
g = [[], [(2, 1), (3, 2)], [(4, 2)], [(4, 1)], []]
dist = [float('inf')] * 5
ways = [0] * 5
dist[1], ways[1] = 0, 1
heap = [(0, 1)]
while heap:
    cost, u = heapq.heappop(heap)
    if cost != dist[u]:
        continue
    for v, w in g[u]:
        nd = cost + w
        if nd < dist[v]:
            dist[v] = nd
            ways[v] = ways[u]
            heapq.heappush(heap, (nd, v))
        elif nd == dist[v]:
            ways[v] = (ways[v] + ways[u]) % 1000000007
print(dist[4], ways[4])

3 2

Kết quả cho đích 4 là chi phí 3 và hai đường. Với trọng số mỗi cạnh ít nhất 1, đỉnh trước v trên đường ngắn nhất có khoảng cách nhỏ hơn hẳn dist[v]. Dijkstra xử lý các đỉnh trước đó trước v, nên ways[v] đã nhận đủ đóng góp khi v được lấy.

Trọng số 0 phá vỡ lập luận này: hai đỉnh kề trên đường ngắn nhất có thể cùng khoảng cách. Một đóng góp có thể đến sau khi đỉnh đã được xử lý. Chu trình 0 còn làm khái niệm số đường phụ thuộc quy ước cho phép lặp đỉnh. Vì vậy cách đếm trên yêu cầu mọi trọng số dương.

Số đường có thể rất lớn, nên đề có thể yêu cầu lấy phần dư theo 1000000007. Phép cộng theo phần dư giữ kết quả đếm đúng theo yêu cầu. Với 50000 đỉnh và 100000 cạnh, thuật toán xét mỗi cạnh khi xử lý đỉnh đầu của nó và dùng O(n + m log(m + 1)) thời gian.

Thêm trạng thái khi quyền đi tiếp còn khác nhau

Giả sử Lan có một phiếu miễn phí cho tối đa một chuyến. Hai đường cùng tới trạm u nhưng khác tình trạng phiếu chưa chắc tương đương. Đường đang đắt hơn vẫn có thể dẫn tới kết quả tốt hơn nếu còn phiếu cho chuyến tiếp theo.

Ví dụ, Lan tới trạm B bằng cách trả 3 hoặc dùng phiếu để trả 0. Sau đó B có chuyến tới C giá 10. Nếu chỉ giữ giá nhỏ nhất tới B là 0, Lan đã bỏ mất đường còn phiếu và không thể giảm chuyến giá 10.

Hãy xem (u, used) là một đỉnh mới, với used = 0 nghĩa là còn phiếu. Với mỗi tuyến u → v giá w, ta có các lựa chọn sau:

• Trả phí: từ (u, used) sang (v, used) với trọng số w.
• Dùng phiếu còn lại: từ (u, 0) sang (v, 1) với trọng số 0.
• Khi used = 1, không được tạo thêm cạnh dùng phiếu.

Đoạn sau so sánh hai cách dùng phiếu trên hành trình có đúng hai chuyến, giá 3 và 10:

first, second = 3, 10
use_first = 0 + second
use_second = first + 0
print(use_first, use_second)

10 3

Kết quả cho thấy dùng phiếu ở chuyến sau tốn 3, còn dùng ở chuyến trước tốn 10. Trong đồ thị thực tế có nhiều đường, ta không thể chọn chỉ bằng cách nhìn một tuyến. Dijkstra trên các cặp trạng thái xét mọi lựa chọn hợp lệ mà vẫn dùng được trọng số không âm.

Mảng dist[u][0] và dist[u][1] lưu hai chi phí riêng. Đống chứa (cost, u, used); bản ghi cũ phải được so với đúng ô dist[u][used]. Đáp án là giá nhỏ hơn trong hai trạng thái của đích, vì đề cho phép không dùng phiếu.

Với n đỉnh và m cạnh ban đầu, đồ thị trạng thái có 2n đỉnh và tối đa 3m cạnh. Mỗi đường trong đồ thị trạng thái tương ứng một đường gốc dùng phiếu không quá một lần. Ngược lại, mỗi lựa chọn hợp lệ trong đồ thị gốc đều có đường trạng thái tương ứng. Do đó tìm đường ngắn nhất trên đồ thị mới cho đúng đáp án.

Với n = 1000, m = 5000, ta có tối đa 2000 trạng thái và 15000 cạnh trạng thái. Hàng đợi ưu tiên cho thời gian O(n + m log(m + 1)) và bộ nhớ O(n + m). Không cần dựng sẵn các cạnh trạng thái; có thể tạo các lựa chọn khi xét từng cạnh gốc.

Lỗi thường gặp

Tóm tắt

• Dijkstra áp dụng cho các cạnh không âm và tìm khoảng cách nhỏ nhất từ một nguồn.
• Mỗi lần nới lỏng, so đường qua cạnh với khoảng cách tốt nhất đang biết.
• Lấy bản ghi nhỏ nhất, bỏ bản ghi cũ và chỉ thêm khi tìm được giá nhỏ hơn.
• Lưu parent lúc cải thiện để khôi phục một đường; nêu rõ quy ước phí trên lưới.

Kiểm tra nhanh

Đọc thêm

• Tài liệu Python về heapq: cách thêm và lấy phần tử nhỏ nhất.
• CP-Algorithms: Dijkstra: lập luận và các cách cài đặt.