Đường dẫn ngắn nhất DSA

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

Bài toán đường đi ngắn nhất nổi tiếng trong lĩnh vực khoa học máy tính.

Để giải bài toán đường đi ngắn nhất có nghĩa là tìm đường đi hoặc đường đi ngắn nhất có thể giữa hai đỉnh (hoặc nút) trong Đồ thị.

Trong bài toán đường đi ngắn nhất, Biểu đồ có thể biểu thị bất kỳ thứ gì từ mạng đường bộ đến mạng truyền thông, trong đó các đỉnh có thể là giao lộ, thành phố hoặc bộ định tuyến và các cạnh có thể là đường, đường bay hoặc liên kết dữ liệu.

Đường đi ngắn nhất từ ​​đỉnh D đến đỉnh F trong Biểu đồ trên là D->E->C->F, với tổng trọng lượng đường đi là 2+4+4=10. Các đường đi khác từ D đến F cũng có thể, nhưng chúng có tổng trọng số cao hơn nên không thể coi là đường đi ngắn nhất.

Lời giải cho bài toán đường đi ngắn nhất

Thuật toán Dijkstra và thuật toán Bellman-Ford tìm đường đi ngắn nhất từ ​​một đỉnh bắt đầu đến tất cả các đỉnh khác.

Để giải bài toán đường đi ngắn nhất có nghĩa là kiểm tra các cạnh bên trong Biểu đồ cho đến khi chúng ta tìm thấy đường dẫn mà chúng ta có thể di chuyển từ đỉnh này sang đỉnh khác bằng cách sử dụng trọng số kết hợp thấp nhất có thể dọc theo các cạnh.

Tổng trọng số dọc theo các cạnh tạo nên đường dẫn được gọi là chi phí đường dẫn hoặc trọng số đường dẫn .

Các thuật toán tìm đường đi ngắn nhất, như thuật toán Dijkstra hoặc thuật toán Bellman-Ford , tìm đường đi ngắn nhất từ ​​một đỉnh bắt đầu đến tất cả các đỉnh khác.

Để bắt đầu, các thuật toán đặt khoảng cách từ đỉnh bắt đầu đến tất cả các đỉnh là dài vô hạn. Và khi thuật toán chạy, các cạnh giữa các đỉnh được kiểm tra lặp đi lặp lại và các đường đi ngắn hơn có thể được tìm thấy nhiều lần cho đến khi tìm thấy đường đi ngắn nhất ở cuối.

Mỗi khi một cạnh được kiểm tra và dẫn đến khoảng cách ngắn hơn đến một đỉnh được tìm thấy và cập nhật, nó được gọi là thư giãn hoặc thư giãn một cạnh.

Trọng số cạnh dương và âm

Một số thuật toán tìm đường đi ngắn nhất, như thuật toán Dijkstra , chỉ có thể tìm đường đi ngắn nhất trong đồ thị có tất cả các cạnh đều dương. Những đồ thị có khoảng cách dương như vậy cũng dễ hiểu nhất vì chúng ta có thể coi các cạnh giữa các đỉnh là khoảng cách giữa các vị trí.

Nếu chúng ta hiểu trọng số cạnh là số tiền bị mất khi đi từ đỉnh này sang đỉnh khác, thì trọng số cạnh dương là 4 từ đỉnh A đến C trong biểu đồ trên có nghĩa là chúng ta phải chi 4 USD để đi từ A đến C.

Nhưng đồ thị cũng có thể có các cạnh âm và đối với những đồ thị như vậy , thuật toán Bellman-Ford có thể được sử dụng để tìm đường đi ngắn nhất.

Và tương tự, nếu trọng số của cạnh biểu thị số tiền bị mất thì trọng số cạnh âm -3 từ đỉnh C đến A trong biểu đồ trên có thể được hiểu là cạnh có thể kiếm được nhiều tiền hơn số tiền bị mất khi đi từ C đến A. Vì vậy, ví dụ: nếu chi phí nhiên liệu là 5 đô la khi đi từ C đến A và chúng tôi được trả 8 đô la để nhận các gói hàng ở C và giao chúng ở A, thì số tiền lỗ là -3, nghĩa là chúng tôi thực sự kiếm được tổng cộng 3 đô la.

Chu kỳ âm trong bài toán đường đi ngắn nhất

Việc tìm đường đi ngắn nhất trở nên bất khả thi nếu đồ thị có chu trình âm.

Có một chu trình âm có nghĩa là có một đường đi mà bạn có thể đi theo vòng tròn và các cạnh tạo nên đường tròn này có tổng trọng số đường đi là âm.

Trong biểu đồ bên dưới, đường dẫn A->E->B->C->A là một chu trình âm vì tổng trọng số đường dẫn là 5+2-4-4=-1.

Lý do tại sao không thể tìm được đường đi ngắn nhất trong đồ thị có chu kỳ âm là vì luôn có thể tiếp tục chạy thuật toán để tìm những đường đi ngắn hơn nữa.

Ví dụ: giả sử chúng ta đang tìm khoảng cách ngắn nhất từ ​​đỉnh D trong biểu đồ trên đến tất cả các đỉnh khác. Đầu tiên chúng ta tìm được khoảng cách từ D đến E là 3, chỉ bằng cách đi theo cạnh D->E. Nhưng sau đó, nếu chúng ta đi một vòng theo chu kỳ âm E->B->C->A->E thì khoảng cách đến E sẽ là 2. Sau khi đi thêm một vòng nữa khoảng cách sẽ trở thành 1, thậm chí còn ngắn hơn, và như thế. Chúng ta luôn có thể đi thêm một vòng nữa trong chu trình âm để tìm khoảng cách ngắn hơn đến E, nghĩa là không bao giờ tìm được khoảng cách ngắn nhất.

May mắn thay, thuật toán Bellman-Ford , chạy trên đồ thị có cạnh âm, có thể được triển khai bằng cách phát hiện các chu kỳ âm.