Thuật toán bellman-ford tìm đường đi ngắn nhất

Giải thuật Dijkstra nhỏng mình đã giới thiệu lần trước rất có thể giải quyết và xử lý khôn xiết nkhô hanh bài xích toán search lối đi nđính nhất cùng với đồ thị trọng số dương. (Các bạn có thể coi nội dung bài viết về giải thuật Dijkstra trên phía trên .

You watching: Thuật toán bellman-ford tìm đường đi ngắn nhất

Tuy nhiên, cùng với đồ dùng thị trọng số âm, chúng ta sẽ chọn giải thuật Bellman-Ford.Vậy trong nội dung bài viết này mình vẫn có tác dụng 2 điều:

Giới thiệu phương pháp giải bài bác tân oán shortest-path bằng lời giải Bellman-FordThiết kế lời giải này bởi code ruby.

1. Cách thuật toán Bellman-Ford hoạt động.

Về bài xích toán kiếm tìm đường đi ngắn tốt nhất, những chúng ta có thể coi đề bài sinh hoạt vào nội dung bài viết trước.

Ý tưởng của thuật toán thù như sau:

Ta triển khai để ý n lần, với n là số đỉnh của đồ gia dụng thị.Với những lần phê chuẩn, ta search tất cả các cạnh mà con đường đi qua cạnh đó sẽ tinh giảm đường đi nđính độc nhất trường đoản cú đỉnh nơi bắt đầu cho tới một đỉnh không giống.Ở lần chuyên chú thiết bị n, nếu như còn ngẫu nhiên cạnh nào hoàn toàn có thể rút ngắn đường đi, điều ấy minh chứng đồ vật thị gồm chu trình âm, và ta kết thúc thuật toán.

Thuật toán Bellman-Ford bao gồm 3 bước:

Cách 1: Khởi chế tạo ra trang bị thị

Giải mê thích bằng pseudocode:

for each v in danh_sách_đỉnh: if v is nguồn then khoảng_cách(v):= 0 else khoảng_cách(v):= cực kỳ đỉnh_liền_trước(v):= nullBước 2: Cập nhật các cạnh với n vòng lặp(n là số node) làm thế nào để cho lối đi từ bỏ source node mang đến node bị lặp là lớn số 1 .Giải thích hợp bởi pseudocode:

for i from 1 khổng lồ 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):= uBước 3: Kiểm tra coi đồ thị gồm quy trình âm giỏi 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ị đựng chu trình âm"

2. Giải bài xích tân oán thế thể

Giả sử bản thân gồm đồ gia dụng thị trọng số nlỗi sau:
*

Ta vẫn đi tìm kiếm đường đi ngắn nhất từ bỏ node 1 cho các node còn sót lại .

Cách 1: Ta khởi chế tạo đồ vật thị cùng với khoảng cách tự node 1 cho chủ yếu nó là 0, sót lại là infinity

*

Bước 2: Thực hiện 4 vòng lặp .

See more: Tính Chất Hóa Học Của Silic Là Kim Loại Hay Phi Kim Loại Ko Nhỉ ??? Help

Tại vòng lặp đầu tiên, ta update được đường đi ngắn thêm tuyệt nhất thông qua các cạnh (1, 2); (1, 3); (1, 4):

*

vòng lặp số 2, cạnh (2, 5) với (3, 4) là những cạnh tối ưu:

*

vòng lặp số 3, ta chỉ thấy bao gồm cạnh (4,5) nâng cấp đường đi từ 1 -> 5 :

*

vòng lặp số 4, ta nhận ra không hề cạnh như thế nào có thể về tối ưu được đường đi tự node 1 nữa, vậy phải đồ thị này sẽ không có quy trình âm. Suy ra ta hoàn toàn có thể kết thúc thuật toán trên trên đây.

Và tác dụng ta đạt được là những shorchạy thử path từ node 1 như sau:

Từ 1 mang đến 2: 1 -> 2Từ 1 đến 3: 1 -> 3Từ 1 cho 4: 1 -> 3 -> 4Từ 1 mang lại 5: 1 -> 3 -> 4 ->5

3. Thiết kế giải thuật bằng code ruby

Trước tiên, bản thân sẽ khởi tạo 1 class để tạo các đối tượng người tiêu dùng node:

class Node attr_accessor :name, :graph def initialize(name)
name = name endendVà 1 class để có thể tạo các cạnh.

class Edge attr_accessor :from, :to, :weight def initialize(from, khổng lồ, weight)
weight = from, khổng lồ, weight over def >(other) self.weight > other.weight endendMỗi đối tượng người sử dụng cạnh tất cả 3 nằm trong tính:


weight : độ dài cạnh

Mình thêm một method để rất có thể đối chiếu độ dài những cạnh với nhau .

Ta tạo nên 1 class để khởi tạo đồ gia dụng thị :

class Graph attr_accessor :nodes attr_accessor :edges def initialize
edges = <> end def add_node(node) nodes node node.graph = self end def add_edge(from, to lớn, weight) edges Edge.new(from, to lớn, weight) endendHai methods add_node với add_class sẽ giúp đỡ bản thân định hình được đồ vật thị.

Giờ mình sẽ tạo 1 class thiết yếu nhằm xử lý bài xích toán.

class BellmanFord def initialize(graph, source_node)
source_node).map node.name kết thúc private def compute_shortest_path update_distance_of_all_edges_to(Float::INFINITY)
path_to = edge.from over endendLúc 1 bài bác toán được khởi tạo thành, tương ứng với 1 instance của class BellmanFord, sẽ có 2 tsay mê số tương tự cùng với dữ kiện của bài bác toán thù là:


soure_node : là node đích của bài toán thù . Ta đã kiếm tìm đường đi nlắp độc nhất vô nhị của các node còn lại mang đến node này.

See more: Bị Chó Cắn, Tiêm Phòng Chó Dại Cắn Có Ảnh Hưởng Gì Không, Bị Chó Cắn, Tiêm Thuốc Phòng Dại Có Hại Sức Khỏe

Và tác dụng của bài xích tân oán phía trong thay đổi
path_lớn - nó là 1 Hash đựng các node kề mà 1 node nên nối cho để sở hữu được lối đi nthêm độc nhất vô nhị.

Với bài bác tân oán vật thị như vậy này:

*

Mình vẫn demo chạy bài toán nlỗi sau:

Khởi tạo thành các node của đồ dùng thị:


node5, 2)Giờ ta đang giải bài toán kiếm tìm lối đi nlắp độc nhất vô nhị từ node1 cho những node sót lại khôn xiết đối kháng giản:

bai_toan_1 = BellmanFord.new(
node5)=> <"Node #1", "Node #3", "Node #4", "Node #5">References:

https://www.geeksforgeeks.org/bellman-ford-algorithm-dp-23/


Chuyên mục: Blog