Leetcode 1334: Tìm đường đi ngắn nhất của các cặp với thuật toán Floyd-Warshall

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.

Leetcode 1334: Tìm đường đi ngắn nhất của các cặp với thuật toán Floyd-Warshall
Shortest Pathfinding Algorithm

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

Thông thường các bài toán tìm đường ngắn nhất sẽ đưa vào input là các cặp của các vertex, biểu thị cho liên kết của các vertex với nhau trong đồ thị, các cặp này thường có dạng (s, t, w) với s tương ứng với source node, t tương ứng với target node và w là weight. Ví dụ như:

Input: 

pairs = [('B', 'A', 3), ('A', 'C', 2), ('D', 'B', 5), ('E', 'C', 6), 
 ('E', 'F',7), ('B', 'H', 9), ('B', 'G', 10), ('B', 'F', 12), 
 ('C', 'G', 5)]

source = D
destination = C
Input đầu vào của các bài toán đồ thị

Lưu ý về input

Input mình đưa ra ở trên là tương đối, không được áp dụng cho tất cả các bài. Mỗi bài sẽ mỗi nền tảng sẽ có một cách biểu diễn input khác nhau nhưng về mặt ý tưởng thì vẫn như nhau.

Từ input ở trên, các bạn sẽ phải tự đưa về Adjacent List (Danh sách kề) hoặc Adjacent Matrix (Ma trận kề) và cài đặt cơ sở dữ liệu đồ thị và đưa ra giải pháp thuật toán cho phù hợp. Với các dữ liệu đầu vào này, chúng ta có thể biểu thị dưới dạng đồ thị như hình sau (ở đây mình dùng thư viện Networkx của Python. Tham khảo code tại link Google Colab)

Từ input trên có thể được biểu thị như sau

và output là đường đi ngắn nhất (có tổng số weight ít nhất) từ source node tới target node. Có thể được biểu diễn là đường đi qua các vertex

Output: D, B, A, C
Output là đường đi ngắn nhất qua các vertex

Hoặc là số weight của đường đi ngắn nhất tìm được

Output: 10 

D -> B : 5
B -> A : 3
A -> C : 2
Out put là số weight của đường đi ngắn nhất

Leetcode 1334: Find the City With the Smallest Number of Neighbors at a Threshold Distance

Đối với Leetcode 1334, input của chúng là cũng sẽ là một tập hợp các edge và weight của edge trong đồ thị. Ngoài ra input còn có thêm distance_threshold để phục vụ cho nhu cầu đề bài.

Input và Output của Leetcode 1334

Output thoả yêu cầu của đề bài là thành phố với số thứ tự lớn nhất và  thoả điều kiến có các thành phố lân cận bé hơn hoặc bằng distanceThreshold.


Thuật toán Floyd Warshall (hay All-Pairs Shortest Paths)

Định nghĩa

Khi nào thì thuật toán Floyd-Warshall nên được cân nhắc sử dụng?

Thuât toán Floyd-Warshall chỉ phù hiệu quả với các đồ thị nhỏ, có số node nhỏ hơn 200 (con số này là tương đối, không phải chính xác).

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ị. Khác với cách biểu diễn tính liên kết của các cặp vertex trong đồ thị như các thuật toán ở trên, trong thuật toán Floyd-Warshall, cách tối ưu nhất để biểu diễn tính liền kề của các vertex là ma trận hai chiều. Ma trận này được biểu diễn dưới dạng hình vuông có cạnh là V với V là số vertex của đồ thị.

Adjacent Matrix trong thuật toán Floyd-Warshall

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. Input đầu vào của thuật toán này có thể là array chứa các cặp như mình biểu diễn ở trên, sau đó bạn có thể xây dựng ma trận 2 chiều từ dãy được cho. Do đó, để ngắn gọn thì Input đầu vào lúc này sẽ là ma trận 2 chiều:

Input:
[
    [0,  3,  8,  ~, -4],
    [~,  0,  ~,  1,  7],
    [~,  4,  0,  ~,  ~],
    [2,  ~, -5,  0,  ~],
    [~,  ~,  ~,  6,  0]
]
Input là mảng hai chiều VxV với V là số Vertex (Mình dùng ~ để biểu diễn cho "dương vô cùng")

Từ dữ liệu được cho, có thể truy xuất được các thông tin sau từ việc đọc ma trận dữ liệu đầu vào:

Các thông tin ma trận biểu diễn

Và vấn đề mà thuật toán này giải quyết sẽ là trả về một ma trận VxV với chiều cột và hàng giống với Input. Ma trận này sẽ gồm weight nhỏ nhất của đường đi giữa các node trong đồ thị. Nếu bạn có tìm hiểu qua về Quy hoạch động (Dynamic Programming) thì bài toán được xếp vào nhánh Combinatorial Problem trong Quy hoạch động. Dữ liệu đầu ra không phải là đường đi chính xác từ điểm A đến B mà là weight của đường đi nhỏ nhất. Do đó áp dụng Quy hoạch động vài bài này là hoàn toàn hợp lý.

Cách thuật toán hoạt động?

Từ những thông tin trên, chắc các bạn đã nắm được phần nào vấn đề mà thuật toán này giải quyết. Vậy thuật toán này hoạt động như thế nào?

Để tìm được đường đi ngắn nhất cho tất cả các nút trong đồ thị yêu cầu ít nhất O(V2) với V là số nút trong đồ thị vì chúng ta phải quét qua hết các nút trong đồ thị. Nếu giải bài này theo phương pháp thông thường, số lượng hoán vị trường hợp con là rất lớn. Tuy nhiên, như đã nói ở trên, vì đây là một dạng bài Quy hoạch động nên ta có thể áp dụng các phương pháp của Quy hoạch động vào để giải bài này.

Giả sử chúng ta chọn ngẫu nhiên 2 nút trong đồ thị và tìm đường đi ngắn nhất của chúng. Ở đây mình chọn nút 0 làm điểm đi và nút 2 làm điểm đến. Có thể thấy, với d[0][2] trong ma trân được cho, có giá trị bằng 8. Tuy nhiên, đây chưa phải là đường đi ngắn nhất. Nếu đi theo đường 0 -> 1 -> 3 -> -5 thì tổng weight lúc này sẽ là -1. Do đó, ta tách nhỏ bài toán tìm đường đi ngắn nhất từ 0 -> 2 thành bài toán tìm đường đi ngắn nhất từ 0 -> 33 -> 2 (Xem hình dưới để biết vì sao là 0 -> 3 chứ không phải 0 -> 1).

Phân tích bài toán

Theo cách đó, có vô số hoán vị cần phải đi qua. Tuy nhiên, một điểm chung của các bài Combinatorics là chúng ta sẽ sử dụng giá trị của các trạng thái trước đó được ghi nhớ trong bảng Quy hoạch động để hỗ trợ cho trạng thái hiện tại. Nếu bạn ghi ra các đường đi của 1 điểm để tìm đường đi ngắn nhất, bạn sẽ thấy một công thức chung được dùng để tính weight các đường đi này, ví dụ như mình có đường đi của điểm 0 tới 2.

Điểm chung từ việc tính Weight của đường đi giữa 2 điểm

Chỗ này có thể kết luận rằng, weight đường đi của 2 điểm trong đồ thị sẽ bằng giá trị min(d[i][j], d[i][k] + d[k][j]) với i, j là toạ độ của điểm đó và k sẽ là các trường hợp con. Để có thể kiểm tra được tất cả các đường đi giữa 2 nút 0 và 2, k sẽ phải đi từ điểm đầu tiên tới điểm cuối cùng hay từ 0..V.

Triển khai thuật toán

Thuật toán này sẽ gồm 2 phần chính, đầu tiên là đưa input được cho gồm các edges thành Adjacent Matrix VxV. Theo như lý thuyết ở trên, weight của node với chính nó sẽ bằng 0 và weight sẽ bằng dương vô cùng khi đường đi không tồn tại.

Sau khi đã cài đặt thành công Adjacent Matrix, chúng ta sẽ xay dựng thuật toán Floyd-Warshall trên ma trận vừa được khởi tạo. Thuật toán sẽ gồm 3 vòng lặp như đã giải thích ở trên để có thể bao quát được hết các trường hợp hoán vị đường đi giữa các điểm. Do đó, bài này sẽ có time complexity là O(V3) với V là số vertex và space complexity là O(V2) nếu phải xây dựng Adjacent Matrix. Và đây là toàn bộ code của thuật toán Floyd-Warshall.

Ứng dụng thuật toán để giả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.