Tìm đường đi ngắn nhất toán rời rạc năm 2024

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ục

1. Ý tưởng

Thuậ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:

  • Bước 1: Từ đỉnh gốc, khởi tạo khoảng cách tới chính nó là $0$, khởi tạo khoảng cách nhỏ nhất ban đầu tới các đỉnh khác là $+\infty$. Ta được danh sách các khoảng cách tới các đỉnh.
  • Bước 2: Chọn đỉnh a có khoảng cách nhỏ nhất trong danh sách này và ghi nhận. Các lần sau sẽ không xét tới đỉnh này nữa.
  • Bước 3: Lần lượt xét các đỉnh kề b của đỉnh a. Nếu khoảng cách từ đỉnh gốc tới đỉnh b nhỏ hơn khoảng cách hiện tại đang được ghi nhận thì cập nhật giá trị và đỉnh kề a vào khoảng cách hiện tại của b.
  • Bước 4: Sau khi xét tất cả đỉnh kề b của đỉnh a. Lúc này ta được danh sách khoảng cách tới các điểm đã được cập nhật. Quay lại Bước 2 với danh sách này. Thuật toán kết thúc khi chọn được khoảng cách nhỏ nhất từ tất cả các điểm.

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.

Với các bạn sinh viên chuyên ngành công nghệ thông tin, chắc không lạ gì với bài toán tìm đường đi ngắn nhất [Shortest Path Problems] trong đồ thị trọng số nữa. Ở bài viết lần này, mình sẽ làm 3 việc:

  • Giới thiệu bài toán tìm đường đi ngắn nhất và ứng dụng của nó.
  • Giải thích giải thuật Dijkstra để giải quyết bài toán trên
  • Viết giải thuật Dijkstra bằng code Ruby .

1. Giới thiệu bài toán tìm đường đi ngắn nhất

Mình sẽ đưa ra một ví dụ cơ bản về bài toán này.

Bài toán: Cho một đồ thị trọng số gồm các nodes A,B,C,D,E,F và khoảng cách giữa các nodes tương ứng với các cạnh như hình bên dưới . Tìm đường đi ngắn nhất từ node B đến các node còn lại trong đồ thị?

Sau khi giải bài toán, ta được kết quả như sau. Đường đi ngắn nhất từ A đến 5 node còn lại:

  • Từ A -> B : A - B, tổng độ dài đường đi = 2
  • Từ A -> C : A - C, tổng độ dài đường đi = 5
  • Từ A -> D : A - D, tổng độ dài đường đi = 1
  • Từ A -> E : A - D - E, tổng độ dài đường đi = 2
  • Từ A -> F : A - D - E - F, tổng độ dài đường đi = 4

Để nói về ứng dụng của việc giải bài toán này, nếu bạn thay các node bằng các giao lộ, và các cạnh của nó là các tuyến đường, ta sẽ có 1 bài toán rất quen thuộc. Bài toán tìm đường đi ngắn nhất đến một địa điểm trên bản đồ.

Ví dụ như hình ở trên, bằng cách giải quyết bài toán này, bạn sẽ tìm được lộ trình ngắn nhất để đi từ vị trí của bạn đến Mễ Trì Thượng.

Ngoài ra, nếu thay các node bằng các router mạng hoặc các host , chúng ta có bài toán định tuyến đường đi của một hệ thống mạng - loại bài toán cơ bản mà các kỹ sư mạng cần phải biết đến:

Có khá nhiều giải thuật được đưa ra để giải quyết bài toán này : Dijkstra's algorithm , Bellman–Ford algorithm, A* search algorithm, Floyd–Warshall algorithm, .....

Tuy nhiên ở bài viết này, mình sẽ giải thích về giải thuật Dijkstra và cách để viết nó bằng code Ruby.

2. Giải thích về giải thuật Dijkstra

Mô tả về giải thuật Dijkstra:

  • Bước 1: Chọn S = {} là tập các soure_node bao gồm current_nodepassed_node . Với current_node là node đang được xét đến, passed_node là các node đã được xét. current_node đầu tiên sẽ là node đích của bài toán tìm đường đi ngắn nhất.
  • Bước 2: Khởi tạo giải thuật với current_node là node đích và cost[N] là giá trị của đường đi ngắn nhất từ N đến node đích.
  • Bước 3: Xét các node kề N với current_node . Gọi d[current_node,N] là khoảng cách giữa node kề N và current_node . Với p = d[current_node,N] + cost [current_node]. Nếu p < cost[N] thì

    gr = Graph.new gr.add_edge["a","b",5] gr.add_edge["b","c",3] gr.add_edge["c","d",1] gr.add_edge["a","d",10] gr.add_edge["b","d",2] gr.add_edge["f","g",1] gr.shortest_paths["a"]

    0 . Nếu không thì cost[N] giữ nguyên giá trị .
  • Bước 4: Sau khi xét hết các node kề N, đánh dấu current_node thành passed_node .
  • Bước 5: Tìm current_node mới với 2 điều kiện: không phải passed_node và cost[current_node] là nhỏ nhất
  • Bước 6: Nếu tập S = {} chứa đủ các node của đồ thị thì dừng thuật toán. Nếu không thì quay trở lại Bước 3 .

Để giải thích về cách giải thuật Dijkstra hoạt động, mình sẽ sử dụng đồ thị trọng số dưới đây để đi tìm đường đi ngắn nhất từ node C đến mọi node còn lại trong đồ thị :

Trong quá trình thuật toán chạy, ta gọi

  gr = Graph.new
  gr.add_edge["a","b",5]
  gr.add_edge["b","c",3]
  gr.add_edge["c","d",1]
  gr.add_edge["a","d",10]
  gr.add_edge["b","d",2]
  gr.add_edge["f","g",1]
  gr.shortest_paths["a"]

1 là khoảng cách ngắn nhất từ mỗi node đến node C và đánh dấu nó trên hình [giá trị số màu xanh da trời] . Khi thuật toán mới bắt đầu, ta mặc định lưu

  gr = Graph.new
  gr.add_edge["a","b",5]
  gr.add_edge["b","c",3]
  gr.add_edge["c","d",1]
  gr.add_edge["a","d",10]
  gr.add_edge["b","d",2]
  gr.add_edge["f","g",1]
  gr.shortest_paths["a"]

2 , cost[A] = cost[B] = cost[D] = cost[E] = infinity.

Ta cũng đánh dấu current_node [node đang xét hiện tại] bằng một dấu chấm đỏ trên hình. current_node đầu tiên sẽ là node đích của bài toán - ở đây là C.

Thuật toán bắt đầu chạy bằng cách xét tất cả các node kề với current_node [các node được nối trực tiếp với current_node ] , ở đây là A, B và D. Ta sẽ bắt đầu với node B trước và thực hiện 4 bước:

  • Đầu tiên ta tìm được khoảng các từ current_node đến

    gr = Graph.new gr.add_edge["a","b",5] gr.add_edge["b","c",3] gr.add_edge["c","d",1] gr.add_edge["a","d",10] gr.add_edge["b","d",2] gr.add_edge["f","g",1] gr.shortest_paths["a"]

    4: d[C,B] = 7.
  • Tính toán giá trị đường đi từ

    gr = Graph.new gr.add_edge["a","b",5] gr.add_edge["b","c",3] gr.add_edge["c","d",1] gr.add_edge["a","d",10] gr.add_edge["b","d",2] gr.add_edge["f","g",1] gr.shortest_paths["a"]

    5 :

    gr = Graph.new gr.add_edge["a","b",5] gr.add_edge["b","c",3] gr.add_edge["c","d",1] gr.add_edge["a","d",10] gr.add_edge["b","d",2] gr.add_edge["f","g",1] gr.shortest_paths["a"]

    6
  • Nếu giá trị vừa tính

    gr = Graph.new gr.add_edge["a","b",5] gr.add_edge["b","c",3] gr.add_edge["c","d",1] gr.add_edge["a","d",10] gr.add_edge["b","d",2] gr.add_edge["f","g",1] gr.shortest_paths["a"]

    7 thì

    gr = Graph.new gr.add_edge["a","b",5] gr.add_edge["b","c",3] gr.add_edge["c","d",1] gr.add_edge["a","d",10] gr.add_edge["b","d",2] gr.add_edge["f","g",1] gr.shortest_paths["a"]

    8, ngược lại thì cost[B] giữ nguyên. [ ở đây

    gr = Graph.new gr.add_edge["a","b",5] gr.add_edge["b","c",3] gr.add_edge["c","d",1] gr.add_edge["a","d",10] gr.add_edge["b","d",2] gr.add_edge["f","g",1] gr.shortest_paths["a"]

    9 nên `nodes`0 ]
  • Đánh dấu cost[B] lên hình.

Tương tự với A và D, ta cũng tìm được cost[A] = 1 và cost[D] = 2 .

Sau khi xét hết tất cả các node kề với current_node, ta chuyểncurrent_node thành passed_node - tức là node đã được xét rồi. passed_node sẽ được đánh 1 dấu tích xanh trên hình.

Bây giờ chúng ta sẽ chọn 1 current_node mới với 2 điều kiện:

  • current_node không thể là passed_node.
  • cost[current_node] có giá trị nhỏ nhất.

Nếu xét trên hình, current_node tiếp theo sẽ là node A . Ta đánh dấu node A với 1 dấu chấm đỏ.

Ta tiếp tục giải thuật bằng cách xét các node kề với current_node với điều kiện node kề không được là passed_node . Như vậy ở đây ta chỉ được xét node B .

  • `nodes`1 .
  • `nodes`2
  • `nodes`3 . Vậy `nodes`4
  • Đánh dấu cost[B] lên hình

Đánh dấu node A trở thành passed_node. Ta tiếp tục tìm current_node mới, lần này nó là node D với cost[D] = 2:

Có 2 node kề với D là B và E.

Xét với

  gr = Graph.new
  gr.add_edge["a","b",5]
  gr.add_edge["b","c",3]
  gr.add_edge["c","d",1]
  gr.add_edge["a","d",10]
  gr.add_edge["b","d",2]
  gr.add_edge["f","g",1]
  gr.shortest_paths["a"]

4

  • `nodes`6 .
  • `nodes`7
  • `nodes`8 . Vậy `nodes`4
  • Giữ nguyên cost[B]

Xét với `node`0

  • `node`1 .
  • `node`2
  • `node`3 . Vậy `node`4
  • Đánh dấu cost[E] lên hình.

Đánh dấu node D trở thành passed_node. Ta tiếp tục tìm current_node mới, lần này nó là node B với `nodes`4 :

Chỉ còn 1node kề với B là E.

Xét với `node`0

  • `node`7 .
  • `node`8
  • `node`9 . Vậy `soure_node`0
  • Đánh dấu cost[E] lên hình.

Giờ chúng ta không còn node nào để check nữa. Đánh dấu node E trở thành passed_node và kết thúc thuật toán.

Vậy ta có kết quả của thuật toán với đường đi ngắn nhất từ C đến các điểm còn lại là:

  • Từ C -> A: C - A, cost[A] = 1
  • Từ C -> B: C - A - B, cost[B] = 4
  • Từ C -> D: C - D, cost[D] = 2
  • Từ C -> E: C - A - B - E, cost[E] = 5

3. Giải thuật Diijkstra với code Ruby

Mình đã giải thích rất rõ cách hoạt động của giải thuật Dijkstra rồi. Nên việc triển khai nó trong code Ruby khá dễ hiểu.

Chủ Đề