Bài toán tìm đường đi ngắn nhất với giải thuật Dijkstra

Với các bạn sinh viên chuyên ngành công nghệ thông tin, chắc chắn không còn xa lạ gì với bài toán tìm đường đi ngắn nhất trong đồ thị trọng số. Trong bài viết này, chúng ta sẽ cùng khám phá bài toán này và ứng dụng của nó, cũng như tìm hiểu về giải thuật Dijkstra và cách triển khai nó bằng ngôn ngữ Ruby.

Có thể bạn quan tâm

Contents

1 1. Giới thiệu bài toán tìm đường đi ngắn nhất
2 2. Giải thuật Dijkstra
3 3. Triển khai giải thuật Dijkstra bằng code Ruby
4 References:

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

Bài toán tìm đường đi ngắn nhất có thể được minh họa bằng một ví dụ cụ thể. Cho một đồ thị trọng số với các node A, B, C, D, E, F và khoảng cách giữa chúng như hình minh họa. Bài toán đặt ra là: Tìm đường đi ngắn nhất từ node B đến các node còn lại trong đồ thị?

Bạn đang xem: Bài toán tìm đường đi ngắn nhất với giải thuật Dijkstra

Sau khi giải bài toán, ta thu được kết quả như sau:

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

Xem thêm : Work For là gì và cấu trúc cụm từ Work For trong câu Tiếng Anh

Bài toán tìm đường đi ngắn nhất có rất nhiều ứng dụng trong thực tế. Ví dụ, nếu chúng ta thay các node bằng các giao lộ và các cạnh bằng các tuyến đường, ta sẽ có bài toán tìm đường đi ngắn nhất trên bản đồ. Nếu thay các node bằng các router mạng hoặc các host, chúng ta sẽ có bài toán định tuyến đường đi trong mạng.

2. Giải thuật Dijkstra

Giải thuật Dijkstra là một phương pháp giúp tìm đường đi ngắn nhất từ một node đến tất cả các node khác trong đồ thị. Phương pháp hoạt động như sau:

Bước 1: Chọn node bắt đầu và tập các node đã được xét gọi là passed_node. Node bắt đầu sẽ là node source.
Bước 2: Khởi tạo giải thuật với source là node bắt đầu và cost(N) là giá trị của đường đi ngắn nhất từ source đến node N.
Bước 3: Xét các node kề với node N. Gọi d(N, K) là khoảng cách giữa node K và node N. Với p = d(N, K) + cost(N). Nếu p < cost(K), thì cost(K) = p. Ngược lại, cost(K) giữ nguyên.
Bước 4: Đánh dấu node N thành passed_node.
Bước 5: Tìm node mới để xét tiếp theo với 2 điều kiện: không phải passed_node và cost(node) là nhỏ nhất.
Bước 6: Nếu tập passed_node chứa đủ tất cả các node trong đồ thị, dừng thuật toán. Ngược lại, quay lại Bước 3.

Giải thuật Dijkstra hoạt động như một quá trình xét từng bước một, cập nhật các giá trị cost để thu được đường đi ngắn nhất từ node bắt đầu đến tất cả các node trong đồ thị.

3. Triển khai giải thuật Dijkstra bằng code Ruby

Xem thêm : Ảnh học bài đẹp tuyệt vời

Để triển khai giải thuật Dijkstra trong code Ruby, chúng ta sẽ sử dụng một đồ thị trọng số cụ thể. Dưới đây là đoạn code Ruby triển khai giải thuật Dijkstra:

class Graph
  def initialize
    @g = {} # Đồ thị
    @nodes = Array.new
    @INFINITY = 1 << 64
  end

  def add_edge(s, t, w)
    if (not @g.has_key?(s))
      @g[s] = {t => w}
    else
      @g[s][t] = w
    end
    # Đồ thị không hướng
    if (not @g.has_key?(t))
      @g[t] = {s => w}
    else
      @g[t][s] = w
    end
    # Thêm node vào danh sách
    if (not @nodes.include?(s))
      @nodes << s
    end
    if (not @nodes.include?(t))
      @nodes << t
    end
  end

  def dijkstra(s)
    @d = {}
    @prev = {}
    @nodes.each do |i|
      @d[i] = @INFINITY
      @prev[i] = -1
    end

    @d[s] = 0
    q = @nodes.compact

    while (q.size > 0)
      u = nil
      q.each do |min|
        if (not u) or (@d[min] and @d[min] < @d[u])
          u = min
        end
      end

      if (@d[u] == @INFINITY)
        break
      end

      q = q - [u]
      @g[u].keys.each do |v|
        alt = @d[u] + @g[u][v]
        if (alt < @d[v])
          @d[v] = alt
          @prev[v] = u
        end
      end
    end
  end

  def print_path(dest)
    if @prev[dest] != -1
      print_path @prev[dest]
    end
    print ">#{dest}"
  end

  def shortest_paths(s)
    @source = s
    dijkstra s
    puts "Source: #{@source}"
    @nodes.each do |dest|
      puts "Target: #{dest}"
      print_path dest if @d[dest] != @INFINITY
      puts "nDistance: #{@d[dest]}"
    end
  end
end

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")

Kết quả trong code trên là các đường đi ngắn nhất từ node a đến các node còn lại. Các kết quả sẽ được in ra màn hình.

Bài viết của mình vẫn còn nhiều thiếu sót, mong nhận được phản hồi tốt từ các bạn.