Một số thuật toán tìm đường đi ngắn nhất trong đồ thị

Bài viết này giới thiệu một số thuật toán tìm đường đi ngắn nhất thông dụng, cách chúng hoạt động ở mức khái niệm, điểm mạnh – điểm yếu và khi nào nên dùng thuật toán nào.

Bài toán đường đi ngắn nhất là gì?

Bài toán đường đi ngắn nhất (Shortest Path) được phát biểu đơn giản như sau:

• Cho một đồ thị gồm các đỉnh (node) và cạnh (edge).
• Mỗi cạnh có thể có trọng số (weight) thể hiện chi phí, độ dài hoặc thời gian di chuyển.
• Cần tìm đường đi có tổng trọng số nhỏ nhất từ một đỉnh xuất phát đến đỉnh đích, hoặc đến tất cả các đỉnh khác.

Tùy vào điều kiện của đồ thị (có trọng số hay không, trọng số âm hay không, cần tìm đường cho một cặp đỉnh hay cho tất cả cặp đỉnh), sẽ có thuật toán phù hợp khác nhau.

BFS – Tìm đường đi ngắn nhất trên đồ thị không trọng số

Khi đồ thị không có trọng số, hoặc tất cả các cạnh được xem như có cùng chi phí, ta có thể sử dụng thuật toán tìm kiếm theo chiều rộng Breadth-First Search (BFS) để tìm đường đi ngắn nhất tính theo số cạnh.

Ý tưởng chính của BFS:

• Bắt đầu từ đỉnh nguồn, duyệt đồ thị theo từng “lớp” khoảng cách.
• Các đỉnh ở lớp thứ nhất là những đỉnh kề trực tiếp với nguồn, lớp thứ hai là những đỉnh cách nguồn hai cạnh, và cứ thế tiếp tục.
• Khi BFS gặp đỉnh đích lần đầu tiên, đường đi tìm được chính là đường đi ngắn nhất về số cạnh.

BFS rất phù hợp cho:

• Đồ thị không trọng số hoặc trọng số đồng nhất.
• Bài toán mê cung dạng lưới (mỗi bước di chuyển xem như một cạnh).
• Các bài toán cần đo “số bước tối thiểu” giữa hai trạng thái.

Dijkstra – Thuật toán kinh điển cho đồ thị có trọng số không âm

Dijkstra là một trong những thuật toán nổi tiếng nhất cho bài toán đường đi ngắn nhất. Thuật toán này áp dụng cho đồ thị có trọng số không âm, nghĩa là không có cạnh mang trọng số âm.

Ý tưởng khái quát:

• Khởi tạo khoảng cách từ đỉnh nguồn đến chính nó bằng 0, đến các đỉnh khác là vô cùng.
• Mỗi bước, chọn ra đỉnh chưa được “chốt” có khoảng cách tạm thời nhỏ nhất.
• Cố định khoảng cách đến đỉnh đó (coi như đã tối ưu), sau đó dùng nó để “relax” các cạnh kề, cập nhật khoảng cách tốt hơn nếu có.
• Lặp lại cho đến khi tất cả đỉnh được xét hoặc không còn đường đi tốt hơn.

Dijkstra phù hợp cho:

• Đường đi ngắn nhất trên bản đồ (khoảng cách, thời gian, chi phí) khi tất cả chi phí đều không âm.
• Định tuyến mạng, tìm đường trong game, tối ưu hóa đường đi trong hệ thống logistic.

Hạn chế: Dijkstra không xử lý được đồ thị có cạnh trọng số âm. Trong trường hợp đó, cần thuật toán khác.

Bellman–Ford – Xử lý được trọng số âm

Bellman–Ford là thuật toán xử lý được các đồ thị có cạnh mang trọng số âm, miễn là không tồn tại chu trình âm (negative cycle) có thể làm cho tổng chi phí giảm vô hạn.

Ý tưởng chính:

• Khởi tạo khoảng cách như Dijkstra: nguồn là 0, các đỉnh khác là vô cùng.
• Thực hiện lặp nhiều lần, mỗi lần duyệt qua tất cả các cạnh và cố gắng “relax” chúng.
• Sau tối đa V - 1 lần lặp (V là số đỉnh), nếu không còn cải thiện, ta đã tìm được khoảng cách ngắn nhất.
• Nếu sau đó vẫn còn cạnh có thể giảm khoảng cách, chứng tỏ có chu trình âm.

Khi nên dùng Bellman–Ford:

• Khi đồ thị có cạnh mang trọng số âm.
• Khi cần vừa tìm đường đi ngắn nhất, vừa kiểm tra xem có tồn tại chu trình âm hay không.

Đổi lại, Bellman–Ford có độ phức tạp cao hơn Dijkstra, nên không phù hợp với đồ thị rất lớn nếu không cần xử lý trọng số âm.

Floyd–Warshall – Tìm đường đi ngắn nhất cho mọi cặp đỉnh

Các thuật toán như BFS, Dijkstra, Bellman–Ford thường được sử dụng khi cần tìm đường đi từ một nguồn tới một hoặc nhiều đích. Khi cần tìm đường đi ngắn nhất giữa mọi cặp đỉnh trong đồ thị, thuật toán Floyd–Warshall là lựa chọn kinh điển.

Ý tưởng chính:

• Khởi tạo ma trận khoảng cách, trong đó dist[i][j] là trọng số cạnh từ i đến j (hoặc vô cùng nếu không có cạnh).
• Duyệt lần lượt từng đỉnh k làm “trung gian”.
• Với mỗi cặp (i, j), kiểm tra xem đường đi qua k có ngắn hơn đường đi hiện tại hay không:
  nếu dist[i][k] + dist[k][j] < dist[i][j] thì cập nhật.
• Sau khi duyệt xong, ta có đường đi ngắn nhất giữa mọi cặp đỉnh.

Floyd–Warshall phù hợp khi:

• Số lượng đỉnh không quá lớn.
• Cần truy vấn khoảng cách giữa nhiều cặp đỉnh lặp đi lặp lại.
• Cần xử lý đồ thị có trọng số âm nhưng không có chu trình âm.

A* – Tìm đường hiệu quả với heuristic

A* (A star) là thuật toán dùng nhiều trong game, bản đồ và các bài toán tìm đường trên không gian hai hoặc ba chiều. Nó là một biến thể thông minh của Dijkstra, kết hợp thêm hàm heuristic để “đoán” đỉnh nào có khả năng dẫn đến đích nhanh hơn.

Ý tưởng khái quát:

• Mỗi đỉnh có hai giá trị: chi phí đã đi từ nguồn đến đó và ước lượng chi phí từ đó đến đích.
• Tổng hai giá trị này dùng để ưu tiên đỉnh nào được xét trước.
• Heuristic tốt (ví dụ, khoảng cách Euclid hoặc Manhattan trên bản đồ) giúp A* tìm đường nhanh hơn Dijkstra trên nhiều trường hợp.

A* phù hợp cho:

• Game 2D/3D cần tìm đường giữa hai vị trí.
• Ứng dụng bản đồ, điều hướng, mô phỏng giao thông.
• Các bài toán tìm đường trên lưới hoặc không gian có thể định nghĩa heuristic rõ ràng.

So sánh nhanh và cách chọn thuật toán

Tùy vào đặc điểm bài toán, có thể chọn thuật toán khác nhau:

• BFS: Đồ thị không trọng số, cần đường đi ngắn nhất theo số cạnh.
• Dijkstra: Đồ thị có trọng số không âm, cần đường đi ngắn nhất từ một nguồn đến nhiều đích.
• Bellman–Ford: Đồ thị có trọng số âm, cần phát hiện chu trình âm và đường đi ngắn nhất.
• Floyd–Warshall: Cần khoảng cách ngắn nhất giữa mọi cặp đỉnh, đồ thị không quá lớn.
• A*: Bài toán tìm đường trên không gian hình học với heuristic tốt, cần hiệu năng cao.

Ứng dụng thực tế của các thuật toán đường đi ngắn nhất

Một vài ví dụ ứng dụng:

• Hệ thống bản đồ: Tìm lộ trình giữa hai địa điểm, tối ưu theo quãng đường hoặc thời gian.
• Định tuyến mạng: Tính đường đi tối ưu cho gói tin qua các router.
• Game: Điều khiển NPC tìm đường quanh chướng ngại vật đến mục tiêu.
• Tối ưu vận tải: Xác định tuyến đường giao hàng với chi phí thấp.
• Phân tích đồ thị: Đo “khoảng cách” giữa các nút trong mạng xã hội hoặc hệ thống liên kết.

Kết luận

Thuật toán tìm đường đi ngắn nhất là nền tảng cho rất nhiều bài toán thực tế trong lập trình và khoa học dữ liệu. Việc hiểu rõ từng thuật toán – BFS, Dijkstra, Bellman–Ford, Floyd–Warshall, A* – giúp bạn chọn đúng công cụ cho đúng bối cảnh, cân bằng giữa độ chính xác và hiệu năng.

Khi nắm vững các ý tưởng cốt lõi, bạn có thể dễ dàng triển khai chúng trong nhiều ngôn ngữ lập trình, tùy chỉnh thêm logic và áp dụng cho những bài toán phức tạp hơn trong thực tế.