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

Bài toán đường đi rộng nhất, còn gọi là bài toán đường đi nút cổ chai rộng nhất hay bài toán tìm đường đi có khả năng thông qua lớn nhất, là bài toán yêu cầu tìm đường đi giữa hai đỉnh trong đồ thị có hướng có trọng số sao cho trọng số của cung có trọng số nhỏ nhất là lớn nhất có thể.
Một ví dụ cụ thể là khi đồ thị biểu diễn mạng lưới các bộ định tuyến trên mạng internet, và trọng số của các cung là băng thông của cáp nối giữa hai bộ định tuyến. Bài toán đường đi rộng nhất tương ứng với tìm đường đi giữa hai bộ định tuyến cho trước với băng thông lớn nhất có thể. Chiều rộng của cung hẹp nhất được gọi là khả năng thông qua hay băng thông của đường đi. Ngoài ứng dụng trong định tuyến trên mạng, bài toán đường đi rộng nhất còn là một thành phần quan trọng của phương pháp Schulze cho việc xác định người thắng cuộc trong bầu cử nhiều ứng cử viên, và có ứng dụng trong tổng hợp số, phân tích sự trao đổi chất, và trong thuật toán tìm luồng cực đại. Hầu hết các thuật toán tìm đường đi ngắn nhất đều có thể được sửa đổi để tính đường đi rộng nhất thay vì đường đi ngắn nhất. Tuy nhiên, trong nhiều trường hợp, có những thuật toán nhanh hơn để tính đường đi rộng nhất.
Một bài toán liên quan mang tên bài toán đường đi minimax yêu cầu tìm đường đi sao cho trọng số lớn nhất trên đường là nhỏ nhất có thể. Bất kì thuật toán tìm đường đi rộng nhất nào cũng đều có thể được dùng để tìm đường đi minimax và ngược lại, bằng cách đảo ngược tất cả các phép so sánh của thuật toán hoặc thay mọi trọng số bằng số đối của chúng.

Đồ thị vô hướng

Trong đồ thị vô hướng, đường đi rộng nhất giữa hai đỉnh chính là đường đi giữa chúng trên cây bao trùm lớn nhất của đồ thị, và đường đi minimax giữa hai đỉnh chính là đường đi trên cây bao trùm nhỏ nhất.
Trong bất kì đồ thị nào, dù có hướng hay vô hướng, đều có thể áp dụng thuật toán đơn giản sau để tìm đường đi rộng nhất sau khi đã biết trọng số nhỏ nhất trên đường đi đó: xóa tất cả các cung có trọng số nhỏ hơn và tìm đường đi trên các cung còn lại bằng tìm kiếm theo chiều rộng hoặc tìm kiếm theo chiều sâu. Dựa trên ý tưởng này, có thể xây dựng một thuật toán chạy trong thời gian tuyến tính để tìm đường đi rộng nhất từ s đến t mà không cần đến cây bao trùm lớn nhất. Ý tưởng chính của thuật toán là tìm trọng số trung vị trong đồ thị, rồi kiểm tra xem có tồn tại đường đi rộng hơn giá trị trung vị hay không theo phương pháp trên. Nếu đường đi tồn tại, thì xóa hết các cung nhỏ hơn giá trị trung vị. Nếu đường đi không tồn tại, thì hợp mỗi thành phần liên thông tạo bởi các cung lớn hơn lại thành một đỉnh. Trong cả hai trường hợp, thuật toán tiếp tục trên đồ thị nhỏ hơn mới thu được.

Đồ thị có hướng

Có nhiều thuật toán khác nhau cho đồ thị có hướng, tùy theo nhu cầu sử dụng chẳng hạn như đỉnh xuất phát hay kết thúc có cố định hay không, và có cần tìm đường cho nhiều cặp đỉnh cùng một lúc hay không.

Mọi cặp đỉnh

Bài toán đường đi rộng nhất giữa mọi cặp đỉnh có ứng dụng trong phương pháp Schulze để xác định người thắng cuộc trong bầu cử với nhiều ứng cử viên trong đó trên mỗi phiếu, các ứng cử viên được xếp hạng theo thứ tự ưu tiên. Phương pháp Schulze xây dựng một đồ thị đấu loại trong đó mỗi đỉnh biểu diễn một ứng cử viên và hai đỉnh bất kì đều được nối với nhau bằng 1 cung. Mỗi cung có hướng từ người thắng cuộc đến người thua cuộc trong cuộc đấu tay đôi giữa hai ứng viên ở hai đầu của cung, và được gắn nhãn bằng chênh lệch giữa hai người. Sau đó, tính đường đi rộng nhất giữa mọi cặp đỉnh của đồ thị và người thắng cuộc là ứng cử viên có đường đi tới mỗi đối thủ rộng hơn đường đi rộng nhất theo hướng ngược lại. Kết quả của phương pháp này tương thích với phương pháp Condorcet - nếu một ứng cử viên thắng trong tất cả các kết quả so sánh tay đôi thi người đó thắng chung cuộc - nhưng nó cũng cho phép lựa chọn người thắng cuộc trong nhiều trường hợp khi phương pháp Condorcet thất bại. Phương pháp Schulze đã được sử dụng bởi nhiều tổ chức, chẳng hạn như Wikimedia Foundation.
Để tính chiều rộng của đường đi rộng nhất giữa mọi cặp đỉnh trong đồ thị trù mật có hướng, chẳng hạn như đồ thị thu được trong ứng dụng bầu cử, thuật toán nhanh nhất hiện nay chạy trong thời gian O(n) trong đó ω là lũy thừa trong thời gian chạy của thuật toán nhân ma trận nhanh. Nếu sử dụng thuật toán nhân ma trận nhanh nhất hiện nay, thì độ phức tạp trên trở thành O(n2.688). Thay vào đó, cách lập trình thông thường của phương pháp Schulze sử dụng một phiên bản của thuật toán Floyd-Warshall chạy trong thời gian O(n³). Trên đồ thị thưa, có thể việc chạy thuật toán tìm đường đi rộng nhất với đỉnh nguồn cố định nhiều lần còn hiệu quả hơn các phương pháp trên.

Một đỉnh nguồn cố định

Nếu độ dài các cạnh đã được sắp xếp thì có thể sử dụng một biến thể của thuật toán Dijkstra để tìm các đường đi rộng nhất từ một đỉnh nguồn cố định tới tất cả các đỉnh khác trong thời gian tuyến tính. Ý tưởng chính ở đây là trong bài toán đường đi rộng nhất, thứ tự các đỉnh được xem xét trong thuật toán chính là một dãy con tăng dần của danh sách các cung sắp xếp theo trọng số. Do đó hàng đợi ưu tiên của thuật toán Dijkstra trong trường hợp này có thể thay bằng một mảng kích thước m lưu trữ các cung của đồ thị theo trọng số tăng dần. Phương pháp này cho phép tìm kiếm đường đi rộng nhất trong thời gian ngang với thời gian sắp xếp. Nếu các trọng số là số nguyên thì thuật toán có cùng thời gian chạy với thuật toán sắp xếp số nguyên.

Một nguồn và một đích

Có thể tìm đường đi rộng nhất cho một đỉnh nguồn và một đỉnh đích duy nhất một cách hiệu quả ngay cả trong mô hình chỉ cho phép so sánh trọng số của các cung mà không được tính toán trên chúng. Thuật toán duy trì một tập hợp các cung S sao cho các cung trên đường đi rộng nhất chắc chắn nằm trong S. Ban đầu, S chứa tất cả m cung của đồ thị. Trong mỗi lượt, thuật toán chia tập S thành một danh sách các tập con được sắp thứ tự S₁, S₂,... (các số trong tập trước nhỏ hơn hoặc bằng các số trong tập sau) có kích thước xấp xỉ nhau. Số lượng tập hợp con được chọn sao cho các giá trị để phân chia S thành các tập con có thể được xác định bằng cách lặp đi lặp lại việc tìm phần tử trung vị trong thời gian O(m). Sau đó, thuật toán thay trọng số của các cung trên đồ thị bằng số thứ tự của tập chứa nó. Do ta đã có danh sách các cung sắp xếp theo trọng số mới, có thể tìm đường đi rộng nhất trong thời gian tuyến tính theo kết quả ở trên và do đó xác định được cung hẹp nhất của đường đi nằm trong tập nào. Sau đó, thuật toán thay tập S bằng tập Sᵢ đã được xác định là chứa cung hẹp nhất trên đường, và lặp lại các bước trên. Số lượng tập hợp mà ta có thể chia S tăng theo hàm mũ sau mỗi lần lặp nên số lần lặp là O(log*n). Tổng thời gian, do đó, là O(m log*n). Khi các trọng số là số nguyên, bước lặp đi lặp lại việc tìm kiếm trung vị có thể thay bằng kĩ thuật phân chia danh sách bởi Han & Thorup (2002), cho phép chia S thành O(\sqrt{m}) tập con Sᵢ trong một bước và toàn bộ thuật toán chạy trong thời gian tuyến tính.