Giải bài toán tìm đường đi ngắn nhất bằng giải thuật Bellman-Ford với code Ruby

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ới node 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ớp Graph - 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"]