Đăng nhập để tham gia lộ trình luyện tập

Lộ trình Đường đi ngắn nhất – Shortest Paths

Đường đi ngắn nhất là một trong những chủ đề nền tảng và quan trọng nhất của thuật toán đồ thị. Các bài toán thuộc nhóm này xuất hiện thường xuyên trong HSG Tin học, Olympic Tin học, ICPC và Competitive Programming.

Mục tiêu của lộ trình không chỉ là ghi nhớ cách cài đặt các thuật toán, mà quan trọng hơn là hình thành khả năng:

• Nhận ra một bài toán có thể mô hình hóa thành đồ thị.
• Xác định đúng đỉnh, cạnh và trạng thái.
• Phân tích đặc điểm trọng số cạnh.
• Chọn đúng thuật toán đường đi ngắn nhất.
• Biết khi nào nên dùng BFS, 0-1 BFS hoặc Dijkstra.
• Biết xử lý cạnh âm bằng Bellman–Ford.
• Biết giải bài toán mọi cặp đỉnh bằng Floyd–Warshall hoặc Johnson.
• Khôi phục đường đi tối ưu.
• Phát hiện và xử lý chu trình âm.
• Mô hình hóa các bài toán trạng thái phức tạp thành bài toán đường đi ngắn nhất.

---

1. Kiến thức tiên quyết

Trước khi bắt đầu lộ trình, người học nên nắm được:

• Khái niệm đỉnh và cạnh.
• Đồ thị có hướng và đồ thị vô hướng.
• Đồ thị có trọng số và không trọng số.
• Biểu diễn đồ thị bằng danh sách kề.
• BFS.
• DFS.
• Queue.
• Deque.
• Priority Queue / Heap.
• Độ phức tạp thuật toán.
• Ký hiệu Big-O.
• Kiểu dữ liệu số nguyên lớn và vấn đề tràn số.

---

2. Nền tảng bài toán đường đi ngắn nhất

Cho đồ thị $G=(V,E)$.

Với hai đỉnh $s$ và $t$, một đường đi từ $s$ tới $t$ có dạng:

$$s=v_0,v_1,v_2,\ldots,v_k=t$$

Nếu mỗi cạnh $(u,v)$ có trọng số $w(u,v)$ thì độ dài của đường đi là:

$$\sum_{i=0}^{k-1} w(v_i,v_{i+1})$$

Khoảng cách ngắn nhất từ $s$ tới $t$ được ký hiệu là:

$$d(s,t)$$

và được định nghĩa là tổng trọng số nhỏ nhất trong tất cả các đường đi từ $s$ tới $t$.

Nếu không tồn tại đường đi từ $s$ tới $t$, ta có thể xem:

$$d(s,t)=+\infty$$

Các mô hình cơ bản cần phân biệt:

• Single-Pair Shortest Path: một nguồn, một đích.
• Single-Source Shortest Paths: một nguồn, mọi đỉnh.
• Multi-Source Shortest Paths: nhiều nguồn.
• All-Pairs Shortest Paths: mọi cặp đỉnh.

---

3. BFS – Đường đi ngắn nhất trên đồ thị không trọng số

Nếu đồ thị không có trọng số, hoặc mọi cạnh có cùng chi phí, BFS là thuật toán tự nhiên nhất.

Đặt:

$$dist[s]=0$$

Khi từ đỉnh $u$ lần đầu tiên đi tới đỉnh $v$:

$$dist[v]=dist[u]+1$$

BFS duyệt đồ thị theo từng lớp khoảng cách nên lần đầu tiên một đỉnh được thăm chính là lúc tìm được số cạnh ít nhất để đi tới đỉnh đó.

Độ phức tạp:

$$O(V+E)$$

Các dạng cần luyện:

• Đường đi ngắn nhất trên đồ thị không trọng số.
• Đường đi ngắn nhất trên lưới.
• Mê cung.
• Khôi phục đường đi.
• BFS nhiều nguồn.
• BFS trên đồ thị ẩn.
• BFS với trạng thái mở rộng.

Phản xạ cần hình thành:

Đồ thị không trọng số $\Rightarrow$ nghĩ tới BFS trước tiên.

---

4. Multi-Source BFS

Trong một số bài toán có nhiều đỉnh xuất phát cùng lúc.

Thay vì chạy BFS riêng từ từng nguồn, ta đưa tất cả các nguồn vào queue ngay từ đầu.

Với mọi nguồn $s_i$:

$$dist[s_i]=0$$

Sau đó thực hiện BFS như bình thường.

Kết quả:

$$dist[v] = \min_i d(s_i,v)$$

Tức là khoảng cách từ $v$ tới nguồn gần nhất.

Độ phức tạp vẫn là:

$$O(V+E)$$

Các dạng thường gặp:

• Khoảng cách tới bệnh viện gần nhất.
• Khoảng cách tới ô nguy hiểm gần nhất.
• Lửa lan.
• Virus lan.
• Nhiều điểm xuất phát đồng thời.
• Tìm nguồn gần nhất.

---

5. BFS trên đồ thị trạng thái

Trong nhiều bài toán, một vị trí vật lý chưa đủ để mô tả trạng thái.

Ví dụ trạng thái có thể là:

$$(v,k)$$

trong đó:

• $v$ là đỉnh hiện tại;
• $k$ là số quyền đặc biệt đã sử dụng.

Hoặc trên lưới:

$$(x,y,k)$$

Khi đó mỗi trạng thái được xem như một đỉnh của một đồ thị mới.

Ví dụ:

• Vị trí hiện tại.
• Đã lấy chìa khóa hay chưa.
• Đã phá bao nhiêu bức tường.
• Đã sử dụng phép dịch chuyển hay chưa.
• Trạng thái chẵn/lẻ.
• Số bước modulo $K$.

Đây là một trong những kỹ năng mô hình hóa quan trọng nhất của Shortest Path.

---

6. 0-1 BFS

Nếu mọi cạnh chỉ có trọng số:

$$w(u,v)\in\{0,1\}$$

ta có thể sử dụng 0-1 BFS thay cho Dijkstra.

Sử dụng deque.

Khi relaxation cạnh $(u,v)$:

$$dist[v] > dist[u] + w(u,v)$$

thì cập nhật:

$$dist[v] = dist[u]+w(u,v)$$

Nếu:

$$w(u,v)=0$$

thì đưa $v$ vào đầu deque.

Nếu:

$$w(u,v)=1$$

thì đưa $v$ vào cuối deque.

Độ phức tạp:

$$O(V+E)$$

Các dạng cần luyện:

• Chi phí bằng $0$ hoặc $1$.
• Đổi hướng mất phí.
• Edge reversal.
• Teleport miễn phí.
• Phá tường.
• Dùng hoặc không dùng một thao tác.
• Grid có hai loại chi phí.
• Đồ thị trạng thái có trọng số nhị phân.

Phản xạ cần hình thành:

Trọng số chỉ gồm $0$ và $1$ $\Rightarrow$ nghĩ tới 0-1 BFS.

---

7. Dijkstra cơ bản

Dijkstra giải bài toán Single-Source Shortest Paths khi mọi cạnh có trọng số không âm:

$$w(u,v)\ge 0$$

Ta duy trì:

$$dist[v]$$

là khoảng cách tốt nhất hiện biết từ nguồn $s$ tới $v$.

Khởi tạo:

$$dist[s]=0$$

và với mọi $v\ne s$:

$$dist[v]=+\infty$$

Với cạnh:

$$u\rightarrow v$$

có trọng số $w$, ta thực hiện relaxation nếu:

$$dist[v] > dist[u]+w$$

Khi đó:

$$dist[v] = dist[u]+w$$

Với danh sách kề và Binary Heap / Priority Queue, độ phức tạp thường được viết là:

$$O((V+E)\log V)$$

Với đồ thị liên thông đủ lớn, thường có thể rút gọn cách viết thành:

$$O(E\log V)$$

Các dạng cơ bản:

• Một nguồn, một đích.
• Một nguồn, mọi đỉnh.
• Đồ thị vô hướng.
• Đồ thị có hướng.
• Khôi phục đường đi.
• Nhiều cạnh giữa cùng hai đỉnh.
• Đỉnh không thể tới được.

Phản xạ cần hình thành:

Trọng số không âm $\Rightarrow$ nghĩ tới Dijkstra.

---

8. Vì sao Dijkstra không dùng được với cạnh âm?

Giả sử một đỉnh $u$ đã được Dijkstra xem là có khoảng cách tối ưu.

Nếu tồn tại cạnh âm, một đường đi được phát hiện sau đó vẫn có thể làm giảm khoảng cách của $u$.

Điều này phá vỡ tính chất tham lam của Dijkstra.

Vì vậy:

$$w(u,v)<0$$

là dấu hiệu phải đặc biệt cẩn thận.

Có cạnh âm không có nghĩa là bài toán không giải được, nhưng Dijkstra thông thường không còn bảo đảm đúng.

---

9. Dijkstra nâng cao – Đồ thị trạng thái

Một trong những dạng quan trọng nhất trong Competitive Programming là mở rộng mỗi đỉnh thành nhiều trạng thái.

Ví dụ:

$$dist[v][k]$$

có thể biểu diễn chi phí nhỏ nhất để tới đỉnh $v$ sau khi đã sử dụng $k$ quyền đặc biệt.

Nếu được dùng tối đa $K$ lần, số trạng thái có thể lên tới:

$$V(K+1)$$

Các dạng cần luyện:

• Một lần giảm giá.
• Một cạnh miễn phí.
• Tối đa $K$ lần sử dụng phép đặc biệt.
• Vé giao thông.
• Nhiên liệu.
• Số lần đổi phương tiện.
• Trạng thái chẵn/lẻ.
• Trạng thái modulo.
• Product Graph.
• Layered Graph.

---

10. Multi-Source Dijkstra

Nếu có nhiều nguồn:

$$S=\{s_1,s_2,\ldots,s_k\}$$

ta đặt:

$$dist[s_i]=0$$

cho mọi $i$, rồi đưa toàn bộ các nguồn vào Priority Queue.

Khi thuật toán kết thúc:

$$dist[v] = \min_{1\le i\le k} d(s_i,v)$$

Đây là phiên bản có trọng số của Multi-Source BFS.

---

11. Khôi phục đường đi ngắn nhất

Ngoài mảng khoảng cách, lưu thêm:

$$parent[v]$$

Khi relaxation từ $u$ sang $v$ thành công:

$$parent[v]=u$$

Sau khi tìm được đích $t$, lần lượt đi:

$$t,\ parent[t],\ parent[parent[t]],\ldots$$

cho tới nguồn $s$.

Sau đó đảo ngược dãy để thu được đường đi từ $s$ tới $t$.

---

12. Shortest Path DAG

Sau khi đã biết khoảng cách ngắn nhất từ nguồn, một cạnh:

$$u\rightarrow v$$

có trọng số $w(u,v)$ nằm trên một đường đi ngắn nhất nếu:

$$dist[u]+w(u,v)=dist[v]$$

Các cạnh thỏa điều kiện trên tạo thành cấu trúc Shortest Path Graph.

Trong nhiều trường hợp, cấu trúc này có thể tiếp tục được sử dụng để:

• Đếm số đường đi ngắn nhất.
• Tìm số cạnh ít nhất.
• Tìm số cạnh nhiều nhất.
• Xác định cạnh nằm trên đường đi ngắn nhất.
• Xác định đỉnh nằm trên đường đi ngắn nhất.
• Thực hiện DP trên các đường đi tối ưu.

---

13. Đếm số đường đi ngắn nhất

Ngoài:

$$dist[v]$$

ta có thể duy trì:

$$ways[v]$$

là số đường đi ngắn nhất tới $v$.

Nếu tìm được khoảng cách tốt hơn:

$$dist[v] > dist[u]+w$$

thì:

$$dist[v]=dist[u]+w$$

và:

$$ways[v]=ways[u]$$

Nếu tìm được một đường đi khác có cùng khoảng cách:

$$dist[v]=dist[u]+w$$

thì:

$$ways[v] = ways[v]+ways[u]$$

Nếu đề yêu cầu modulo $M$, ta thực hiện:

$$ways[v] = (ways[v]+ways[u])\bmod M$$

---

14. Bellman–Ford

Bellman–Ford có thể xử lý đồ thị chứa cạnh có trọng số âm.

Thuật toán dựa hoàn toàn trên phép relaxation.

Với mỗi cạnh:

$$u\rightarrow v$$

có trọng số $w(u,v)$, kiểm tra:

$$dist[v] > dist[u]+w(u,v)$$

Nếu đúng:

$$dist[v] = dist[u]+w(u,v)$$

Nếu đồ thị không chứa chu trình âm có thể đạt được từ nguồn, một đường đi ngắn nhất đơn không cần chứa quá:

$$V-1$$

cạnh.

Vì vậy Bellman–Ford thực hiện tối đa $V-1$ lượt relaxation trên toàn bộ các cạnh.

Độ phức tạp:

$$O(VE)$$

Các dạng cần luyện:

• Cạnh âm.
• Shortest Path có trọng số âm.
• Phát hiện chu trình âm.
• Khôi phục chu trình âm.
• Xác định đỉnh bị chu trình âm ảnh hưởng.

---

15. Phát hiện chu trình âm

Sau $V-1$ lượt relaxation, thực hiện thêm một lượt.

Nếu vẫn tồn tại cạnh:

$$u\rightarrow v$$

sao cho:

$$dist[v] > dist[u]+w(u,v)$$

thì tồn tại chu trình âm có thể đạt được từ nguồn.

Một chu trình:

$$v_0\rightarrow v_1\rightarrow\cdots\rightarrow v_k=v_0$$

là chu trình âm nếu:

$$\sum_{i=0}^{k-1} w(v_i,v_{i+1})<0$$

Nếu có thể đi tới chu trình âm và sau đó đi tới đích, chi phí có thể giảm vô hạn.

Khi đó có thể xem khoảng cách tối ưu là:

$$-\infty$$

Cần phân biệt rõ:

• Chu trình âm tồn tại ở đâu đó trong đồ thị.
• Chu trình âm có thể đạt được từ nguồn.
• Chu trình âm có thể ảnh hưởng tới đích đang xét.

---

16. Shortest Path trên DAG

Nếu đồ thị là DAG, ta không cần Dijkstra ngay cả khi có cạnh âm.

Ta thực hiện:

1. Topological Sort.
2. Duyệt các đỉnh theo thứ tự topo.
3. Relax các cạnh đi ra.

Độ phức tạp:

$$O(V+E)$$

Đây là trường hợp đặc biệt rất quan trọng.

Phản xạ cần hình thành:

Đồ thị DAG $\Rightarrow$ nghĩ tới Topological Order + Relaxation.

---

17. Floyd–Warshall

Floyd–Warshall giải bài toán All-Pairs Shortest Paths.

Đặt:

$$dist[i][j]$$

là khoảng cách tốt nhất hiện biết từ $i$ tới $j$.

Ban đầu:

$$dist[i][i]=0$$

Với mỗi cạnh:

$$i\rightarrow j$$

có trọng số $w(i,j)$:

$$dist[i][j] = \min(dist[i][j],w(i,j))$$

Xét lần lượt các đỉnh trung gian $k$.

Công thức chuyển:

$$dist[i][j] = \min \left( dist[i][j], dist[i][k]+dist[k][j] \right)$$

Độ phức tạp thời gian:

$$O(V^3)$$

Độ phức tạp bộ nhớ:

$$O(V^2)$$

Các dạng cần luyện:

• Khoảng cách giữa mọi cặp đỉnh.
• Rất nhiều truy vấn khoảng cách.
• Khôi phục đường đi.
• Phát hiện chu trình âm.
• Transitive Closure.
• Minimax Path.
• Các biến thể DP trên đỉnh trung gian.

Điểm quan trọng:

Không nên chỉ học thuộc ba vòng lặp. Cần hiểu Floyd–Warshall là một bài toán quy hoạch động.

---

18. Chu trình âm với Floyd–Warshall

Sau khi chạy Floyd–Warshall, nếu:

$$dist[v][v]<0$$

thì tồn tại một chu trình âm liên quan tới đỉnh $v$.

Điều này xuất phát từ việc một đường đi từ $v$ quay trở lại chính $v$ có tổng trọng số âm.

---

19. Johnson Algorithm

Johnson giải bài toán All-Pairs Shortest Paths trên đồ thị thưa có thể chứa cạnh âm nhưng không được chứa chu trình âm.

Thuật toán kết hợp:

• Bellman–Ford.
• Reweighting.
• Dijkstra.

Bước 1 – Thêm siêu nguồn

Thêm một đỉnh mới $q$.

Với mọi đỉnh $v$ của đồ thị, thêm cạnh:

$$q\rightarrow v$$

có trọng số:

$$0$$

---

Bước 2 – Chạy Bellman–Ford

Chạy Bellman–Ford từ $q$.

Đặt:

$$h(v)=d(q,v)$$

Nếu Bellman–Ford phát hiện chu trình âm thì Johnson không thể tiếp tục.

---

Bước 3 – Reweight cạnh

Với mỗi cạnh:

$$u\rightarrow v$$

có trọng số ban đầu $w(u,v)$, định nghĩa trọng số mới:

$$w'(u,v) = w(u,v)+h(u)-h(v)$$

Nhờ tính chất của Bellman–Ford:

$$h(v)\le h(u)+w(u,v)$$

suy ra:

$$w(u,v)+h(u)-h(v)\ge 0$$

do đó:

$$w'(u,v)\ge 0$$

Toàn bộ cạnh sau khi reweight đều không âm.

---

Bước 4 – Chạy Dijkstra

Sau khi mọi trọng số đã không âm, chạy Dijkstra từ từng đỉnh $s$.

Gọi khoảng cách trên đồ thị đã reweight là:

$$d'(u,v)$$

---

Bước 5 – Khôi phục khoảng cách ban đầu

Khoảng cách thật trên đồ thị ban đầu là:

$$d(u,v) = d'(u,v)-h(u)+h(v)$$

Đây là công thức quan trọng cần nhớ của Johnson.

---

Độ phức tạp Johnson

Bellman–Ford cần:

$$O(VE)$$

Chạy Dijkstra từ mỗi trong $V$ đỉnh với Binary Heap cần tổng cộng:

$$O\left(V(V+E)\log V\right)$$

Do đó tổng độ phức tạp có thể viết là:

$$O\left(VE+V(V+E)\log V\right)$$

Với đồ thị thưa, Johnson thường hiệu quả hơn Floyd–Warshall.

---

20. So sánh Floyd–Warshall và Johnson

Floyd–Warshall

Độ phức tạp:

$$O(V^3)$$

Phù hợp khi:

• $V$ không quá lớn.
• Đồ thị tương đối dày.
• Có rất nhiều truy vấn.
• Cần một cài đặt APSP đơn giản.

Johnson

Độ phức tạp với Binary Heap:

$$O\left(VE+V(V+E)\log V\right)$$

Phù hợp khi:

• Đồ thị thưa.
• $V$ lớn hơn.
• Có cạnh âm.
• Không tồn tại chu trình âm.

---

21. Bảng lựa chọn thuật toán

Đặc điểm đồ thị	Thuật toán nên nghĩ tới
Không trọng số	BFS
Mọi cạnh cùng chi phí dương	BFS
Trọng số chỉ là $0$ hoặc $1$	0-1 BFS
Trọng số không âm	Dijkstra
Có cạnh âm	Bellman–Ford
Cần phát hiện chu trình âm từ nguồn	Bellman–Ford
DAG	Topological Sort + Relaxation
All-Pairs, số đỉnh nhỏ	Floyd–Warshall
All-Pairs, đồ thị thưa, có cạnh âm	Johnson
Nhiều nguồn, không trọng số	Multi-Source BFS
Nhiều nguồn, trọng số không âm	Multi-Source Dijkstra

---

22. Quy trình nhận dạng thuật toán

Khi gặp một bài toán đường đi ngắn nhất, hãy lần lượt trả lời các câu hỏi sau.

Câu hỏi 1

Đồ thị có được cho trực tiếp hay phải tự mô hình hóa?

Câu hỏi 2

Trọng số cạnh thuộc loại nào?

• Không có trọng số.
• Chỉ có $0$ và $1$.
• Không âm.
• Có số âm.

Câu hỏi 3

Bài toán cần khoảng cách từ:

• Một nguồn tới một đích?
• Một nguồn tới mọi đỉnh?
• Nhiều nguồn?
• Mọi cặp đỉnh?

Câu hỏi 4

Đồ thị có cấu trúc đặc biệt không?

• DAG?
• Tree?
• Grid?
• Functional Graph?
• State Graph?

Câu hỏi 5

Có cần:

• Khôi phục đường đi?
• Đếm số đường đi?
• Tìm đường đi thứ hai?
• Tìm $K$ đường đi ngắn nhất?
• Phát hiện chu trình âm?

Câu hỏi 6

Giới hạn:

$$V=?$$

và:

$$E=?$$

Từ đó mới chọn thuật toán phù hợp.

---

23. Các biến thể Dijkstra quan trọng

Sau khi thành thạo Dijkstra cơ bản, cần luyện các dạng:

• Multi-Source Dijkstra.
• Dijkstra trên Grid.
• Dijkstra trên State Graph.
• Dijkstra với Coupon.
• Dijkstra với một cạnh miễn phí.
• Dijkstra với tối đa $K$ lần đặc quyền.
• Dijkstra với trạng thái modulo $K$.
• Dijkstra với trạng thái chẵn/lẻ.
• Dijkstra trên đồ thị đảo cạnh.
• Dijkstra hai chiều khoảng cách.
• Ghép khoảng cách từ nguồn và từ đích.
• Dijkstra trên Layered Graph.
• Dijkstra trên Product Graph.

---

24. Đường đi ngắn thứ hai

Một biến thể phổ biến là tìm đường đi ngắn thứ hai.

Thay vì chỉ lưu:

$$dist_1[v]$$

ta có thể lưu thêm:

$$dist_2[v]$$

với:

$$dist_1[v]\le dist_2[v]$$

Trong đó:

• $dist_1[v]$ là khoảng cách ngắn nhất;
• $dist_2[v]$ là khoảng cách ngắn thứ hai.

Dạng này yêu cầu xử lý relaxation cẩn thận hơn Dijkstra thông thường.

---

25. K đường đi ngắn nhất

Một mở rộng khác là tìm:

$$K$$

đường đi có chi phí nhỏ nhất.

Thay vì chỉ chấp nhận một lần lấy đỉnh khỏi Priority Queue, ta có thể cho phép một đỉnh được xử lý nhiều lần, nhưng giới hạn tối đa $K$ kết quả cần thiết.

Đây là nhóm bài nâng cao sau khi đã thành thạo Dijkstra.

---

26. Mô hình hóa bài toán thành Shortest Path

Đây là kỹ năng quan trọng hơn cả việc nhớ code.

Nếu bài toán yêu cầu:

Tìm chi phí nhỏ nhất để chuyển từ trạng thái ban đầu sang trạng thái đích.

hãy thử xây dựng:

• Mỗi trạng thái $\rightarrow$ một đỉnh.
• Mỗi thao tác hợp lệ $\rightarrow$ một cạnh.
• Chi phí thao tác $\rightarrow$ trọng số cạnh.

Sau đó bài toán trở thành:

$$\text{Minimum Cost} \quad\Longleftrightarrow\quad \text{Shortest Path}$$

Các mô hình thường gặp:

• Thành phố và đường.
• Mê cung.
• Grid.
• Chuyển đổi chuỗi.
• Trò chơi trạng thái.
• Teleport.
• Phương tiện giao thông.
• Vé.
• Nhiên liệu.
• Coupon.
• Công tắc.
• Đổi hướng.
• Layered Graph.
• Product Graph.

---

27. Các bài phối hợp nâng cao

Ở cấp độ cao hơn, Shortest Path thường được kết hợp với các kỹ thuật khác:

• Shortest Path + Dynamic Programming.
• Shortest Path + Bitmask.
• Shortest Path + Binary Search.
• Shortest Path + Greedy.
• Shortest Path + DAG.
• Shortest Path + SCC.
• Shortest Path + Tree.
• Shortest Path + Segment Tree.
• Shortest Path + Computational Geometry.
• Shortest Path + State Compression.
• Shortest Path trên Implicit Graph.

Đây là nhóm bài giúp chuyển từ mức biết thuật toán sang mức sử dụng thuật toán linh hoạt trong thi đấu.

---

28. Trình tự học khuyến nghị

Tầng 1 – Nền tảng

Graph Representation

↓

BFS cơ bản

↓

BFS Shortest Path

↓

Path Reconstruction

---

Tầng 2 – BFS nâng cao

Multi-Source BFS

↓

Grid BFS

↓

State-Space BFS

↓

Implicit Graph

---

Tầng 3 – Trọng số đặc biệt

0-1 BFS

↓

0-1 BFS trên Grid

↓

0-1 BFS trên State Graph

---

Tầng 4 – Dijkstra nền tảng

Dijkstra cơ bản

↓

Priority Queue

↓

Relaxation

↓

Path Reconstruction

---

Tầng 5 – Dijkstra nâng cao

Multi-Source Dijkstra

↓

State-Space Dijkstra

↓

Layered Graph

↓

Coupon / Special Edge

↓

Product Graph

---

Tầng 6 – Biến thể đường đi

Đếm số đường đi ngắn nhất

↓

Shortest Path DAG

↓

Second Shortest Path

↓

K Shortest Paths

---

Tầng 7 – Cạnh âm

Bellman–Ford

↓

Negative Edge

↓

Negative Cycle Detection

↓

Negative Cycle Reconstruction

---

Tầng 8 – Đồ thị đặc biệt

Shortest Path on DAG

↓

Topological Order + Relaxation

---

Tầng 9 – All-Pairs Shortest Paths

Floyd–Warshall

↓

Path Reconstruction

↓

Negative Cycle

↓

Floyd–Warshall Variants

---

Tầng 10 – Johnson

Bellman–Ford

↓

Potential Function

↓

Reweighting

↓

Dijkstra từ mọi đỉnh

↓

Johnson Algorithm

---

Tầng 11 – Mô hình hóa nâng cao

State Expansion

↓

Layered Graph

↓

Product Graph

↓

Implicit Graph

↓

Shortest Path Modeling

---

Tầng 12 – Bài phối hợp

Shortest Path + DP

↓

Shortest Path + Bitmask

↓

Shortest Path + Binary Search

↓

Shortest Path + SCC

↓

Shortest Path + Data Structures

---

29. Mục tiêu hoàn thành

Sau khi hoàn thành lộ trình, người học cần đạt được các năng lực sau:

• Nhận dạng được bài toán đường đi ngắn nhất ngay cả khi đề không nói trực tiếp về đồ thị.
• Mô hình hóa bài toán thành đỉnh, cạnh và trọng số.
• Chọn chính xác BFS, 0-1 BFS, Dijkstra, Bellman–Ford, DAG Shortest Path, Floyd–Warshall hoặc Johnson.
• Phân biệt rõ SSSP và APSP.
• Cài đặt ổn định các thuật toán.
• Khôi phục đường đi.
• Đếm số đường đi ngắn nhất.
• Xử lý trạng thái mở rộng.
• Phát hiện chu trình âm.
• Xử lý cạnh âm.
• Giải các bài Shortest Path nâng cao.
• Kết hợp Shortest Path với các kỹ thuật khác.

---

30. Phản xạ cần đạt được

Khi đọc đề, người học cần dần hình thành bảng phản xạ:

$$\text{Unweighted} \Rightarrow \text{BFS}$$ $$w\in\{0,1\} \Rightarrow \text{0-1 BFS}$$ $$w\ge 0 \Rightarrow \text{Dijkstra}$$ $$\text{Negative Edge} \Rightarrow \text{Bellman--Ford}$$$$\text{DAG} \Rightarrow \text{Topological Order + Relaxation}$$$$\text{APSP, small }V \Rightarrow \text{Floyd--Warshall}$$$$\text{APSP, sparse graph} \Rightarrow \text{Johnson}$$

Mục tiêu cuối cùng không phải là học thuộc code của từng thuật toán, mà là đạt được khả năng:

Đọc đề → mô hình hóa → phân tích trọng số → phân tích giới hạn → chọn đúng thuật toán → cài đặt chính xác.