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

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

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: Depth-First Search (DFS) , Breadth-First Search (BFS). Về mặt ý nghĩa, cả 2 thuật toán đều thực hiện trên đồ thị không có trọng số . Thuật toán DFS cho ta tìm đường đi đến đỉnh ta muốn ( có thể chưa ngắn nhất), còn BFS cũng tìm đường đi đến đỉnh ta muốn nhưng là đường ngắn nhất có thể.

Trong đồ thị có trọng số, vấn đề sẽ khó hơn, nó nảy sinh ra 1 bài toán, đó là bài toán tìm đường đi ngắn nhất giữa 2 đỉnh. Nó là bài toán rất quen thuộc với những người bắt đầu học Graph. Để giải quyết bài toán này, đến giờ có nhiều thuật toán và các biến thể. Trong phạm vi bài viết này, mình sẽ giới thiệu về những thuật toán quen thuộc để giải quyết. Các thuộc toán được đưa ra thuộc dạng thuật toán tìm kiếm.

2. Định nghĩa

Có 2 định nghĩa:

  1. Bài toán tìm đường đi ngắn nhất là bài toán tìm 1 đường đi giữa 2 đỉnh sao cho tổng các trọng số của các cạnh tạo ra đường đi đó nhỏ nhất
  2. Cho trước 1 graph vô hướng G, và hàm trọng số có giá trị thực $f: E\rightarrow \mathbb{R}$ , đường đi ngắn nhất từ đỉnh v đến đỉnh v' là đường đi : $$P = (v_{1},v_{2},...,v_{n})$$ sao cho $$\sum_{p\in P}{f(p)}$$ là nhỏ nhất

Đây là 2 định nghĩa cơ bản nhất của bài toán. Bài toán này có những dạng sau cùng các thuật toán xử lý:

  1. Giải bài toán đường đi ngắn nhất nguồn đơn ( simple-source): Ta sẽ tìm đường đi ngắn nhất từ đỉnh nguồn v đến tất cả các đỉnh khác . Có 2 thuật toán quan trọng: Thuật toán Dijkstra ( đối với trọng số dương) và Thuật toán Bellman-Ford ( đối với trọng số bất kỳ).
  2. Giải bài toán đường đi ngắn nhất nguồn đích (simple-destination): Ta sẽ tìm đường đi ngắn nhất trong đồ thị có hướng từ các đỉnh đến đỉnh đích v. Ta có thể giải quyết bằng cách đảo ngược hướng của đồ thị và trở thành bài toán nguồn đơn.
  3. Giải bài toán đường đi ngắn nhất cho mọi cặp đỉnh: Ta sẽ tìm đường đi ngắn nhất giữa 2 đỉnh bất kỳ . Có 2 thuật toán quan trọng: Thuật toán Floyd-WarshallThuật toán Johnson

Trong khuôn khổ phần 1, mình sẽ giới thiệu 2 thuật toán đầu tiên giải quyết bài toán nguồn đơn .

3. Thuật toán Dijkstra

Đây là thuật toán tìm đường đi ngắn nhất nguồn đơn có trọng số dương. Tức là mỗi cạnh ta sẽ có trọng số ( trọng số tức là chi phí, chiều dài, thời gian....gọi là trọng số ). Để phân tích thuật toán 1 cách dễ hiểu, mình sẽ không trình bày pseudo code của thuật toán, mà mình sẽ đưa ví dụ và cách thực hiện thuật toán cho ví dụ này để người đọc dễ hiểu nhất

Ví dụ: Cho đồ thị dưới đây, tìm đường đi ngắn nhất từ A đến các đỉnh còn lại

alt text

Ta lập bảng sau, và mình sẽ giải thích cách thực hiện từng bước:

Bước A B C D E
0 0 $$\infty$$ $$\infty$$ $$\infty$$ $$\infty$$
1 $$\cdot $$ 10 (A) $$\infty$$ $$\infty$$ 5 (A)
2 $$\cdot $$ 8 (E) 14 (E) 7 (E) $$\cdot $$
3 $$\cdot $$ 8 (E) 13 (D) $$\cdot $$
4 $$\cdot $$ $$\cdot $$ 9 (B) $$\cdot $$ $$\cdot $$
  • Bước 0: đầu tiên ta sẽ xuất phát từ đỉnh 0, vì chỉ là xuất phát chưa đến ai cả nên giá trị tại A là 0 và các đỉnh còn lại sẽ là vô cùng
  • Bước 1: Xuất phát, ta thấy đỉnh A chỉ có đường đi đến 2 đỉnh B và E. Xét về trọng số, (A,B) = 10, còn (A,E) = 5. Ta viết 2 trọng số này vào bảng, các đỉnh còn lại không có đường đi đến thì vẫn giữ nguyên giá trị. Chú ý: từ bước này ta sẽ chọn ra đỉnh tiếp theo để thực hiện bước 2, đỉnh tiếp theo là đỉnh có giá trị trọng số nhỏ nhất ở từng bước , ví dụ ở đây ta phải xét đỉnh E ( vì E chỉ có giá trị 5 (A) ) ( ký hiệu 5 (A) tức là đỉnh A đến E có giá trị trọng số 5)
  • Bước 2: Xét đỉnh E, E có 3 đường đi đến các đỉnh B , C , D lần lượt có giá trị trọng số là 3, 9, 7. Đem cộng với 5 (A), tức mỗi đỉnh lúc này có giá trị trong bảng là 8 (E), 14 (E), 7 (E). So sánh ba giá trị này, chọn giá trị nhỏ nhất . Ở đây là giá trị 7 (E), tức bước tiếp theo ta sẽ xét từ đỉnh D
  • Bước 3: Từ đỉnh D, thực hiện tương tự bước 2 ta được D --> C = 13 (D), D-->A = 7 (D). Nhưng ở A giá trị ban đầu là 0 rồi, ta không cần cập nhật lại. Do vậy bước này chỉ có duy nhất 1 giá trị mới sinh ra, nhưng ta không chọn giá trị này vì tại bước 2, đỉnh B có 8 (E) < 13 (D). Nên ta chọn đỉnh B để thực hiện tiếp bước 4
  • Bước 4: Tương tự, ta được B--> C = 9 (B). Mà từ C , chỉ có duy nhất 1 đường đi đến D có giá trị là 13 (C), nhưng nó lại lớn hơn giá trị 7 (E) tính từ trước. Nên ở đây ta đã kết thúc thuật toán

Giải thích ý nghĩa bảng

  1. Các giá trị theo cột phải nhỏ dần ( nhỏ nhất là 0)
  2. Nếu ta nói các chữ bên cạnh con số với tên của cột , ta được 1 đồ thị mới không lặp
  3. Nhìn vào bảng , ta hiểu như sau: Ví dụ cột D, giá trị là 7 (E) . Tức là đường đi ngắn nhất từ A đến D có GTNN là 7, và theo lộ trình: trước mắt đi từ E --> D , ta nhìn xem đỉnh nào sẽ đi đến E dựa vào giá trị nhỏ nhất trong cột của đỉnh đó, ở E , min là 5 (A), tức là A --> E. Vậy đường đi ngắn nhất từ A -> D là A -> E -> D có giá trị là 7.

Chú ý: bạn phải đọc thật kỹ từng bước thuật toán này, hiểu được cách lập bảng thì mới tiếp tục được thuật toán Bellman- Ford.

4. Thuật toán Bellman-Ford

Thuật toán này tương tự thuật toán Dijkstra, tuy nhiên trong mỗi bước, ta không còn chọn cố định 1 đỉnh nhỏ nhất nũa mà phải xét hết. Ví dụ ở bước 1, ở thuật toán Dijkstra ta chọn đỉnh E để xét bước 2, nhưng với thuật toán này , ta xét luôn đỉnh B và E rồi so sánh giá trị chọn nhỏ nhất. Lưu ý đồ thị không được có vòng (cycle) nào có tổng là 1 số âm, vì khi đó cứ mỗi lần duyệt qua vòng này ta không thể tìm ra đường đi ngắn nhất ( 1 lần đi 1 vòng độ dài đường đi sẽ giảm, càng đi càng giảm, vì vậy vô hạn lần)
Ví dụ ( tham khảo): Tìm đường đi ngắn nhất từ A đến các đỉnh còn lại

alt text

Bước A B C D E
0 0 $$\infty$$ $$\infty$$ $$\infty$$ $$\infty$$
1 $$\cdot $$ 3 (A) $$\infty$$ $$\infty$$ 4 (A)
2 $$\cdot $$ $$\cdot $$ -1 (E) 5 (B) $$\cdot $$
3 $$\cdot $$ -3 (C) $$\cdot $$ $$\cdot $$ $$\cdot $$
4 $$\cdot $$ -3 (C) -1 (E) -1 (B) 4 (A)
  • Bước 1: giá trị (A,B) = 3, giá trị (A,E) = 4 . Thực hiện bình thường.
  • Bước 2: Xét giá trị từ 2 đỉnh B và E đến các đỉnh còn lại. Ta thấy (B, C ) = 5, (B , E) = 13 , (B, D) = 5 và (E, C) = -1. So sánh thấy từ E đến C cho giá trị nhỏ nhất , nên cập nhật giá trị này vào cột C, (B,E) =13 > (A,E) = 4 nên bỏ qua giá trị này, còn D thì cập nhật vào
  • Bước 3: Xét giá trị từ C và D , ta thấy (C,B) = -3 (C) , (D,C) = 8 . Cập nhật giá trị vào cột B
  • Bước 4: Xét tương tự cho B ta được (B,D) = -1. Đến đây ta thấy nếu xét đỉnh D, (D,C) = 2 nhưng tại C giá trị nhỏ nhất nó đã là -1 (E) rồi nên không cập nhật được. Kết thúc

Trên đây là 2 thuật toán mình giới thiệu, khi gặp các bài toán tìm đường đi ngắn nhất xuất phát từ 1 điểm đến 1 điểm nào đó, nếu trọng số dương thì ta dùng thuật toán Dijkstra, còn vừa âm vừa dương thì dùng Bellman-Ford. Ở bài tiếp theo mình sẽ giới thiệu 2 thuật toán còn lại
(continue....)

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
3 1
5. Thuật toán FloydWarshall Trước khi xem tiếp, các bạn hãy xem phần 1 mình đã đăng ở (Link) Trong phần này, đầu tiên mình sẽ giới thiệu về thu...
Hải Đinh Thanh viết 8 tháng trước
3 1
Bài viết liên quan
White
3 1
5. Thuật toán FloydWarshall Trước khi xem tiếp, các bạn hãy xem phần 1 mình đã đăng ở (Link) Trong phần này, đầu tiên mình sẽ giới thiệu về thu...
Hải Đinh Thanh viết 8 tháng trước
3 1
{{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á!