Đây là bản xem thử. Phiên bản đầy đủ trong ứng dụng có bài tập, AI chấm ngay và theo dõi tiến độ học.
Bài học
Dijkstra bằng heapq và giới hạn của thuật toán
Mục tiêu bài học
Sau bài này, em cài đặt được thuật toán Dijkstra bằng `heapq` để tìm đường đi ngắn nhất từ một đỉnh nguồn tới mọi đỉnh còn lại trên đồ thị trọng số không âm, đạt đúng độ phức tạp $O((V+E)\log V)$, và — quan trọng hơn cả phần cài đặt — nhận ra chính xác lúc nào thuật toán này KHÔNG còn dùng được.
Cần nhớ trước
Bài học dùng lại nền tảng của khóa Đồ thị (I): duyệt đồ thị bằng BFS/DFS, biểu diễn đồ thị bằng danh sách kề, và cấu trúc hàng đợi (`deque`). Nếu em chưa quen module `heapq` — hàng đợi ưu tiên kiểu min-heap trong Python, hai thao tác chính là `heappush` và `heappop` — hãy thử vài dòng trong trình thông dịch trước khi đọc tiếp.
**So với mức chuẩn:** SGK Tin học 12 giới thiệu bài toán đường đi ngắn nhất chủ yếu trên đồ thị nhỏ, đủ để dò bằng tay hoặc chạy BFS khi mọi cạnh cùng trọng số. Đề HSG cho $V \le 10^5$, $E \le 2\times 10^5$ — dò tay là bất khả thi, và một cài đặt Dijkstra kiểu mảng $O(V^2)$ cũng không kịp thời gian. Em cần bản heap đúng độ phức tạp, cộng với hiểu biết chính xác về giới hạn của thuật toán.
Bài toán mở đầu — hệ thống giao hàng
Một trung tâm phát hàng đặt tại kho $S$, cần giao tới năm điểm $A, B, C, D, E$. Giữa các điểm có những tuyến đường hai chiều với thời gian di chuyển (phút) đã biết. Trung tâm muốn biết: đường đi nhanh nhất từ $S$ tới TỪNG điểm là bao nhiêu, và cụ thể đi qua đâu?
Đồ thị (vô hướng, trọng số là thời gian):
$S$-$A$: 4, $S$-$B$: 1, $B$-$A$: 2, $B$-$C$: 5, $A$-$C$: 1, $A$-$D$: 7, $C$-$D$: 3, $C$-$E$: 6, $D$-$E$: 2.
Duyệt tay từng đường một sẽ nhầm lẫn ngay khi có nhiều điểm — ta cần một quy trình có thể chứng minh là luôn đúng.
Ý tưởng cốt lõi — luôn xử lý đỉnh gần nhất trước
Gọi $dist[v]$ là khoảng cách tạm thời (ước lượng hiện tại, có thể còn giảm tiếp) từ $S$ đến $v$. Dijkstra lặp lại: trong các đỉnh CHƯA "chốt", chọn đỉnh $u$ có $dist[u]$ nhỏ nhất, chốt nó (coi $dist[u]$ là giá trị cuối cùng, không đổi nữa), rồi "nới lỏng" (relax) mọi cạnh đi ra từ $u$ — nếu $dist[u] + w(u,v) < dist[v]$ thì cập nhật $dist[v]$.
**Vì sao chốt xong không cần xét lại?** Xét đỉnh $u$ có $dist[u]$ nhỏ nhất trong các đỉnh chưa chốt tại một thời điểm. Mọi đường đi khác tới $u$ phải đi qua ít nhất một đỉnh $w$ chưa chốt trước khi tới $u$. Vì $dist[w] \ge dist[u]$ (do $u$ đang nhỏ nhất) và mọi trọng số cạnh đều $\ge 0$, nên đường đi qua $w$ không thể ngắn hơn $dist[u]$. Đây chính là chỗ điều kiện "không âm" được dùng — thiếu nó, lập luận sụp đổ hoàn toàn, như Ví dụ 3 dưới đây sẽ cho thấy.
Ví dụ
Ví dụ 1 — cài đặt Dijkstra bằng heapq và chạy trên đồ thị giao hàng
1
Dùng một min-heap chứa các cặp $(dist, đỉnh)$. Mỗi lần lấy ra cặp có $dist$ nhỏ nhất; nếu đỉnh đó đã "chốt" rồi (một bản ghi cũ, lỗi thời còn sót trong heap) thì bỏ qua — đây gọi là kỹ thuật **lazy deletion**: thay vì tìm và xóa bản ghi cũ trong heap (tốn kém), ta cứ để nó nằm đó và lọc ra khi lấy lên.
2
```python
import heapq
def dijkstra(n, adj, src):
dist = [float('inf')] * n
dist[src] = 0
pq = [(0, src)] # (khoảng cách tạm, đỉnh)
visited = [False] * n
while pq:
d, u = heapq.heappop(pq)
if visited[u]:
continue # bản ghi cũ, lazy deletion: bỏ qua
visited[u] = True # chốt u
for v, w in adj[u]:
if not visited[v] and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(pq, (dist[v], v))
return dist
```
Mỗi cạnh tạo ra nhiều nhất một lần push, mỗi lần push/pop tốn $O(\log V)$, nên tổng độ phức tạp là $O((V+E)\log V)$ — KHÔNG phải $O(V^2)$ của bản cài đặt mảng cũ.
3
Chạy `dijkstra` từ $S$, thứ tự "chốt" và giá trị $dist$ ngay sau mỗi lần chốt:
Bước 1: chốt $S$ ($dist=0$) → cập nhật $A=4$, $B=1$.
Bước 2: chốt $B$ ($dist=1$, nhỏ nhất trong hàng đợi) → cập nhật $A=3$ (qua $B$, tốt hơn 4), $C=6$.
Bước 3: chốt $A$ ($dist=3$) → cập nhật $C=4$ (qua $A$, tốt hơn 6), $D=10$.
Bước 4: chốt $C$ ($dist=4$) → cập nhật $D=7$ (qua $C$, tốt hơn 10), $E=10$.
Bước 5: chốt $D$ ($dist=7$) → cập nhật $E=9$ (qua $D$, tốt hơn 10).
Bước 6: chốt $E$ ($dist=9$) → không còn cạnh nào cải thiện thêm.
Kết quả cuối: $dist[S,A,B,C,D,E] = 0, 3, 1, 4, 7, 9$.
4
Ta có đồ thị vô hướng không âm, áp dụng Dijkstra với hàng đợi ưu tiên. Theo tính chất chốt-là-xong đã chứng minh ở trên, thứ tự chốt $S \to B \to A \to C \to D \to E$ cho khoảng cách đúng ngay khi mỗi đỉnh được chốt. Vậy khoảng cách ngắn nhất từ $S$ tới $A, B, C, D, E$ lần lượt là $3, 1, 4, 7, 9$ (đơn vị phút).
Thứ tự chốt đỉnh của Dijkstra trên đồ thị giao hàng — mỗi bước chốt đúng một đỉnh có khoảng cách tạm nhỏ nhất.Bước 6 (kết thúc): mảng dist cuối cùng — đây là đáp án của Ví dụ 1.
Ví dụ
Ví dụ 2 — truy vết đường đi cụ thể bằng mảng cha
1
Đề chuẩn thường chỉ hỏi khoảng cách. Đề HSG hay hỏi thêm: đường đi CỤ THỂ đó gồm những đỉnh nào — đòi hỏi lưu lại "đỉnh cha" của mỗi đỉnh trong quá trình nới lỏng, không chỉ mỗi giá trị $dist$.
2
```python
def dijkstra_with_parent(n, adj, src):
dist = [float('inf')] * n
parent = [-1] * n
dist[src] = 0
pq = [(0, src)]
visited = [False] * n
while pq:
d, u = heapq.heappop(pq)
if visited[u]:
continue
visited[u] = True
for v, w in adj[u]:
if not visited[v] and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
parent[v] = u
heapq.heappush(pq, (dist[v], v))
return dist, parent
def trace_path(parent, names, target):
path = []
v = target
while v != -1:
path.append(names[v])
v = parent[v]
return list(reversed(path))
```
Mỗi khi nới lỏng thành công cạnh $(u,v)$, ta ghi $parent[v] = u$ — đây CHÍNH LÀ cạnh cuối cùng trên đường đi ngắn nhất tới $v$, vì $dist[v]$ chỉ đổi khi tìm ra đường ngắn hơn.
3
Theo Bước 5 ở Ví dụ 1, $D$ được cập nhật lần cuối qua $C$ ($dist[D] = dist[C] + 3 = 4+3=7$), $C$ được cập nhật qua $A$ ($dist[C]=dist[A]+1=3+1=4$), $A$ được cập nhật qua $B$ ($dist[A]=dist[B]+2=1+2=3$), $B$ được cập nhật trực tiếp từ $S$. Truy ngược mảng $parent$: $D \to C \to A \to B \to S$. Đảo chiều: đường đi là $S \to B \to A \to C \to D$, tổng chi phí $1+2+1+3=7$ — khớp $dist[D]=7$.
4
Mảng $parent$ được cập nhật đồng thời với $dist$ trong mỗi lần nới lỏng thành công, nên khi thuật toán kết thúc, truy ngược từ đích về nguồn qua $parent$ luôn cho đúng MỘT đường đi ngắn nhất (có thể có nhiều đường cùng chi phí, thuật toán chỉ giữ đường tìm thấy trước). Vậy đường đi ngắn nhất từ $S$ đến $D$ là $S \to B \to A \to C \to D$, độ dài 7 phút.
Khi trọng số có thể âm — Dijkstra bắt đầu sai
Lập luận "chốt xong không cần xét lại" ở trên dựa đúng một chỗ: mọi trọng số cạnh không âm. Bỏ điều kiện này, chứng minh không còn đúng — và không chỉ là lý thuyết suông, ta có thể XÂY một đồ thị cụ thể khiến Dijkstra trả lời sai.
Ví dụ
Ví dụ 3 — phản ví dụ: Dijkstra sai khi có cạnh âm
1
Đồ thị có hướng ba đỉnh $S, A, B$: cạnh $S \to B$ trọng số $1$, cạnh $S \to A$ trọng số $2$, cạnh $A \to B$ trọng số $-5$. Đường đi ngắn nhất thật sự từ $S$ đến $B$ là bao nhiêu?
2
Khởi tạo $dist[S]=0$. Nới lỏng từ $S$: $dist[B]=1$, $dist[A]=2$. Heap có $(1,B)$ và $(2,A)$ — Dijkstra lấy $(1,B)$ ra TRƯỚC vì nhỏ hơn, và **chốt luôn $B=1$** (đánh dấu `visited[B]=True`). Sau đó lấy $(2,A)$, chốt $A=2$, nới lỏng cạnh $A \to B$: $dist[A]+(-5) = -3 < dist[B]=1$ — về mặt số học đây LÀ đường ngắn hơn, nhưng vì `visited[B]` đã `True`, dòng lệnh `if not visited[v]` chặn cập nhật lại. Dijkstra dừng và trả lời $dist[B]=1$.
3
Bellman-Ford (không có bước "chốt" sớm, nới lỏng tự do cho tới khi không đổi nữa) cho $dist[B] = \min(1,\; 2+(-5)) = \min(1,-3) = -3$.
4
Dijkstra trả lời $1$, nhưng đường đi ngắn nhất thật sự là $S \to A \to B$ với chi phí $-3$. **Dijkstra chốt đỉnh $B$ quá sớm** — trước khi kịp biết đường vòng qua $A$ rẻ hơn nhiều nhờ cạnh âm $-5$ — rồi khóa cứng giá trị đó lại. Đây là lý do nền tảng: hễ đồ thị có cạnh trọng số âm, TUYỆT ĐỐI không dùng Dijkstra, dù cạnh âm đó có nằm "xa" đỉnh cần hỏi hay không.
Bẫy thường gặp
Ba bẫy hay gặp: (1) tưởng "lazy deletion" (không xóa bản ghi cũ trong heap) tự động sửa được lỗi cạnh âm — nó chỉ tối ưu tốc độ, không đổi bản chất thuật toán tham lam; (2) quên rằng $O((V+E)\log V)$ chỉ đúng khi dùng heap, cài đặt bằng mảng tuyến tính là $O(V^2)$ (vẫn đúng, chỉ chậm hơn với đồ thị thưa); (3) thấy đề chỉ có MỘT cạnh âm "ở xa" rồi vẫn chủ quan dùng Dijkstra — phản ví dụ trên chỉ cần đúng một cạnh âm là đủ để sai.
Mở rộng dành cho HSG — Dijkstra phân lớp (0-1 BFS)
Kỹ thuật sau không nằm trong yêu cầu chuẩn của lớp 12. Khi trọng số cạnh CHỈ nhận giá trị $0$ hoặc $1$, ta có thể thay hàng đợi ưu tiên (chi phí $O(\log V)$ mỗi thao tác) bằng một `deque` hai đầu: cạnh trọng số $0$ thì đẩy đỉnh vào ĐẦU hàng đợi, cạnh trọng số $1$ thì đẩy vào CUỐI. Vì hàng đợi luôn giữ thứ tự không giảm theo khoảng cách, ta không cần so sánh gì thêm — đạt $O(V+E)$, nhanh hơn hẳn $O((V+E)\log V)$ của Dijkstra tổng quát.
```python
from collections import deque
def zero_one_bfs(n, adj, src):
dist = [float('inf')] * n
dist[src] = 0
dq = deque([src])
while dq:
u = dq.popleft()
for v, w in adj[u]: # w chỉ là 0 hoặc 1
nd = dist[u] + w
if nd < dist[v]:
dist[v] = nd
(dq.appendleft if w == 0 else dq.append)(v)
return dist
```
Trên một đồ thị thử nghiệm 5 đỉnh $S,A,B,C,D$ với các cạnh trọng số $0/1$, `zero_one_bfs` và `dijkstra` cho ra CÙNG một mảng $dist$ — như kỳ vọng, vì $0/1$ vẫn là không âm, chỉ là 0-1 BFS khai thác cấu trúc đặc biệt để nhanh hơn.
Luyện tập có hướng dẫn
Luyện tập độc lập
Thử thách
Tóm tắt
Dijkstra tham lam đúng khi mọi trọng số $\ge 0$: luôn chốt đỉnh gần nhất, dùng `heapq` để đạt $O((V+E)\log V)$, lưu mảng $parent$ để truy vết đường đi. Khi có dù chỉ MỘT cạnh âm, thuật toán có thể chốt sai và không sửa lại được — Ví dụ 3 là mẫu phản chứng cần nhớ nằm lòng cho phòng thi. Khi trọng số chỉ 0/1, 0-1 BFS là một biến thể nhanh hơn đáng nhớ.
Bước tiếp theo: xử lý chính xác lớp đồ thị mà Dijkstra bó tay — đồ thị có cạnh trọng số âm.
Sau bài này, em cài đặt được thuật toán Dijkstra bằng heapq để tìm đường đi ngắn nhất từ một đỉnh nguồn tới mọi đỉnh còn lại trên đồ thị trọng số không âm, đạt đúng độ phức tạp O((V+E)logV), và — quan trọng hơn cả phần cài đặt — nhận ra chính xác lúc nào thuật toán này KHÔNG còn dùng được.
Bài học dùng lại nền tảng của khóa Đồ thị (I): duyệt đồ thị bằng BFS/DFS, biểu diễn đồ thị bằng danh sách kề, và cấu trúc hàng đợi (deque). Nếu em chưa quen module heapq — hàng đợi ưu tiên kiểu min-heap trong Python, hai thao tác chính là heappush và heappop — hãy thử vài dòng trong trình thông dịch trước khi đọc tiếp.
So với mức chuẩn: SGK Tin học 12 giới thiệu bài toán đường đi ngắn nhất chủ yếu trên đồ thị nhỏ, đủ để dò bằng tay hoặc chạy BFS khi mọi cạnh cùng trọng số. Đề HSG cho V≤105, E≤2×105 — dò tay là bất khả thi, và một cài đặt Dijkstra kiểu mảng O(V2) cũng không kịp thời gian. Em cần bản heap đúng độ phức tạp, cộng với hiểu biết chính xác về giới hạn của thuật toán.
Một trung tâm phát hàng đặt tại kho S, cần giao tới năm điểm A,B,C,D,E. Giữa các điểm có những tuyến đường hai chiều với thời gian di chuyển (phút) đã biết. Trung tâm muốn biết: đường đi nhanh nhất từ S tới TỪNG điểm là bao nhiêu, và cụ thể đi qua đâu?
Đồ thị (vô hướng, trọng số là thời gian):
S-A: 4, S-B: 1, B-A: 2, B-C: 5, A-C: 1, A-D: 7, C-D: 3, C-E: 6, D-E: 2.
Duyệt tay từng đường một sẽ nhầm lẫn ngay khi có nhiều điểm — ta cần một quy trình có thể chứng minh là luôn đúng.
Gọi dist[v] là khoảng cách tạm thời (ước lượng hiện tại, có thể còn giảm tiếp) từ S đến v. Dijkstra lặp lại: trong các đỉnh CHƯA "chốt", chọn đỉnh u có dist[u] nhỏ nhất, chốt nó (coi dist[u] là giá trị cuối cùng, không đổi nữa), rồi "nới lỏng" (relax) mọi cạnh đi ra từ u — nếu dist[u]+w(u,v)<dist[v] thì cập nhật dist[v].
Vì sao chốt xong không cần xét lại? Xét đỉnh u có dist[u] nhỏ nhất trong các đỉnh chưa chốt tại một thời điểm. Mọi đường đi khác tới u phải đi qua ít nhất một đỉnh w chưa chốt trước khi tới u. Vì dist[w]≥dist[u] (do u đang nhỏ nhất) và mọi trọng số cạnh đều ≥0, nên đường đi qua w không thể ngắn hơn dist[u]. Đây chính là chỗ điều kiện "không âm" được dùng — thiếu nó, lập luận sụp đổ hoàn toàn, như Ví dụ 3 dưới đây sẽ cho thấy.
Dùng một min-heap chứa các cặp (dist,đỉnh). Mỗi lần lấy ra cặp có dist nhỏ nhất; nếu đỉnh đó đã "chốt" rồi (một bản ghi cũ, lỗi thời còn sót trong heap) thì bỏ qua — đây gọi là kỹ thuật lazy deletion: thay vì tìm và xóa bản ghi cũ trong heap (tốn kém), ta cứ để nó nằm đó và lọc ra khi lấy lên.
import heapq
def dijkstra(n, adj, src):
dist = [float('inf')] * n
dist[src] = 0
pq = [(0, src)] # (khoảng cách tạm, đỉnh)
visited = [False] * n
while pq:
d, u = heapq.heappop(pq)
if visited[u]:
continue # bản ghi cũ, lazy deletion: bỏ qua
visited[u] = True # chốt u
for v, w in adj[u]:
if not visited[v] and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(pq, (dist[v], v))
return dist
Mỗi cạnh tạo ra nhiều nhất một lần push, mỗi lần push/pop tốn O(logV), nên tổng độ phức tạp là O((V+E)logV) — KHÔNG phải O(V2) của bản cài đặt mảng cũ.
Chạy dijkstra từ S, thứ tự "chốt" và giá trị dist ngay sau mỗi lần chốt:
Bước 1: chốt S (dist=0) → cập nhật A=4, B=1.
Bước 2: chốt B (dist=1, nhỏ nhất trong hàng đợi) → cập nhật A=3 (qua B, tốt hơn 4), C=6.
Bước 3: chốt A (dist=3) → cập nhật C=4 (qua A, tốt hơn 6), D=10.
Bước 4: chốt C (dist=4) → cập nhật D=7 (qua C, tốt hơn 10), E=10.
Bước 5: chốt D (dist=7) → cập nhật E=9 (qua D, tốt hơn 10).
Bước 6: chốt E (dist=9) → không còn cạnh nào cải thiện thêm.
Kết quả cuối: dist[S,A,B,C,D,E]=0,3,1,4,7,9.
Ta có đồ thị vô hướng không âm, áp dụng Dijkstra với hàng đợi ưu tiên. Theo tính chất chốt-là-xong đã chứng minh ở trên, thứ tự chốt S→B→A→C→D→E cho khoảng cách đúng ngay khi mỗi đỉnh được chốt. Vậy khoảng cách ngắn nhất từ S tới A,B,C,D,E lần lượt là 3,1,4,7,9 (đơn vị phút).
Đề chuẩn thường chỉ hỏi khoảng cách. Đề HSG hay hỏi thêm: đường đi CỤ THỂ đó gồm những đỉnh nào — đòi hỏi lưu lại "đỉnh cha" của mỗi đỉnh trong quá trình nới lỏng, không chỉ mỗi giá trị dist.
def dijkstra_with_parent(n, adj, src):
dist = [float('inf')] * n
parent = [-1] * n
dist[src] = 0
pq = [(0, src)]
visited = [False] * n
while pq:
d, u = heapq.heappop(pq)
if visited[u]:
continue
visited[u] = True
for v, w in adj[u]:
if not visited[v] and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
parent[v] = u
heapq.heappush(pq, (dist[v], v))
return dist, parent
def trace_path(parent, names, target):
path = []
v = target
while v != -1:
path.append(names[v])
v = parent[v]
return list(reversed(path))
Mỗi khi nới lỏng thành công cạnh (u,v), ta ghi parent[v]=u — đây CHÍNH LÀ cạnh cuối cùng trên đường đi ngắn nhất tới v, vì dist[v] chỉ đổi khi tìm ra đường ngắn hơn.
Theo Bước 5 ở Ví dụ 1, D được cập nhật lần cuối qua C (dist[D]=dist[C]+3=4+3=7), C được cập nhật qua A (dist[C]=dist[A]+1=3+1=4), A được cập nhật qua B (dist[A]=dist[B]+2=1+2=3), B được cập nhật trực tiếp từ S. Truy ngược mảng parent: D→C→A→B→S. Đảo chiều: đường đi là S→B→A→C→D, tổng chi phí 1+2+1+3=7 — khớp dist[D]=7.
Mảng parent được cập nhật đồng thời với dist trong mỗi lần nới lỏng thành công, nên khi thuật toán kết thúc, truy ngược từ đích về nguồn qua parent luôn cho đúng MỘT đường đi ngắn nhất (có thể có nhiều đường cùng chi phí, thuật toán chỉ giữ đường tìm thấy trước). Vậy đường đi ngắn nhất từ S đến D là S→B→A→C→D, độ dài 7 phút.
Đồ thị có hướng ba đỉnh S,A,B: cạnh S→B trọng số 1, cạnh S→A trọng số 2, cạnh A→B trọng số −5. Đường đi ngắn nhất thật sự từ S đến B là bao nhiêu?
Khởi tạo dist[S]=0. Nới lỏng từ S: dist[B]=1, dist[A]=2. Heap có (1,B) và (2,A) — Dijkstra lấy (1,B) ra TRƯỚC vì nhỏ hơn, và chốt luôn B=1 (đánh dấu visited[B]=True). Sau đó lấy (2,A), chốt A=2, nới lỏng cạnh A→B: dist[A]+(−5)=−3<dist[B]=1 — về mặt số học đây LÀ đường ngắn hơn, nhưng vì visited[B] đã True, dòng lệnh if not visited[v] chặn cập nhật lại. Dijkstra dừng và trả lời dist[B]=1.
Bellman-Ford (không có bước "chốt" sớm, nới lỏng tự do cho tới khi không đổi nữa) cho dist[B]=min(1,2+(−5))=min(1,−3)=−3.
Dijkstra trả lời 1, nhưng đường đi ngắn nhất thật sự là S→A→B với chi phí −3. Dijkstra chốt đỉnh B quá sớm — trước khi kịp biết đường vòng qua A rẻ hơn nhiều nhờ cạnh âm −5 — rồi khóa cứng giá trị đó lại. Đây là lý do nền tảng: hễ đồ thị có cạnh trọng số âm, TUYỆT ĐỐI không dùng Dijkstra, dù cạnh âm đó có nằm "xa" đỉnh cần hỏi hay không.
Ba bẫy hay gặp: (1) tưởng "lazy deletion" (không xóa bản ghi cũ trong heap) tự động sửa được lỗi cạnh âm — nó chỉ tối ưu tốc độ, không đổi bản chất thuật toán tham lam; (2) quên rằng O((V+E)logV) chỉ đúng khi dùng heap, cài đặt bằng mảng tuyến tính là O(V2) (vẫn đúng, chỉ chậm hơn với đồ thị thưa); (3) thấy đề chỉ có MỘT cạnh âm "ở xa" rồi vẫn chủ quan dùng Dijkstra — phản ví dụ trên chỉ cần đúng một cạnh âm là đủ để sai.
Kỹ thuật sau không nằm trong yêu cầu chuẩn của lớp 12. Khi trọng số cạnh CHỈ nhận giá trị 0 hoặc 1, ta có thể thay hàng đợi ưu tiên (chi phí O(logV) mỗi thao tác) bằng một deque hai đầu: cạnh trọng số 0 thì đẩy đỉnh vào ĐẦU hàng đợi, cạnh trọng số 1 thì đẩy vào CUỐI. Vì hàng đợi luôn giữ thứ tự không giảm theo khoảng cách, ta không cần so sánh gì thêm — đạt O(V+E), nhanh hơn hẳn O((V+E)logV) của Dijkstra tổng quát.
from collections import deque
def zero_one_bfs(n, adj, src):
dist = [float('inf')] * n
dist[src] = 0
dq = deque([src])
while dq:
u = dq.popleft()
for v, w in adj[u]: # w chỉ là 0 hoặc 1
nd = dist[u] + w
if nd < dist[v]:
dist[v] = nd
(dq.appendleft if w == 0 else dq.append)(v)
return dist
Trên một đồ thị thử nghiệm 5 đỉnh S,A,B,C,D với các cạnh trọng số 0/1, zero_one_bfs và dijkstra cho ra CÙNG một mảng dist — như kỳ vọng, vì 0/1 vẫn là không âm, chỉ là 0-1 BFS khai thác cấu trúc đặc biệt để nhanh hơn.
Dijkstra tham lam đúng khi mọi trọng số ≥0: luôn chốt đỉnh gần nhất, dùng heapq để đạt O((V+E)logV), lưu mảng parent để truy vết đường đi. Khi có dù chỉ MỘT cạnh âm, thuật toán có thể chốt sai và không sửa lại được — Ví dụ 3 là mẫu phản chứng cần nhớ nằm lòng cho phòng thi. Khi trọng số chỉ 0/1, 0-1 BFS là một biến thể nhanh hơn đáng nhớ.
Bước tiếp theo: xử lý chính xác lớp đồ thị mà Dijkstra bó tay — đồ thị có cạnh trọng số âm.