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 PATHRấ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.
Nguồn: https://izumi.edu.vn/
Danh mục: Tài liệu toán
