Thuật toán đường đi ngắn nhất (Shortest Path Algorithm)
1. Tổng quan
A. Định nghĩa
Thuật toán đường đi ngắn nhất (Shortest Path Algorithm) là tên gọi chung của các thuật toán tìm, trong số nhiều đường đi nối đỉnh xuất phát và đỉnh đích trên một đồ thị có trọng số, đường đi có tổng trọng số cạnh nhỏ nhất. Nó được phân thành các bài toán Nguồn đơn (Single-Source), Cặp đơn (Single-Pair) và Toàn cặp (All-Pairs), và được cài đặt trên hai chiến lược thiết kế: Tham lam (Greedy) và Quy hoạch động (DP).
Bài toán đường đi ngắn nhất là sự trừu tượng hóa toán học của câu hỏi phổ quát "con đường rẻ nhất để đi từ A đến B là gì?". Ở đây "sự rẻ" có thể là bất kỳ thước đo nào — khoảng cách, thời gian, chi phí, độ trễ, độ tin cậy — và một khi bản đồ, mạng đường bộ, mạng truyền thông và luồng quy trình được mô hình hóa bằng đỉnh (node) và cạnh có trọng số (weighted edge) thì chúng được giải bằng cùng một thuật toán. Hướng dẫn lộ trình điều hướng, quyết định đường đi trong các giao thức định tuyến Internet, di chuyển của nhân vật trò chơi và tối ưu giao hàng logistics đều là các biến thể của một bài toán này, vì vậy đường đi ngắn nhất được xem là chủ đề có giá trị thực tiễn lớn nhất trong lý thuyết đồ thị.
Nguyên lý cốt lõi của thuật toán đường đi ngắn nhất là cấu trúc con tối ưu (optimal substructure) và nới lỏng (relaxation). Cấu trúc con tối ưu là tính chất "bất kỳ đoạn trung gian nào nằm trong đường đi ngắn nhất từ nguồn đến đích tự nó cũng là đường đi ngắn nhất", nghĩa là lời giải của bài toán lớn được cấu thành từ lời giải của các bài toán nhỏ. Nới lỏng là phép toán "cập nhật ước lượng khoảng cách đến một đỉnh đích đã biết cho đến nay mỗi khi phát hiện một đường đi ngắn hơn", và mọi thuật toán đường đi ngắn nhất rốt cuộc được phân biệt bởi thứ tự và số lần thực hiện nới lỏng. Khi hai nguyên lý này được cài đặt qua các chiến lược khác nhau là Tham lam (một khi đã chốt thì không quay lại) và DP (cập nhật mọi trường hợp một cách hệ thống), đặc tính và ràng buộc của từng thuật toán phân hóa.
B. Bối cảnh ra đời và sự cần thiết
Với đồ thị không trọng số, chỉ riêng tìm kiếm theo chiều rộng (BFS) đã có thể tìm đường đi ngắn nhất theo số cạnh. Tuy nhiên mạng kết nối thực tế có khoảng cách, thời gian tiêu tốn, phí đường bộ và độ trễ đường truyền khác nhau ở từng đoạn, nên trọng số là không thể thiếu. Một con đường không nhanh chỉ vì nó đi qua ít đỉnh hơn, bởi một cạnh có thể lớn hơn tổng của hàng chục cạnh khác. Ở điểm này BFS bộc lộ giới hạn, và cần một thuật toán chuyên dụng so sánh và nới lỏng chi phí tích lũy có xét trọng số.
Hơn nữa các bài toán thực tế có tính chất trọng số và dạng truy vấn đa dạng đến mức không một thuật toán đơn lẻ nào có thể bao phủ hết. Có trường hợp mọi trọng số đều dương như mạng đường bộ, nhưng cũng có trường hợp tồn tại trọng số âm (−) như giao dịch chênh lệch tỷ giá hay mạng chi phí có bao gồm trợ cấp. Có khi phải tìm một lần từ một điểm xuất phát đến mọi đích, có khi phải tính trước khoảng cách giữa mọi cặp đỉnh. Như vậy, vì thuật toán phù hợp thay đổi tùy theo "có cho phép cạnh âm hay không, có cần phát hiện chu trình âm hay không, truy vấn là nguồn đơn hay toàn cặp, đồ thị thưa hay đặc", nên Kỹ sư chuyên nghiệp phải nhận diện chính xác điều kiện của bài toán và có con mắt chọn đúng công cụ trong số Dijkstra, Bellman-Ford, Floyd-Warshall và A</strong>*.
2. Phân loại bài toán đường đi ngắn nhất và nguyên lý nới lỏng
Bài toán đường đi ngắn nhất được phân thành ba loại theo phạm vi truy vấn. Đường đi ngắn nhất nguồn đơn (SSSP) tìm khoảng cách ngắn nhất từ một đỉnh xuất phát đến tất cả các đỉnh còn lại, với Dijkstra và Bellman-Ford là tiêu biểu. Đường đi ngắn nhất cặp đơn chỉ yêu cầu một cặp xuất phát-đích cụ thể; vì lời giải tổng quát giống SSSP nên thường giải SSSP và kết thúc khi đến đích, hoặc dùng A* để tập trung tìm kiếm chỉ theo hướng đích. Đường đi ngắn nhất toàn cặp (APSP) tìm khoảng cách giữa mọi cặp đỉnh, với Floyd-Warshall là điển hình.
flowchart TB
ROOT["Thuật toán đường đi ngắn nhất"] --> SSSP["Nguồn đơn (SSSP)"]
ROOT --> APSP["Toàn cặp (APSP)"]
SSSP --> DIJ["Dijkstra (tham lam, không cạnh âm)"]
SSSP --> BF["Bellman-Ford (DP, phát hiện cạnh/chu trình âm)"]
SSSP --> ASTAR["A* (tập trung vào đích dựa trên heuristic)"]
APSP --> FW["Floyd-Warshall (DP, toàn cặp)"]
APSP --> JOHN["Johnson (APSP cho đồ thị thưa)"]
Cùng với phân loại này, cũng cần lưu ý rằng nếu đồ thị hoàn toàn không có trọng số (hoặc mọi cạnh có cùng chi phí) thì các thuật toán trên là không cần thiết. Trong trường hợp đó tìm kiếm theo chiều rộng (BFS) cung cấp đường đi ngắn nhất theo số cạnh trong O(V+E), nên thuật toán có trọng số chỉ được biện minh "khi mỗi cạnh có chi phí khác nhau". Trong thực tế cũng xuất hiện các biến thể "trộn lẫn cạnh khoảng cách 1 và cạnh có trọng số" (0-1 BFS, rút gọn Dijkstra), nhưng nắm chính xác cấu trúc trọng số của bài toán và chọn công cụ đơn giản nhất mà vẫn đúng là điểm xuất phát để tránh thiết kế thừa.
Phép toán chung xuyên suốt mọi thuật toán là nới lỏng cạnh (Edge Relaxation). Mỗi đỉnh v có khoảng cách ngắn nhất tạm thời dist[v] từ nguồn, ban đầu chỉ riêng nguồn là 0, phần còn lại là vô cùng (∞). Gọi trọng số cạnh (u, v) là w, nới lỏng là phép so sánh-cập nhật đơn giản: "nếu dist[u] + w < dist[v] thì giảm dist[v] xuống dist[u] + w và ghi lại đỉnh tiền nhiệm của v là u." Nếu ghi lại cả đỉnh tiền nhiệm thì sau khi đến nơi có thể truy ngược để khôi phục cả đường đi thực tế. Rốt cuộc Dijkstra là thứ tự tham lam "tăng dần tập đỉnh đã chốt khoảng cách từng đỉnh một và chỉ nới lỏng xung quanh chúng", Bellman-Ford là thứ tự vét cạn "nới lỏng lặp lại mọi cạnh V−1 lần", và Floyd-Warshall là thứ tự DP "mở rộng tập đỉnh trung gian được phép đi qua từng đỉnh một và nới lỏng mọi cặp"; theo nghĩa đó, ba thuật toán có thể hiểu là các biến tấu thực hiện cùng một phép nới lỏng theo các lịch khác nhau.
flowchart LR
U["đỉnh u: dist=5"] -- "w=3" --> V["đỉnh v: dist=10"]
V --> CHK{"dist[u]+w = 8 có nhỏ hơn dist[v] = 10 không?"}
CHK -->|"Có"| UPD["cập nhật dist[v]=8, prev[v]=u"]
CHK -->|"Không"| KEEP["không cập nhật, giữ đường đi hiện có"]
3. Dựa trên tham lam: Thuật toán Dijkstra
Thuật toán Dijkstra, do Edsger Dijkstra đề xuất năm 1959, là thuật toán đường đi ngắn nhất nguồn đơn hoạt động trên đồ thị mà mọi trọng số cạnh đều không âm (0 trở lên). Chiến lược cốt lõi là tham lam. Nó lặp lại, cho đến khi mọi đỉnh được chốt, quá trình "chọn một đỉnh chưa chốt có khoảng cách tạm thời từ nguồn nhỏ nhất, chốt khoảng cách đó, và nới lỏng các cạnh kề với đỉnh đó."
Lý do lựa chọn tham lam này đúng nằm ở tiền đề trọng số không âm. Xét đỉnh u có khoảng cách tạm thời nhỏ nhất trong các đỉnh hiện chưa chốt; để một đường đi khác đến u ngắn hơn, đường đó tất yếu phải đi qua một đỉnh nào đó có khoảng cách tạm thời lớn hơn u. Thế nhưng vì trọng số cạnh không âm, đi vòng qua một đỉnh xa hơn rồi quay về u thì khoảng cách không bao giờ giảm. Do đó khoảng cách tạm thời hiện tại của u đã là khoảng cách ngắn nhất cuối cùng, và đỉnh một khi đã chốt thì không cần cập nhật lại nữa. Chính việc "không ngoái lại" này tạo ra hiệu quả của tham lam, nhưng đồng thời cũng là cội nguồn của giới hạn chí mạng: nó cho đáp án sai khi gặp cạnh âm vì tiền đề bị phá vỡ. Nếu có cạnh âm thì đường đi "đi vòng xa hơn rồi giảm khoảng cách bằng cạnh âm" trở nên khả dĩ, nên giá trị đã chốt có thể bị sai.
Vì sao Dijkstra sai với cạnh âm được xác nhận bằng một phản ví dụ đơn giản. Giả sử với các đỉnh S·A·B, các cạnh là S→A=1, S→B=4, A→B=−3. Ở bước đầu Dijkstra chốt S rồi cố chốt A (1), có khoảng cách tạm thời nhỏ hơn, trước B (4); nhưng trước đó khoảng cách tạm thời của B đã được đặt là dist[B]=4. Sau đó khi chốt A và nới lỏng A→B thì B lẽ ra phải được cập nhật thành 1+(−3)=−2, thế nhưng nếu thứ tự đã chốt B trước A thì đường ngắn hơn này bị bỏ lỡ. Thực tế trong các đồ thị phức tạp hơn, phát sinh tình huống một cạnh âm về sau còn giảm thêm "đỉnh đã lỡ chốt", khiến giá trị đã chốt bị sai — đây là lý do căn bản tuyệt đối không được dùng cạnh âm với Dijkstra. Nhân tiện, ý tưởng "sao không cứ cộng một hằng số lớn vào mọi trọng số để chúng thành dương?" là sai, bởi mỗi đường đi chứa số cạnh khác nhau nên lượng hằng số được cộng vào khác nhau, làm thay đổi thứ hạng của các đường đi ngắn nhất.
Hãy theo dõi hoạt động cụ thể bằng một ví dụ nhỏ. Xét các đỉnh S (nguồn)·A·B·C·T (đích) với các cạnh S→A=4, S→B=1, B→A=2, B→C=5, A→C=1, C→T=3. Ban đầu dist[S]=0, phần còn lại là ∞. Ở bước đầu ta chốt S (0), có khoảng cách tạm thời nhỏ nhất, và nới lỏng các cạnh của S cho ra dist[A]=4, dist[B]=1. Tiếp theo ta chốt B (1), nhỏ nhất trong các đỉnh chưa chốt, và nới lỏng cho ra, qua B→A, 1+2=3 < 4 nên dist[A]=3 giảm, và qua B→C, dist[C]=6. Rồi chốt A (3) và qua A→C, 3+1=4 < 6 nên dist[C]=4 được cập nhật. Sau đó chốt C (4), qua C→T ta được dist[T]=7, và chốt T (7) cuối cùng thì kết thúc. Đường đi ngắn nhất được khôi phục bằng cách truy ngược mảng tiền nhiệm thành S→B→A→C→T (chi phí 7). Như ví dụ cho thấy, một đỉnh đã chốt (S·B·A·C) không bao giờ giảm nữa sau đó, và bất biến này chống đỡ cho tính đúng đắn của tham lam.
Hiệu năng phụ thuộc vào cấu trúc dữ liệu tìm đỉnh có khoảng cách nhỏ nhất trong các đỉnh chưa chốt. Mảng đơn giản quét tuyến tính mỗi lần cho O(V²), còn dùng hàng đợi ưu tiên (heap nhỏ nhất, Min-Heap) xử lý mỗi lần cập nhật khoảng cách ở nới lỏng trong O(log V), cải thiện toàn cục thành O((V + E) log V). Trong đồ thị thưa (sparse graph) nhiều đỉnh nhưng ít cạnh, cách dựa trên heap có lợi lớn, còn trong đồ thị đặc (dense graph) số cạnh gần bình phương số đỉnh, mảng đơn giản có khi lại tốt hơn. Dùng heap Fibonacci hạ về lý thuyết O(E + V log V) nhưng hằng số lớn khiến heap nhị phân là chuẩn trong thực tế. Trong cài đặt dựa trên heap, một đỉnh có thể vào hàng đợi nhiều lần, và cách "xóa trễ (lazy deletion)" — bỏ qua một đỉnh đã chốt khi nó lại bị lấy ra khỏi hàng đợi — được dùng rộng rãi vì cài đặt đơn giản.
Ứng dụng công nghiệp tiêu biểu là giao thức định tuyến OSPF (Open Shortest Path First). OSPF theo cách trạng thái liên kết (Link-State) để mỗi router chia sẻ toàn bộ topo mạng rồi chạy Dijkstra (SPF, Shortest Path First) với chính nó làm gốc để tính đường tối ưu đến từng đích. Ví dụ, bằng cách quy đổi băng thông đường truyền thành chi phí (cost) và gán chi phí cho liên kết 100 Mbps cao hơn liên kết 1 Gbps, ta có thể khiến Dijkstra tự nhiên ưu tiên các đường băng thông lớn. Điều hướng cũng áp dụng họ Dijkstra với thời gian đi qua đoạn đường làm trọng số, nhưng vì mạng đường bộ toàn quốc có hàng chục triệu đỉnh và Dijkstra thuần túy chậm, nên được tăng tốc bằng A* hay các kỹ thuật tiền xử lý được nêu dưới đây.
4. Dựa trên quy hoạch động: Bellman-Ford và Floyd-Warshall
Thuật toán Bellman-Ford cho phép cạnh âm mà Dijkstra đã từ bỏ. Chiến lược là vét cạn: nó "lặp lại V−1 lần công việc nới lỏng mỗi cạnh của đồ thị một lần." Vì đường đi ngắn nhất không chứa chu trình nên nó gồm tối đa V−1 cạnh; bởi mỗi lượt (pass) chắc chắn nới lỏng được ít nhất một cạnh của đường đi ngắn nhất, nên sau V−1 lượt mọi khoảng cách ngắn nhất hội tụ. Độ phức tạp thời gian là O(V·E), chậm hơn Dijkstra, nhưng khác với tham lam không ngoái lại, nó nới lỏng lặp lại mọi cạnh nên thu được đáp án đúng ngay cả khi cạnh âm chen vào.
Vì sao V−1 lượt là đủ có thể hiểu qua tốc độ lan truyền của nới lỏng. Sau lượt thứ 1, khoảng cách ngắn nhất của mọi đỉnh đến được bằng 1 cạnh từ nguồn được chốt; sau lượt thứ 2, các đường đến được bằng 2 cạnh được chốt, và cứ thế, nên lượt thứ k bảo đảm "đường đi ngắn nhất dùng tối đa k cạnh." Vì không đường đi ngắn nhất nào vượt quá V−1 cạnh, toàn cục hội tụ trong V−1 lượt. Điều này cho thấy, khác với Dijkstra "chốt từng đỉnh một theo thứ tự khoảng cách", Bellman-Ford là DP "mở rộng độ dài đường (số cạnh) từng lớp một." Tuy vậy nếu thứ tự nới lỏng cạnh tốt thì nó hội tụ sớm hơn nhiều so với V−1 lượt, nên tối ưu kết thúc sớm (early termination) dừng ngay khi một lượt không có cập nhật nào thường được dùng.
Giá trị quyết định khác của Bellman-Ford là phát hiện chu trình âm (negative cycle). Nếu sau V−1 lần lặp, nới lỏng cạnh thêm một lần nữa (lần thứ V) vẫn tìm thấy một cạnh có khoảng cách giảm, nghĩa là tồn tại một chu trình âm mà chi phí giảm càng đi vòng càng giảm. Trong trường hợp này đường đi ngắn nhất phân kỳ về âm vô cùng và không được định nghĩa, nên thuật toán báo cáo điều đó. Tính chất này được ứng dụng trực tiếp vào phát hiện chênh lệch giá tiền tệ (arbitrage) — đặt các đồng tiền làm đỉnh và logarit âm của tỷ giá làm trọng số cạnh, sự tồn tại của chu trình âm nghĩa là "một cơ hội giao dịch còn lại lợi nhuận sau khi đi hết một vòng." Trong định tuyến, RIP (Routing Information Protocol) áp dụng nguyên lý Bellman-Ford một cách phân tán theo cách vector khoảng cách (Distance-Vector); vì chỉ các router láng giềng trao đổi thông tin đường đi nên hội tụ chậm và có vấn đề "đếm tới vô cùng (count-to-infinity)", nên bị giới hạn ở mạng nhỏ bằng cách chặn số bước nhảy ở 15.
Nhìn kỹ hơn một chút cách vector khoảng cách của RIP sẽ lộ ra bản chất phân tán của Bellman-Ford. Mỗi router, không biết toàn bộ bản đồ, cập nhật bảng định tuyến của mình bằng "khoảng cách theo từng đích mà router láng giềng kết nối trực tiếp báo về cộng với chi phí giữa chính nó và láng giềng đó." Điều này giống như phân tán và thực hiện lặp lại phép nới lỏng của Bellman-Ford trên toàn mạng. Vấn đề là hiện tượng đếm tới vô cùng (count-to-infinity), khi một liên kết đứt, khoảng cách từ từ vọt lên vô cùng vì "một đường cũ mà láng giềng chưa biết lại được tham chiếu", và để giảm thiểu, các kỹ thuật bổ trợ như chặn số bước nhảy (15), chia tầm nhìn (split horizon) và đầu độc tuyến (route poisoning) được dùng. Điểm rằng một thuật toán lý thuyết, một khi đặt vào môi trường phân tán và động, lại làm nảy sinh thách thức mới về tính hội tụ, là một hiểu biết quan trọng từ góc nhìn Kỹ sư chuyên nghiệp.
Thuật toán Floyd-Warshall là kỹ thuật DP tìm khoảng cách ngắn nhất giữa mọi cặp đỉnh (APSP) cùng một lúc. Ý tưởng cốt lõi là "mở rộng tập đỉnh trung gian được phép quá cảnh từng đỉnh một." Ở bước thứ k, nó tìm khoảng cách ngắn nhất cho mọi cặp (i, j) "khi chỉ được dùng các đỉnh 1..k làm trung gian", với công thức truy hồi dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). Tức là nó chọn đường ngắn hơn giữa "đường hiện có không đi qua k" và "đường i→k→j đi qua k." Nó được cài đặt gọn gàng bằng vòng lặp ba lớp, với độ phức tạp O(V³). Nó cho phép cạnh âm nhưng phải không có chu trình âm, và nếu một phần tử đường chéo dist[i][i] trở nên âm thì một chu trình âm đã bị phát hiện. Nó đặc biệt phù hợp khi số đỉnh nhỏ, ở cỡ vài trăm, và cần khoảng cách toàn cặp (ví dụ: ma trận độ trễ của một mạng nhỏ, tính trước cho bản đồ trò chơi). Chẳng hạn, để tìm ma trận độ trễ giữa mọi điểm của một mạng nội bộ 300 đỉnh, thay vì lặp Dijkstra 300 lần (300×O((V+E)log V)), một vòng lặp ba lớp O(300³)=27 triệu phép tính có lợi hơn trong thực tế, vừa đơn giản cài đặt vừa tốt về tính cục bộ bộ nhớ đệm. Ngược lại, nếu cần APSP trên đồ thị thưa hàng triệu đỉnh thì V³ của Floyd-Warshall là quá mức, nên thuật toán Johnson, chạy Dijkstra từ mọi đỉnh nhưng loại bỏ cạnh âm bằng tái gán trọng số (reweighting), hiệu quả hơn.
So sánh: Dùng thuật toán nào khi nào
Việc lựa chọn giữa ba thuật toán được sắp xếp theo ba trục: "có tồn tại cạnh âm hay không, phạm vi truy vấn, và mật độ đồ thị." Bảng dưới tóm tắt các khác biệt, nhưng lý do chúng phát sinh bắt rễ từ nguyên lý thiết kế ở các mục trước.
| Phân loại | Dijkstra | Bellman-Ford | Floyd-Warshall |
|---|---|---|---|
| Chiến lược thiết kế | Tham lam | Quy hoạch động (lặp cạnh) | Quy hoạch động (mở rộng trung gian) |
| Phạm vi truy vấn | Nguồn đơn | Nguồn đơn | Toàn cặp |
| Cạnh âm | Không được | Được | Được (khi không có chu trình âm) |
| Phát hiện chu trình âm | Không thể | Có thể | Có thể |
| Độ phức tạp thời gian | O((V+E)log V) | O(V·E) | O(V³) |
| Tình huống phù hợp | Định tuyến quy mô lớn trọng số dương | Cạnh âm/chênh lệch giá/RIP | Khoảng cách toàn cặp quy mô nhỏ |
Hàm ý thực tiễn rất rõ ràng. Khi, như trong mạng đường bộ hay OSPF, trọng số luôn dương và phải trích xuất đường đi ở quy mô lớn từ một nguồn đơn, Dijkstra nhanh vượt trội. Mặt khác, khi chi phí bao gồm số âm hoặc bản thân chu trình âm là đối tượng phát hiện, phải dùng Bellman-Ford dù chậm hơn. Khi số đỉnh nhỏ và cần khoảng cách toàn cặp, Floyd-Warshall, đơn giản nhất về cài đặt, tốt hơn. Chọn Dijkstra chỉ dựa vào độ phức tạp rồi cho đáp án sai vì cạnh âm là một sai lầm thiết kế điển hình, và ngược lại dùng Floyd-Warshall trên đồ thị dương rồi trả giá V³ không cần thiết cũng là quá mức.
Tóm tắt mối quan hệ giữa ba thuật toán trong một câu: Dijkstra là "tham lam nhanh chuyên cho đồ thị dương", Bellman-Ford là "DP an toàn xử lý cả số âm", và Floyd-Warshall là "DP gọn gàng tìm mọi cặp cùng một lúc." Thay vì cạnh tranh, chúng là một bộ công cụ bổ trợ lẫn nhau mà vai trò được phân chia theo điều kiện bài toán, và các hệ thống thực tế thường kết hợp chúng. Ví dụ, một hệ thống định tuyến quy mô lớn có thể áp dụng thiết kế lai, thường ngày trích xuất đường đi nhanh bằng Dijkstra, nhưng chỉ áp dụng Bellman-Ford cho vùng mà trọng số thưởng/chiết khấu tương ứng với số âm theo chính sách được đưa vào.
5. Chuyên sâu: Tìm kiếm heuristic A* và tăng tốc tìm đường quy mô lớn
Trong tìm đường thời gian thực quy mô lớn, ngay cả Dijkstra thuần túy cũng chậm. Vì Dijkstra chốt khoảng cách về mọi hướng lấy nguồn làm tâm bất kể hướng của đích, nó tìm cả những đỉnh ở phía đối diện một cách không cần thiết ngay cả khi đích ở một phía. Thuật toán A* (A-star) thêm vào đây một hàm ước lượng heuristic h(n) để dẫn dắt nó "ưu tiên tìm các đỉnh trông gần đích." A* đánh giá độ ưu tiên của mỗi đỉnh bằng f(n) = g(n) + h(n), trong đó g(n) là khoảng cách thực sự tích lũy từ nguồn đến n, và h(n) là khoảng cách ước lượng từ n đến đích (ví dụ: khoảng cách đường thẳng trên tọa độ bản đồ). Nếu h(n) thỏa điều kiện chấp nhận được (admissible) là không bao giờ đánh giá quá mức khoảng cách thực, A* bảo đảm lời giải tối ưu y hệt Dijkstra trong khi thu hẹp phạm vi tìm kiếm về phía đích, khiến nó nhanh hơn nhiều. Đặt h(n)=0 thì A* chính xác trở thành Dijkstra, nên có thể xem A* là sự tổng quát hóa của Dijkstra.
A* là chuẩn trên thực tế cho tìm đường của AI trò chơi (pathfinding) và lập kế hoạch đường đi của robot. Khi di chuyển một đơn vị đến điểm mục tiêu trên bản đồ lưới (grid), dùng khoảng cách đường thẳng (Euclid) hoặc khoảng cách lưới (Manhattan) làm heuristic cho phép di chuyển thời gian thực bằng cách chỉ mở rộng một số nhỏ nút ngay cả trên bản đồ hàng triệu ô. Tuy nhiên nếu heuristic đánh giá quá mức thì mất tính tối ưu, và nếu bản thân việc tính heuristic đắt đỏ thì lợi ích bị triệt tiêu, nên thiết kế của h(n) chi phối hiệu năng.
Hãy ước lượng hiệu quả của heuristic bằng con số. Trên bản đồ lưới 1.000×1.000 với nguồn và đích ở hai đầu bản đồ, Dijkstra có thể chốt hàng trăm nghìn ô, lan ra như những vòng tròn đồng tâm lấy nguồn làm tâm. Ngược lại, A* dùng khoảng cách Manhattan làm heuristic tập trung tìm kiếm vào một dải hẹp hướng về đích và, trên bản đồ ít chướng ngại, tìm được cùng đường đi tối ưu trong khi chỉ mở rộng ở mức vài nghìn ô tỉ lệ với độ dài đường đi. Càng nhiều chướng ngại, khiến "ước lượng đường thẳng" của heuristic lệch nhiều so với khoảng cách đi vòng thực tế, thì lợi thế của A* càng giảm và tiến gần Dijkstra — điều này minh họa rõ nguyên lý rằng tính thông tin (informedness) của heuristic càng cao thì tìm kiếm càng hiệu quả. Trong các trò chơi mà tính thời gian thực là tuyệt đối, Weighted A* — thêm trọng số vào heuristic để cho ra đường "đủ tốt" nhanh hơn thay vì tối ưu hoàn toàn — cũng được dùng, đây là một đánh đổi điển hình mua thời gian phản hồi bằng cách nhượng bộ một phần tính tối ưu.
Mạng đường bộ hàng chục triệu đỉnh, như điều hướng toàn quốc, không đủ chỉ với A* và dùng tăng tốc dựa trên tiền xử lý. Tiêu biểu, Phân cấp co rút (Contraction Hierarchies) loại bỏ trước các đỉnh ít quan trọng trong khi thêm các cạnh tắt để xây cấu trúc phân cấp, và tại thời điểm truy vấn tính đường toàn quốc trong vài mili-giây bằng tìm kiếm hai chiều. Một kỹ thuật khác, tìm kiếm hai chiều (bidirectional search), tiến hành tìm kiếm đồng thời từ nguồn và đích để chúng gặp nhau ở giữa, giảm vùng mà tìm kiếm lan ra còn khoảng một nửa trở xuống — nếu tìm kiếm một chiều khám phá một vòng tròn bán kính r thì hai chiều khám phá hai vòng tròn bán kính r/2, nên diện tích giảm mạnh. Hơn nữa, vì điều hướng thực tế là môi trường trọng số động nơi trọng số thay đổi thường xuyên theo lưu lượng, các kỹ thuật tính lại khoảng cách định kỳ để phản ánh thông tin giao thông thời gian thực hoặc cập nhật tăng dần chỉ các đoạn bị ảnh hưởng được kết hợp. Luồng mở rộng như vậy — "thuật toán đường đi ngắn nhất tĩnh → heuristic → tiền xử lý → cập nhật động" — cho thấy công nghệ đường đi ngắn nhất là một lĩnh vực không ngừng tiến bộ vượt ra ngoài thuật toán giáo khoa.
6. Điểm cần cân nhắc và hàm ý
Khi thiết kế và áp dụng thuật toán đường đi ngắn nhất từ góc nhìn Kỹ sư chuyên nghiệp, cần cân nhắc tổng hợp những điều sau.
Trước hết cố định tính chất của trọng số rồi chọn thuật toán. Nếu mọi cạnh đều dương thì Dijkstra tốt nhất, nhưng nếu tồn tại dù chỉ một cạnh âm thì Dijkstra cho đáp án sai, nên phải chuyển sang Bellman-Ford hoặc Floyd-Warshall. Ở giai đoạn phân tích yêu cầu phải nhận diện không thiếu sót "chi phí có thể âm hay không, phát hiện chu trình âm có phải mục tiêu hay không", và bỏ qua điều này sẽ sản xuất hàng loạt kết quả sai trông như đúng.
Điều chỉnh cấu trúc dữ liệu và độ phức tạp theo phạm vi truy vấn và mật độ đồ thị. Dijkstra dựa trên heap (O((V+E)log V)) phù hợp nguồn đơn, đồ thị thưa; Floyd-Warshall (O(V³)) phù hợp toàn cặp, đồ thị đặc nhỏ; và Johnson phù hợp toàn cặp, đồ thị thưa lớn. Nếu truy vấn thường xuyên và đồ thị tĩnh thì chiến lược trả chi phí tiền xử lý (Phân cấp co rút) để tăng tốc truy vấn là hữu hiệu.
Đưa việc khôi phục đường đi thực tế và xử lý đồng hạng (tie) vào thiết kế. Không chỉ giá trị khoảng cách mà cả mảng tiền nhiệm (prev) cũng phải được duy trì mới truy ngược được bản thân đường đi. Hơn nữa, khi tồn tại nhiều đường cùng khoảng cách ngắn nhất, việc nêu rõ quy tắc phá vỡ đồng hạng về việc chọn đường nào (số cạnh nhỏ nhất, một độ ưu tiên cụ thể, v.v.) mới cho kết quả có thể tái lập.
Cân nhắc tính hội tụ và khả năng mở rộng của môi trường động/phân tán. Trong môi trường mà topo và trọng số thay đổi như định tuyến, chi phí tính lại toàn bộ và độ trễ hội tụ trở thành vấn đề. Trạng thái liên kết (OSPF, thông tin toàn cục + Dijkstra) hội tụ nhanh nhưng tải chia sẻ thông tin lớn, còn vector khoảng cách (RIP, thông tin cục bộ + Bellman-Ford) đơn giản nhưng mang rủi ro đếm tới vô cùng và hội tụ chậm, nên phải chọn và phối hợp theo quy mô và độ biến động của mạng.
Quản lý đánh đổi giữa heuristic và xấp xỉ. Heuristic của A* tăng tốc độ lớn nhưng mất tính tối ưu nếu vi phạm điều kiện chấp nhận được. Trong các yêu cầu siêu lớn, thời gian thực, các kỹ thuật xấp xỉ/tiền xử lý nhượng bộ một chút lời giải tối ưu để bảo đảm thời gian phản hồi có thể là hợp lý, nên cần phán đoán điều chỉnh đánh đổi "độ chính xác và khả năng phản hồi" theo mức yêu cầu dịch vụ (SLA).
Kiểm tra tính ổn định số và các cạm bẫy cài đặt. Khi biểu diễn vô cùng (∞) bằng một số nguyên rất lớn, hãy đặt một giới hạn để
∞ + wkhông tràn trong quá trình nới lỏng, và cảnh giác với sai lầm điển hình dùng Dijkstra khi có cạnh âm, hoặc sai thứ tự lặp của Floyd-Warshall (k phải là vòng lặp ngoài cùng). Vì một lỗi cài đặt nhỏ có thể tạo ra đường "có vẻ hợp lý nhưng sai" dẫn đến sự cố vận hành, hãy đưa việc kiểm thử các trường hợp biên (đỉnh không đến được, chu trình tự thân, nhiều đường cùng chi phí) vào thiết kế.Tận dụng liên kết với các bài toán đồ thị lân cận. Đường đi ngắn nhất chia sẻ nguyên lý thiết kế với các bài toán đồ thị khác như cây khung nhỏ nhất (MST), luồng cực đại (Max-Flow) và sắp xếp topo, và thường được kết hợp với chúng. Ví dụ, trong một DAG (đồ thị có hướng không chu trình), chỉ nới lỏng một lần theo thứ tự sắp xếp topo đã tìm được đường đi ngắn nhất — bao gồm cả cạnh âm — trong O(V+E), nên nắm đặc tính cấu trúc của đồ thị cho phép áp dụng một lời giải chuyên biệt nhanh hơn thuật toán tổng quát. Năng lực mô hình hóa quy về (reduction) bài toán thành đường đi ngắn nhất để giải cũng quan trọng.
Tóm lại, thuật toán đường đi ngắn nhất, trên các nguyên lý chung là nới lỏng và cấu trúc con tối ưu, tách thành tham lam (Dijkstra) và DP (Bellman-Ford·Floyd-Warshall), được bổ sung thêm heuristic (A*) và tiền xử lý/cập nhật động, tạo thành một công nghệ nền tảng chống đỡ cho định tuyến, điều hướng, trò chơi và logistics nói chung. Kỹ sư chuyên nghiệp phải chẩn đoán chính xác điều kiện của bài toán (tính chất trọng số, phạm vi truy vấn, quy mô đồ thị, độ biến động) và có năng lực lựa chọn, kết hợp đúng thuật toán và chiến lược tăng tốc tại điểm cân bằng giữa độ chính xác, hiệu năng và khả năng mở rộng.
Tài liệu tham khảo
- E. W. Dijkstra, "A note on two problems in connexion with graphs", Numerische Mathematik, 1959. https://link.springer.com/article/10.1007/BF01386390
- P. E. Hart, N. J. Nilsson, B. Raphael, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths", IEEE Transactions on Systems Science and Cybernetics, 1968. https://ieeexplore.ieee.org/document/4082128
- RFC 2328, "OSPF Version 2". https://www.rfc-editor.org/rfc/rfc2328
- RFC 2453, "RIP Version 2". https://www.rfc-editor.org/rfc/rfc2453
Tóm tắt một câu: Thuật toán đường đi ngắn nhất, trên cơ sở nới lỏng và cấu trúc con tối ưu, chia thành Dijkstra tham lam (mạnh cho nguồn đơn trên đồ thị dương), Bellman-Ford DP (xử lý cạnh/chu trình âm), Floyd-Warshall (tìm mọi cặp) và A* (tập trung tìm kiếm vào đích qua một heuristic), và điều cốt lõi là chẩn đoán tính chất trọng số, phạm vi truy vấn và quy mô đồ thị rồi lựa chọn/tăng tốc tại điểm cân bằng giữa độ chính xác và hiệu năng.