Bài toán đường đi ngắn nhất

Trong lý thuyết đồ thị, bài toán đường đi ngắn nhất nguồn đơn là bài toán tìm một đường đi giữa hai đỉnh sao cho tổng các trọng số của các cạnh tạo nên đường đi đó là nhỏ nhất. Định nghĩa một cách hình thức, cho trước một đồ thị có trọng số (nghĩa là một tập đỉnh V, một tập cạnh E, và một hàm trong số có giá trị thực f : E → R), cho trước một đỉnh v thuộc V, tìm một đường đi P từ v tới mỗi đỉnh v' thuộc V sao cho

${\displaystyle \sum _{p\in P}f(p)}$

là nhỏ nhất trong tất cả các đường nối từ v tới v' . Bài toán đường đi ngắn nhất giữa mọi cặp đỉnh là một bài toán tương tự, trong đó ta phải tìm các đường đi ngắn nhất cho mọi cặp đỉnh v và v' .

Các thuật toán quan trọng nhất giải quyết bài toán này là:

• Thuật toán Dijkstra — giải bài toán nguồn đơn nếu tất cả các trọng số đều không âm. Thuật toán này có thể tính toán tất cả các đường đi ngắn nhất từ một đỉnh xuất phát cho trước s tới mọi đỉnh khác mà không làm tăng thời gian chạy.
• Thuật toán Bellman-Ford — giải bài toán nguồn đơn trong trường hợp trọng số có thể có giá trị âm.
• Giải thuật tìm kiếm A* giải bài toán nguồn đơn sử dụng heuristics để tăng tốc độ tìm kiếm
• Thuật toán Floyd-Warshall — giải bài toán đường đi ngắn nhất cho mọi cặp đỉnh.
• Thuật toán Johnson — giải bài toán đường đi ngắn nhất cho mọi cặp đỉnh, có thể nhanh hơn thuật toán Floyd-Warshall trên các đồ thị thưa.
• Lý thuyết nhiễu (Perturbation theory); tìm đường đi ngắn nhất địa phương (trong trường hợp xấu nhất)

Một bài toán có liên quan là bài toán người bán hàng - bài toán tìm đường đi ngắn nhất đi qua tất cả các đỉnh, mỗi đỉnh đúng một lần, và trở về đỉnh xuất phát. Đây là bài toán NP-đầy đủ, do đó khó có khả năng tồn tại một cách giải hiệu quả.

Trong tư duy của ngành mạng hay viễn thông, bài toán đường đi ngắn nhất đôi khi được gọi là bài toán đường đi có độ trễ nhỏ nhất (min-delay path problem) và thường được gắn với một bài toán đường đi rộng nhất (widest path problem). ví dụ đường đi rộng nhất trong các đường đi ngắn nhất (độ trễ nhỏ nhất) hay đường đi ngắn nhất trong các đường đi rộng nhất.

Tham khảo

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapters 24: Single-Source Shortest Paths, and 25: All-Pairs Shortest Paths, pp. 580–642.