[Bài toán] Tìm đường đi ngắn nhất P.2
#thuật toán
5
White

Hải Đinh Thanh viết ngày 16/03/2018

5. Thuật toán Floyd-Warshall

Trước khi xem tiếp, các bạn hãy xem phần 1 mình đã đăng ở đây
Trong phần này, đầu tiên mình sẽ giới thiệu về thuật toán mới- Thuật toán Floyd-Warshall. Thuật toán này sẽ tìm đường đi ngắn nhất giữa mọi đỉnh trong đồ thị có trọng số dương.
Rõ ràng thuật toán này có độ phức tạp cao hơn 2 thuật toán đã giới thiệu trong phần 1. Thực ra nó cũng từ thuật toán Dijkstra phát triển thêm mà thôi.

  • Để hiểu thuật toán, mình sẽ đưa ra pseudo và ví dụ áp dụng nó. Trước hết ta có ký hiệu sau:

    $W_{i,j}^{k}$ : là đường đi ngắn nhất từ đỉnh i đến j qua l đỉnh, trong đó $ l\in 1,2,...,k $

    trong đó $i,j,k \leq $ tổng số đỉnh của đồ thị.
    Chú ý: $W_{i,j}^{0}=W_{i,j}^{1}$.

    for (k = 1 to n)
        for i = 1 to n
            for j = 1 to n
    
    

    $$W_{i,j}^{k+1}=min (W_{i,j}^{k}, W_{i,k+1}^{k}+W_{k+1,j}^{k})$$
    p/s: sorry, mình không biết làm sao chèn công thức toán vào pseudocode của markdown

Nhìn sơ qua thuật toán thì hơi khó hiểu, ta xét 1 ví dụ và áp dụng từng bước của pseudo vào là hiểu ngay :D
Ví dụ: Tìm đường đi ngắn nhất giữa các đỉnh với nhau

alt text

Đầu tiên: vòng lặp for k=1 to n = 4 trong bài này sẽ tương ứng với 4 bảng ta lập (bảng 4 là kết quả cuối cùng của thuật toán).

  • Bảng 1: k = 1
1 2 3 4
1 0 8 $\infty $ 1
2 $\infty $ 0 1 $\infty $
3 4 12 0 5
4 $\infty $ 2 9 0

Cách lập bảng: Ví dụ xét hàng 1 cột 2:
$$W_{1,2}^{1} = min (W_{1,2}^{0}, W_{1,1}^{0}+W_{1,2}^{0})$$
trong đó $W_{1,2}^{0}= 8$ , và $W_{1,1}^{0} (= \infty )+ W_{1,2}^{0} (= \infty ) = \infty
$

Tóm lại $W_{1,2}^{1} = 8$
Các giá trị còn lại tính tương tự

  • Bảng 2: k=2
1 2 3 4
1 0 8 9 1
2 $\infty $ 0 1 $\infty $
3 4 12 0 5
4 $\infty $ 2 3 0

Bảng này dựa theo bảng 1 mà tính, chú ý nếu giá trị tính được nhỏ hơn thì cập nhật lại
Ví dụ:
$$W_{4,3}^{2} = min (W_{4,3}^{1}, W_{4,2}^{1}+W_{2,3}^{1})$$
trong đó
$W_{4,3}^{1}= 9$ ( theo bảng 1), $W_{4,2}^{1}+W_{2,3}^{1}=2 + 1 =3 $
vậy
$$W_{4,3}^{2} = 3 < 9 =W_{4,3}^{1}$$
Ta cập nhật lại trong bảng (nếu giá trị tính được lớn hơn thì không cập nhật)

  • Bảng 3: k =3
1 2 3 4
1 0 8 9 1
2 5 0 1 6
3 4 12 0 5
4 7 2 3 0

thực hiện tương tự như bảng 2

  • Bảng 4: k = 4
1 2 3 4
1 0 3 4 1
2 5 0 1 6
3 4 7 0 5
4 7 2 3 0

Bảng 4 là kết quả cuối cùng của thuật toán, nhìn vào bảng ta biết được trọng số đi từ đỉnh này đến đỉnh kia , nhưng chưa mô tả được đi qua bao nhiêu đỉnh, đi như thế nào để được giá trị đó. Mình sẽ bổ sung sau :D

6. Thuật toán Johnsom

Thuật toán này tương tự như thuật toán Floyd-Warshall nhưng cho đồ thị có trọng số bất kỳkhông có vòng lặp âm.

Ý tưởng bài toán thế này:

Từ đồ thị đã cho, tìm cách chuyển nó thành đồ thị có trọng số không âm rồi dùng thuật toán Dijkstra áp dụng cho từng đỉnh

Mình sẽ lấy ví dụ từ đây ( thực ra thuật toán này như 1 trick thôi):
alt text
Mình sẽ giải thích từng bước, đầu tiên hình bên trái là đồ thị đã cho, có trọng số âm và không có vòng lặp âm, còn đồ thị bên phải là đồ thị sau khi ta chuyển đổi, trở thành đồ thị có trọng số không dương .
Bước 1:thêm 1 đỉnh q vào đôt thị, có cạnh đến bất kỳ đỉnh nào cũng được ( nhưng chỉ 1 thôi) , trong hình là chọn q, và có trọng số là 0
Bước 2: Dùng thuật toán Bellman-Ford, tìm đường đi từ q đến các đỉnh còn lại. Kí hiệu tại mỗi đỉnh v$h(v)$ : là kết quả đi từ q tới v tính bằng thuật toán trên
Bước 3: Bây giờ ta thay đổi trọng số của đồ thị đã cho bằng đồ thị mới có trọng số không âm bằng cách:

Mỗi cạnh từ u đến v có trọng số w(u,v) ( cho trước ở graph ban đầu) , 
thay bằng 1 giá trị mới : 
w'(u,v) = w(u,v) + h(u) - h(v)

Ví dụ: $w'(z,x) = w (z,x)+ h(z)-h(x)= -7 + 0 - (-7) = 0$
Bước 4: đến đây thì dùng thuật toán Dijsktra được rồi, graph lúc này là graph có trọng số không âm, đơn giản hơn nhiều rồi @@

7. Tổng kết

Sau khi đọc xong 2 bài này rồi, mình tin khi gặp các bài toán tìm đường đi NN thì sẽ không còn vấn đề gì nữa ( tất nhiên nếu graph đã cho không có yêu cầu gì thêm). Mình sẽ viết thêm nhiều bài nữa về các bài toán hay trong lý thuyết đồ thị, ví dụ cây bao trùm, tô màu đồ thị... :D

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

Hải Đinh Thanh

2 bài viết.
20 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
20 3
Tìm đường đi ngắn nhất Find Shortest Path 1. Giới thiệu Nhắc đến giải thuật duyệt đồ thị, chắc ai cũng biết đến 2 thuật toán cơ bản: DepthFirst...
Hải Đinh Thanh viết hơn 2 năm trước
20 3
Bài viết liên quan
White
3 0
(Ảnh) Giới thiệu Bước đầu tiên, chúng ta hướng tới sự hiểu biết về lý do tại sao nghiên cứu và kiến thức về thuật toán lại rất quan trọng và xác...
Trần Minh Tuấn viết 1 năm trước
3 0
White
2 0
Mô tả Quick Sort là một thuật toán sắp xếp hiệu quả dựa trên việc phân chia mảng thành các nhóm phần tử nhỏ hơn. Giải thuật sắp xếp nhanh chia mản...
Dần Huỳnh viết 1 năm trước
2 0
White
20 3
Tìm đường đi ngắn nhất Find Shortest Path 1. Giới thiệu Nhắc đến giải thuật duyệt đồ thị, chắc ai cũng biết đến 2 thuật toán cơ bản: DepthFirst...
Hải Đinh Thanh viết hơn 2 năm trước
20 3
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
2 bài viết.
20 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!