Vấn đề tìm đường đi ngắn nhất trong đồ thị

Trong lý thuyết đồ thị, bài toán tìm đường đi ngắn nhất từ một nguồn đơn yêu cầu xác định một lộ trình giữa hai đỉnh sao cho tổng trọng số các cạnh trên lộ trình đó là nhỏ nhất. Cụ thể, cho một đồ thị có trọng số (gồm tập đỉnh V, tập cạnh E, và hàm trọng số thực f : E → R), và một đỉnh v trong V, mục tiêu là tìm đường đi P từ v đến mọi đỉnh v' trong V sao cho

$$

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

là nhỏ nhất trong số tất cả các đường nối từ v đến v' . Bài toán tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh là một biến thể tương tự, yêu cầu tìm đường đi ngắn nhất cho mọi cặp đỉnh v và v' .

Các thuật toán chủ chốt để giải bài toán này bao gồm:

• Thuật toán Dijkstra — áp dụng cho bài toán nguồn đơn khi tất cả trọng số đều không âm. Nó có khả năng tính toán các đường đi ngắn nhất từ một đỉnh xuất phát s đến mọi đỉnh khác mà không làm tăng thời gian thực hiện.
• Thuật toán Bellman-Ford — xử lý bài toán nguồn đơn khi trọng số có thể là âm.
• Thuật toán tìm kiếm A* — giải bài toán nguồn đơn bằng cách sử dụng các heuristics để tăng tốc quá trình tìm kiếm.
• Thuật toán Floyd-Warshall — giải bài toán tìm đường đi ngắn nhất cho tất cả các cặp đỉnh.
• Thuật toán Johnson — giải bài toán tìm đường đi ngắn nhất cho mọi cặp đỉnh, có thể hiệu quả hơ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 cục bộ (trong trường hợp xấu nhất)

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

Trong lĩnh vực mạng và 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 so sánh với bài toán đường đi rộng nhất (widest path problem), ví dụ như tìm đường đi rộng nhất trong các đường đi ngắn nhất (độ trễ nhỏ nhất) hoặc tìm đường đi ngắn nhất trong các đường đi rộng nhất.

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, và Clifford Stein. Introduction to Algorithms, Phiên bản thứ hai. MIT Press và McGraw-Hill, 2001. ISBN 0-262-03293-7. Các chương 24: Đường đi ngắn nhất nguồn đơn, và 25: Đường đi ngắn nhất cho tất cả cặp đỉnh, trang 580–642.