Thuật toán tìm đường đi ngắn nhất python
Thuật toán Floyd-Warshall hay còn được gọi là thuật toán tìm đường đi ngắn nhất cho các cặp trong đồ thị. Thuật toán này không được thiết kế để giải quyết vấn đề về tìm đường đi ngắn nhất giữa hai điểm, mà là đường đi ngắn nhất giữa các điểm với nhau. Show
Bài toán tìm đường đi ngắn nhất là một bài toán khá phổ biến trong lý thuyết đồ thị. Vì đây là một bài toán có tính thực tế cao nên được hỏi rất nhiều trong các buổi phỏng vấn của các công ty lớn. Một số ngữ cảnh được áp dụng giải quyết bằng thuật toán tìm đường có thể kể đến như tìm bạn chung trong ứng dụng mạng xã hội, tìm đường đi để truyền thông tin nhanh nhất trong hệ thống mạng...Trong bài viết hôm nay, mình sẽ giới thiệu về thuật toán Floyd-Warshall và ứng dụng thuật toán này để giải bài Leetcode 1334: Phần chính của bài này là triển khai thuât toán Floyd-Warshall, nên sau khi đã thành công cài đặt thuật toán thì bạn đã hoàn thành 90% công việc. Tuy nhiên yêu cầu của bài này là chúng ta phải tìm ra thành phố có số neighbor bé hơn distance_threshold nhỏ nhất. Do đó, chúng ta chỉ cần lặp qua các phần tử của ma trận một lần nữa để tìm ra kết quả thoả điều kiện cuối. Thuật toán Dijkstra là một trong những thuật toán cổ điển để giải quyết bài toán tìm đường đi ngắn nhất từ một điểm cho trước tới tất cả các điểm còn lại trong đồ thị có trọng số. Trong bài viết này chúng ta cùng tìm hiểu ý tưởng cơ bản của thuật toán Dijkstra. Mục lục1. Ý tưởngThuật toán Dijkstra có thể giải quyết bài toán tìm đường đi ngắn nhất trên đồ thị vô hướng lẫn có hướng miễn là trọng số không âm. Ý tưởng cơ bản của thuật toán như sau:
2. Ví dụĐể dễ dàng hiểu ý tưởng của thuật toán. Chúng ta cùng xem ví dụ với đồ thị vô hướng $G$. Thuật toán Dijkstra sẽ tìm khoảng cách từ đỉnh gốc $0$ tới tất cả các đỉnh còn lại trong đồ thị $G$. Đồ thị $G$ Đầu tiên, khởi tạo khoảng cách nhỏ nhất ban đầu tới các đỉnh khác là $+\infty$ và khoảng cách tới đỉnh gốc là 0. Ta được danh sách các khoảng cách tới các đỉnh.
Chọn đỉnh 0 có giá trị nhỏ nhất, xét các đỉnh kề của đỉnh 0: Xét đỉnh 1, khoảng cách từ gốc đến đỉnh 1 là 2.5 < $\infty$ nên ghi nhận giá trị mới là $(2.5, 0)$ (nghĩa là khoảng cách đến đỉnh gốc hiện tại ghi nhận là 2.5, đỉnh kề liền trước là đỉnh 0). Xét tương tự cho đỉnh 2 và 3, ta được dòng thứ 2 trong bảng.
Sau khi xét tất cả các đỉnh ta chọn đỉnh 2 có khoảng cách nhỏ nhất và ghi nhận để xét tiếp. Tiếp tục xét đỉnh kề của 2 là đỉnh 4 và 5 với nguyên tắc nêu ở trên. Xét đỉnh 4, khoảng cách từ đỉnh gốc đến đỉnh 4 sẽ bằng khoảng cách từ đỉnh gốc tới đỉnh 2 cộng khoảng cách từ 2 đến 4. Nghĩa là $2.0+0.6=2.6$ nên ta ghi nhận khoảng cách tại đỉnh 4 là $(2.6, 2)$. Xét tương tự cho đỉnh 5.
Lúc này ta chọn được đỉnh 3 có khoảng cách nhỏ nhất, xét đỉnh kề của đỉnh 3 là đỉnh 5. Khoảng cách từ gốc tới đỉnh 5 $=2.1+2.5=4.6$ lớn hơn khoảng cách hiện tại được ghi nhận, vì vậy giá trị tại đỉnh 5 không đổi.
Đỉnh 1 là đỉnh được chọn tiếp theo, xét đỉnh kề của 1 là đỉnh 4. Khoảng cách từ đỉnh gốc không nhỏ hơn khoảng cách hiện tại nên ta không cập nhật gì ở đỉnh này. Bài toán tìm đường đi ngắn nhất trên đồ thị là một trong những bài toán đa dạng, có nhiều ứng dụng thực tế (như trong Google Maps, hay các bài toán networking, …). Các dạng bài về tìm đường đi ngắn nhất cũng thường xuyên có mặt trong các kì thi lập trình. Bài viết này sẽ giới thiệu ba thuật toán cơ bản của dạng bài tìm đường đi ngắn nhất:
Cần lưu ý rằng, cũng có tên thường gọi là thuật toán Floyd, dùng để tìm chu trình trong đồ thị có hướng. Bài viết này sẽ chỉ đề cập đến thuật toán tìm đường đi ngắn nhất. 1. Thuật toán Bellman - FordThuật toán Bellman-Ford dùng để giải quyết bài toán đường đi ngắn nhất một nguồn (Single-source shortest path), đồ thị có thể có trọng số âm. Bài toán.Cho đồ thị có hướng $N$ đỉnh và $M$ cạnh, và một đỉnh nguồn là đỉnh $S$. Mỗi cạnh có trọng số nguyên. Trọng số này có thể âm hoặc dương hoặc bằng 0. Với mỗi đỉnh $u$ từ $1$ đến $N$. Yêu cầu xuất kết quả tại mỗi đỉnh $u$ như sau:
Input: Dòng đầu tiên gồm 3 số nguyên $N, M, S$. $M$ dòng tiếp theo, mỗi dòng gồm ba số nguyên $u, v, W_{u, v}$ biểu diễn một cạnh một chiều từ $u$ đến $v$ với trọng số là $W_{u, v}$. Output: gồm $N$ dòng cho biết đường đi ngắn nhất từ đỉnh $S$ đến các đỉnh từ $0$ đến $N-1$ Giới hạn bài toán : $1 \le N \le 1000, 1 \le M \le 5000$ Sample Input
Sample Output
Khái niệm về chu trình âm
Ý tưởng của thuật toán.Xét trường hợp đơn giản hơn, khi đồ thị không có trọng số âm (tức đường đi ngắn nhất luôn tồn tại). Thuật toán Bellman-Ford sẽ lặp nhiều lần. Ở mỗi vòng lặp, ta sẽ đi qua tất cả các cạnh $(u, v)$ trên đồ thị, so sánh đường đi $S \rightarrow v$ đã tìm được với đường đi $S \rightarrow u \rightarrow v$
Có thể chứng minh được rằng, vòng lặp trên cần thực hiện $N-1$ lần, mỗi lần đi qua toàn bộ $M$ cạnh, là sẽ đủ để tìm đường đi ngắn nhất.
Cài ĐặtỞ thuật toán này, đồ thị thường được lưu ở dạng danh sách cạnh.
Code:
Tìm lại đường đi ngắn nhấtThao tác tìm đường đi ngắn nhất từ $S$ đến $u$ khá đơn giản, ta sẽ bắt đầu từ đỉnh $u$, sau đó truy vết theo mảng $trace$ ngược về $S$.
Các trường hợp có chu trình âmThuật toán Bellman-Ford có thể xử lí được thêm trường hợp nhận biết chu trình âm, cũng như nhận biết nếu không tồn tại đường đi ngắn nhất đến một đỉnh. Nhận biết đường đi âm vô cực
Code:
Tìm chu trình âmMột số bài toán có thể yêu cầu ta tìm một chu trình âm bất kì trong đồ thị. Ta có thể chỉnh sửa thuật toán Bellman-Ford lại như sau:
2. Thuật toán DijkstraThuật toán Dijkstra dùng để giải quyết bài toán đường đi ngắn nhất một nguồn (Single-source shortest path), đồ thị trọng số không âm. Bài toán.Cho một đồ thị có hướng với $N$ đỉnh (được đánh số từ $0$ đến $N-1$), $M$ cạnh có hướng, có trọng số, và một đỉnh nguồn $S$. Trọng số của tất cả các cạnh đều không âm. Yêu cầu tìm ra đường đi ngắn nhất từ đỉnh $S$ tới tất cả các đỉnh còn lại (hoặc cho biết nếu không có đường đi). Sample Input
Sample Output
Hình ảnh của Test ví dụ. Ở đồ thị này, đỉnh nguồn là đỉnh $0$, đường đi ngắn nhất từ $0$ đến các đỉnh $0$ đến $5$ là $[0, 1, 7, 4, 4, 10]$. Riêng đỉnh $6$ không có đường đi đến. Ý tưởng của thuật toán.Giống như thuật toán Bellman-Ford, thuật toán Dijkstra cũng tối ưu hóa đường đi bằng cách xét các cạnh $(u, v)$, so sánh hai đường đi $S \rightarrow v$ sẵn có với đường đi $S \rightarrow u \rightarrow v$. Thuật toán hoạt động bằng cách duy trì một tập hợp các đỉnh trong đó ta đã biết chắc chắn đường đi ngắn nhất. Mỗi bước, thuật toán sẽ chọn ra một đỉnh $u$ mà chắc chắn sẽ không thể tối ưu hơn nữa, sau đó tiến hành tối ưu các đỉnh $v$ khác dựa trên các cạnh $(u, v)$ đi ra từ đỉnh $u$. Sau $N$ bước, tất cả các đỉnh đều sẽ được chọn, và mọi đường đi tìm được sẽ là ngắn nhất. Cụ thể hơn, thuật toán sẽ duy trì đường đi ngắn nhất đến tất cả các đỉnh. Ở mỗi bước, chọn đường đi $S \rightarrow u$ có tổng trọng số nhỏ nhất trong tất cả các đường đi đang được duy trì. Sau đó tiến hành tối ưu các đường đi $S \rightarrow v$ bằng cách thử kéo dài thành $S \rightarrow u\rightarrow v$ như đã mô tả trên. Minh họa thuật toánTa sẽ minh họa thuật toán bằng một đồ thị như hình. Định nghĩa:
Đỉnh được tô đen (đỉnh 0) sẽ là đỉnh nguồn. Ban đầu, $D = [0, \infty, \infty, \infty]$, $P = [false, false, false, false]$
Sau bước này, $D = [0, \infty, 1, 4]$, $P = [true, false, false, false]$
Sau bước này, $D = [0, 4, 1, 3]$, $P = [true, false, true, false]$
Sau bước này, $D = [0, 4, 1, 3]$, $P = [true, false, true, true]$
Đến đây, tất cả các đỉnh đều đã được đánh dấu. Thuật toán kết thúc. Đường đi ngắn nhất tìm được từ đỉnh $0$ là $D = [0, 4, 1, 3]$. Cài đặtỞ thuật toán này, ta sẽ lưu đồ thị dưới dạng danh sách kề. Ta định nghĩa như sau:
Ta sẽ lặp $N$ lần quá trình sau:
Độ phức tạp thuật toán: Ta có $N$ lần lặp:
Như vậy độ phức tạp của cách cài đặt cơ bản sẽ là $O(N^2 + M)$. Code:
Cải tiến đối với đồ thị thưa
Độ phức tạp sau khi cải tiến: $O(MlogN)$. Lưu ý rằng với $M$ lớn thì độ phức tạp này không tốt hơn cài đặt cơ bản. Chứng minh như sau:
Code:
Tìm lại đường đi ngắn nhấtCũng giống như thuật toán Bellman-Ford, để tìm lại đường đi ngắn nhất từ $S$ về $u$, ta sẽ bắt đầu từ đỉnh $u$, sau đó truy vết theo mảng $trace$ ngược về $S$.
3. Thuật toán Floyd-WarshallThuật toán Floyd-Warshll dùng để giải quyết bài toán đường đi ngắn nhất mọi cặp đỉnh (All-pairs shortest path), đồ thị có thể có trọng số âm. Bài toánCho đồ thị gồm $N$ đỉnh và một ma trận trọng số $W$, trong đó ô $(i,j)$ cho biết rằng có một đường đi trực tiếp từ $i\rightarrow j$ với trọng số là $W_{i, j}$. Yêu cầu tìm đường đi ngắn nhất giữa mọi cặp đỉnh trên đồ thị. Giới hạn bài toán: $1 \leq N \leq 100$ Input: Dòng đầu tiên gồm số nguyên dương $N$, $N$ dòng tiếp theo, mỗi dòng gồm $N$ số biểu diễn một ma trận trong đó ô $(i,j)$ cho biết đường đi trực tiếp từ $i\rightarrow j$ có trọng số là $W[i, j]$. Output: Ma trận kết quả trong đó giá trị ô $(i,j)$ là đường đi ngắn nhất từ $i\rightarrow j$. Sample Input
1 Sample Output
2 Ý tưởng của thuật toán.Ý tưởng của thuật toán này là: "Liệu chúng ta có thể chèn một đỉnh $k$ vào đường đi ngắn nhất giữa 2 đỉnh $u$ và $v$?".
Ta nhận thấy có một cấu trúc đệ quy, chia nhỏ bài toán ở đây. Ý tưởng này cho phép chúng ta thực hiện một thuật toán mang hương vị quy hoạch động như sau:
Đến đây ta có thể sử dụng trực tiếp công thức quy hoạch động để cài đặt thuật toán. Tuy nhiên, để đảm bảo bộ nhớ, ta có thể tính các $D(u, v, k)$ với $k$ lần lượt từ $1$ đến $N$, và khi cài đặt chỉ cần lưu lại $D(u, v)$. Cài đặt
Code: Thuật toán có thể được cài đặt rất dễ dàng chỉ với 3 vòng lặp:
3 Tìm lại đường đi ngắn nhấtGiống như hai thuật toán Bellman-Ford và Dijkstra, để tìm đường đi từ $u$ đến $v$, ta sẽ bắt đầu từ $v$, truy ngược về $u$ theo mảng trace đã tìm được.
4 4. Lưu ý
Heap không phải là cấu trúc dữ liệu duy nhất có thể sử dụng khi cài đặt Dijkstra dành cho đồ thị thưa. Ta có thể sử dụng bất cứ cấu trúc dữ liệu nào hỗ trợ các thao tác "xóa khỏi tập hợp", "cập nhật phần tử trong tập hợp", "tìm phần tử nhỏ nhất trong tập hợp". Thực tế cây nhị phân tìm kiếm (
6 trong C++) cũng là một lựa chọn phổ biến khi cài đặt thuật toán này. |