Những điều thú vị về giải thuật Dijkstra trong bài toán tìm đường đi ngắn nhất

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ạ 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, mình sẽ giới thiệu về bài toán này cùng với ứng dụng của nó, và giải thích cách hoạt động của giải thuật Dijkstra. Cuối cùng, mình sẽ chia sẻ cho các bạn code Ruby để triển khai giải thuật này.

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ó ứng dụng rất rộng rãi trong thực tế. Nếu ta thay các node trong đồ thị bằng các giao lộ và các cạnh bằng các tuyến đường, ta sẽ có một bài toán quen thuộc – tìm đường đi ngắn nhất trên bản đồ. Bằng cách giải quyết bài toán này, bạn có thể tìm lộ trình ngắn nhất từ vị trí của bạn đến địa điểm mong muốn.

Bạn đang xem: Những điều thú vị về giải thuật Dijkstra trong bài toán tìm đường đi ngắn nhất

Ngoài ra, 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 – một loại bài toán mà các kỹ sư mạng cần biết.

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

Giải thuật Dijkstra là một giải thuật nổi tiếng được sử dụng để giải quyết bài toán tìm đường đi ngắn nhất trong đồ thị. Để hiểu cách giải thuật này hoạt động, chúng ta sẽ theo dõi ví dụ sau đây.

Giả sử chúng ta có một đồ thị trọng số như sau:

A - B (2)
| 
D   C (5)
  / 
  E (1)
  |
  F (4)

Bài toán của chúng ta là tìm đường đi ngắn nhất từ điểm B đến các điểm còn lại trong đồ thị này. Sau khi thực hiện giải thuật Dijkstra, chúng ta 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

Qua ví dụ trên, chúng ta có thể thấy rõ ứng dụng của việc giải quyết bài toán tìm đường đi ngắn nhất. Các kỹ sư mạng, những người thực hiện định tuyến, cần biết về giải thuật này để tìm ra đường đi tối ưu nhất trong hệ thống mạng.

3. Giải thuật Dijkstra trong code Ruby

Dưới đây là một đ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

    # nếu đồ thị không hướng, thì thêm cạnh ngược lại
    if (not @g.has_key?(t))
      @g[t] = {s=>w}
    else
      @g[t][s] = w
    end

    # thêm node vào danh sách các node
    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
      if @d[dest] != @INFINITY
        puts "nDistance: #{@d[dest]}"
      else
        puts "nNO PATH"
      end
    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")

Ta chạy đoạn code trên trong terminal, chúng ta sẽ được kết quả như sau:

Source: a
Target: a
Distance: 0
Target: b
>ba
Distance: 5
Target: c
>ba>cb
Distance: 8
Target: d
>ba>db
Distance: 7
Target: f
NO PATH
Target: g
NO PATH

Rất dễ hiểu và thú vị đúng không nào?

Hy vọng bài viết mang lại cho bạn các thông tin hữu ích về giải thuật Dijkstra và cách sử dụng nó để tìm đường đi ngắn nhất trong đồ thị. Nếu bạn muốn tìm hiểu thêm, hãy truy cập vào Izumi.Edu.VN. Chúng tôi mong nhận được nhiều phản hồi tốt từ bạn.

Ảnh minh họa

Nguồn: https://izumi.edu.vn/
Danh mục: Tài liệu toán