Giải thuật Dijkstra như tôi đã reviews phiên trước rất có thể giải quyết và xử lý vô cùng thời gian nhanh vấn đề lần lối đi sớm nhất với vật thị trọng số dương. (Các bạn cũng có thể coi nội dung bài viết về giải thuật Dijkstra bên trên phía trên .
Tuy nhiên, với vật thị trọng số âm, tất cả chúng ta tiếp tục lựa chọn giải thuật Bellman-Ford. Vậy vô nội dung bài viết này bản thân tiếp tục thực hiện 2 điều:
Bạn đang xem: thuật toán bellman ford tìm đường đi ngắn nhất
- Giới thiệu cơ hội giải vấn đề shortest-path vị giải thuật Bellman-Ford
- Thiết tiếp giải thuật này vị code ruby.
1. Cách thuật toán Bellman-Ford sinh hoạt.
Về vấn đề lần lối đi sớm nhất, những bạn cũng có thể coi đề bài xích ở vô nội dung bài viết trước.
Ý tưởng của thuật toán như sau:
- Ta tiến hành duyệt n phiên, với n là số đỉnh của vật thị.
- Với từng phiên duyệt, tao lần toàn bộ những cạnh nhưng mà đàng trải qua cạnh này sẽ tinh giảm lối đi sớm nhất kể từ đỉnh gốc cho tới một đỉnh không giống.
- Ở phiên duyệt loại n, nếu như còn ngẫu nhiên cạnh nào là rất có thể tinh giảm lối đi, vấn đề này chứng minh vật thị với quy trình âm, và tao kết cổ động thuật toán.
Thuật toán Bellman-Ford với 3 bước:
- Bước 1: Khởi tạo nên vật thị
Giải quí vị pseudocode:
for each v in danh_sách_đỉnh:
if v is mối cung cấp then khoảng_cách(v):= 0
else khoảng_cách(v):= vô cùng
đỉnh_liền_trước(v):= null
- Bước 2: Cập nhật những cạnh với n vòng lặp(n là số node) sao cho tới lối đi kể từ
source node
cho tớinode bị lặp
là lớn số 1 .
Giải quí vị pseudocode:
for i from 1 to tướng size(danh_sách_đỉnh)-1:
for each (u,v) in danh_sách_cung:
if khoảng_cách(v) > khoảng_cách(u) + trọng_số(u,v):
khoảng_cách(v):= khoảng_cách(u) + trọng_số(u,v)
đỉnh_liền_trước(v):= u
- Bước 3: Kiểm tra coi vật thị với quy trình âm hoặc không?
for each (u,v) in danh_sách_cung:
if khoảng_cách(v) > khoảng_cách(u) + trọng_số(u,v):
error "Đồ thị chứa chấp quy trình âm"
2. Giải vấn đề cụ thể
Giả sử bản thân với vật thị trọng số như sau:
Ta tiếp tục đi kiếm lối đi sớm nhất kể từ node 1
cho tới những node sót lại .
Bước 1: Ta khởi tạo nên vật thị với khoảng cách kể từ node 1 cho tới chủ yếu nó là 0, sót lại là infinity
Bước 2: Thực hiện tại 4 vòng lặp .
Ở vòng lặp đầu tiên, tao update được lối đi sớm nhất trải qua những cạnh (1, 2); (1, 3); (1, 4):
Ở vòng lặp số 2, cạnh (2, 5) và (3, 4) là những cạnh tối ưu:
Ở vòng lặp số 3, tao chỉ thấy với cạnh (4,5) nâng cấp lối đi từ là một -> 5 :
Ở vòng lặp số 4, tao nhận biết không thể cạnh nào là rất có thể tối ưu được lối đi kể từ node 1 nữa, vậy nên vật thị này tiếp tục không tồn tại quy trình âm. Suy rời khỏi tao rất có thể kết cổ động thuật toán bên trên phía trên.
Xem thêm: cổng ps/2 có màu tím được dùng để kết nối với thiết bị nào sau đây
Và thành quả tao đạt được là những shortest path kể từ node 1 như sau:
- Từ 1 cho tới 2:
1 -> 2
- Từ 1 cho tới 3:
1 -> 3
- Từ 1 cho tới 4:
1 -> 3 -> 4
- Từ 1 cho tới 5:
1 -> 3 -> 4 ->5
3. Thiết tiếp giải thuật vị code ruby
Đầu tiên, bản thân sẽ khởi tạo 1 class nhằm khởi tạo nên những đối tượng người tiêu dùng node:
class Node
attr_accessor :name, :graph
def initialize(name)
@name = name
end
end
Và 1 class nhằm khởi tạo nên những cạnh.
class Edge
attr_accessor :from, :to, :weight
def initialize(from, to, weight)
@from, @to, @weight = from, to, weight
end
def <=>(other)
self.weight <=> other.weight
end
end
Mỗi đối tượng người tiêu dùng cạnh với 3 nằm trong tính:
@from
,@to
: là 2 node của cạnh .@weight
: phỏng lâu năm cạnh
Mình thêm một method <=>
nhằm rất có thể đối chiếu phỏng lâu năm những cạnh cùng nhau .
Ta tạo nên 1 class nhằm khởi tạo nên vật thị :
class Graph
attr_accessor :nodes
attr_accessor :edges
def initialize
@nodes = []
@edges = []
end
def add_node(node)
nodes << node
node.graph = self
end
def add_edge(from, to, weight)
edges << Edge.new(from, to, weight)
end
end
Hai methods add_node
và add_class
sẽ hỗ trợ bản thân đánh giá được vật thị.
Giờ bản thân sẽ khởi tạo 1 class chủ yếu nhằm giải quyết và xử lý vấn đề.
class BellmanFord
def initialize(graph, source_node)
@graph = graph
@source_node = source_node
@path_to = {}
@distance_to = {}
compute_shortest_path
end
def shortest_path_to(node)
path = []
while node != @source_node
path.unshift(node)
node = @path_to[node]
end
path.unshift(@source_node).map { |node| node.name }
end
private
def compute_shortest_path
update_distance_of_all_edges_to(Float::INFINITY)
@distance_to[@source_node] = 0
@graph.nodes.size.times do
@graph.edges.each do |edge|
relax(edge)
end
end
end
def update_distance_of_all_edges_to(distance)
@graph.nodes.each do |node|
@distance_to[node] = distance
end
end
def relax(edge)
if @distance_to[edge.to] > @distance_to[edge.from] + edge.weight
@distance_to[edge.to] = @distance_to[edge.from] + edge.weight
@path_to[edge.to] = edge.from
end
end
end
Khi 1 vấn đề được khởi tạo nên, ứng với cùng một instance
của class BellmanFord
, sẽ sở hữu 2 thông số tương tự với dữ khiếu nại của vấn đề là:
@graph
: là 1 trong thể hiện tại của lớpGraph
- cũng chính là vật thị của vấn đề .@soure_node
: là node đích của vấn đề . Ta tiếp tục lần lối đi sớm nhất của những node sót lại cho tới node này.
Và thành quả của vấn đề ở trong biến đổi @path_to
- nó là 1 trong Hash chứa chấp những node kề nhưng mà 1 node nên nối cho tới để sở hữu được lối đi sớm nhất.
Với vấn đề vật thị như vậy này:
Mình tiếp tục demo chạy vấn đề như sau:
Khởi tạo nên những node của vật thị:
@graph = Graph.new
@graph.add_node(@node1 = Node.new("Node #1"))
@graph.add_node(@node2 = Node.new("Node #2"))
@graph.add_node(@node3 = Node.new("Node #3"))
@graph.add_node(@node4 = Node.new("Node #4"))
@graph.add_node(@node5 = Node.new("Node #5"))
Khởi tạo nên những cạnh cho tới vật thị:
#Các cạnh kể từ node1
@graph.add_edge(@node1, @node2, 2)
@graph.add_edge(@node1, @node3, 3)
@graph.add_edge(@node1, @node4, 7)
#Các cạnh kể từ node2
@graph.add_edge(@node2, @node4, 3)
@graph.add_edge(@node2, @node5, 5)
#Cạnh kể từ node3
@graph.add_edge(@node3, @node4, -2)
#Cạnh kể từ node4
@graph.add_edge(@node4, @node5, 2)
Giờ tao tiếp tục giải vấn đề lần lối đi sớm nhất kể từ node1
cho tới những node sót lại vô cùng đơn giản:
Xem thêm: khái quát văn học việt nam từ cách mạng tháng tám năm 1945 đến hết the kỉ 20
bai_toan_1 = BellmanFord.new(@graph, @node1).shortest_path_to(@node2)
=> ["Node #1", "Node #2"]
bai_toan_2 = BellmanFord.new(@graph, @node1).shortest_path_to(@node3)
=> ["Node #1", "Node #3"]
bai_toan_3 = BellmanFord.new(@graph, @node1).shortest_path_to(@node4)
=> ["Node #1", "Node #3", "Node #4"]
bai_toan_4 = BellmanFord.new(@graph, @node1).shortest_path_to(@node5)
=> ["Node #1", "Node #3", "Node #4", "Node #5"]
References:
https://www.geeksforgeeks.org/bellman-ford-algorithm-dp-23/
https://thuytrangcoding.wordpress.com/2018/03/19/graph-shortestpath-bellmanford/
Bình luận