THUẬT TOÁN BELLMAN-FORD TÌM ĐƯỜNG ĐI NGẮN NHẤT

Nơi tổng hòa hợp và chia sẻ những kiến thức và kỹ năng liên quan lại tới lời giải nói tầm thường và định hướng khoa học máy vi tính nói riêng.

Bạn đang xem: Thuật toán bellman-ford tìm đường đi ngắn nhất


‹ Thuật toán Dijkstra tìm đường đi ngắn nhất xuất phát từ một đỉnh-- Dijkstra Algorithm • Quy hoạch đụng tìm đường đi ngắn độc nhất vô nhị giữa đông đảo cặp đỉnh---Floyd-Warshall Algorithm ›


Thuật toán Bellman-Ford tìm lối đi ngắn nhất xuất phát từ một đỉnh trong vật thị tất cả trọng số âm -- Bellman Ford Algorithm

January 20, năm 2016 in Uncategorized | No comments


Bài trước họ đã khám phá thuật toán Dijkstra tìm lối đi ngắn nhất từ 1 đỉnh tới hầu như đỉnh khác trong đồ vật thị được đặt theo hướng với trọng số không âm trong thời gian $O(E + Vlog V)$. Nếu đồ vật thị bao gồm trọng số âm, bọn họ sẽ không thể vận dụng thuật toán Dijkstra được (tại sao?). Trong trường phù hợp này, họ sẽ áp dụng thuật toán Bellman Ford và đó cũng là nội dung bao gồm của bài viết này.

Điểm đặc biệt của đố thị tất cả trọng số âm là hoàn toàn có thể có sự mở ra của chu trình âm, là chu trình mà tổng trọng số những cạnh nhỏ tuổi hơn $0$. Sự lộ diện của quy trình âm tạo cho bài toán trở bắt buộc không xác định. Lấy một ví dụ trong hình bên dưới đây, ta gồm một chu trình âm là $a ightarrow b ightarrow c ightarrow d ightarrow a$. Ta muốn tìm đường đi ngắn tốt nhất từ đỉnh $s$ mang lại đỉnh $t$. Ta có thể đi từ bỏ $s$ mang lại $a$ tiếp đến đi xung quanh chu trình âm vô hạn lần, trước khi ta đi cho $t$. Như vậy, lối đi ngắn duy nhất từ $s$ cho $t$ là không xác minh (hoặc rất có thể coi là âm vô hạn).

*

Remark Nếu họ biết trước được $G$ không tồn tại chu trình âm thì họ không tuyệt nhất thiết cần chạy không còn $|V|-2$ vòng lặp nhưng mà ta hoàn toàn có thể dừng ngay trong khi đồ thị $G$ không thể cung căng nữa.

Thuật toán Bellman-Ford với quy hoạch động

Ta rất có thể phát biểu lại thuật toán Bellman-Ford dưới ánh mắt của quy hoạch động.

Gọi $d$ là độ nhiều năm của đường đi ngắn nhất từ $s$ mang lại $v$ trải qua tối đa $i$ đỉnh.

Ta đã khởi tạo, $d<0> = w(s ightarrow v)$ cùng $d = +infty$ với đa số $i > 0$. Do đường đi ngắn độc nhất vô nhị từ $s$ mang lại $v$ trong đồ thị không có chu trình âm trải qua tối đa $V-2$ đỉnh, ta có:

$delta(s,v) = d qquad (2)$

Từ định nghĩa của $d$, ta bao gồm công thức đệ quy sau:

$d = min_u: (u ightarrow v) in E(d + w(u ightarrow v))qquad (3)$

Ý nghĩa của cách làm đệ quy bên trên là như sau: Nếu điện thoại tư vấn $s ightarrow ldots ightarrow u ightarrow v$ là 1 trong đường đi ngắn nhất từ $s$ tới $v$ trải qua tối đa $i$ đỉnh thì đường đi con $s ightarrow ldots ightarrow u$ là đường đi ngắn duy nhất từ $s$ cho tới $u$ trải qua tối nhiều $i-1$ đỉnh. Bởi vì đó, $d = d + w(u ightarrow v)$. Do ta phân vân $u$, ta đã lặp qua tất cả các đỉnh $u$ mà lại $u ightarrow v in vecE$ rồi mang giá trị nhỏ tuổi nhất.

Ta có thuật toán sau:


DynamicBellmanFordA($G(V,vecE), w, s$): for each $v in V$ $d<0> leftarrow w(s ightarrow v)$ for $i leftarrow 1$ khổng lồ $V-2$ for each $v in V$ for each $u ightarrow v in vecE$ $d = min(d + w(u ightarrow v), d)$ đầu ra $d$ as the shortest distance of $v$

Phân tích thuật toán: Ta đã phân tích nhì vòng lặp for trong cùng của gỉa mã trên. Với từng đỉnh $v in V$, ta sẽ ưng chuẩn qua các đỉnh $u$ mà có một cung $u ightarrow v in vecE$. Vày đó, số vòng lặp của nhị vòng for trong cùng là:

$sum_v in Vdeg^+(v) = O(E) qquad (4)$

trong kia $deg^+(v)$ là bậc tới của đỉnh $v$. Như vậy thời hạn của thuật toán là $O(VE)$. Bộ nhớ của thuật toán sử dụng là $O(V^2)$ vì chưng ta sử dụng mảng hai phía $d$.

Tuy nhiên, ta rất có thể quan gần kề thấy dòng $d<1,2,ldots, V>$ của bảng hai chiều $d$ chỉ phụ thuộc vào cái trước đó $d<1,2,ldots, V>$ của bảng này, bởi vì đó, ta rất có thể giảm bộ nhớ bằng cách chỉ dùng mảng 1 chiều. Thuật toán hoàn toàn có thể viết lại như sau:


DynamicBellmanFordB($G(V,vecE), w, s$): for each $v in V$ $d<0> leftarrow w(s ightarrow v)$ for $i leftarrow 1$ to lớn $V-2$ for each $v in V$ for each $u ightarrow v in vecE$ $d = min(d + w(u ightarrow v), d) qquad (*)$ output $d$ as the shortest distance of $v$

Để ý trong cái $(*)$ của thuật toán DynamicBellmanFordB, gía trị $d$ chỉ được update khi còn chỉ khi cung $d DynamicBellmanFordC($G(V,vecE), w, s$): for each $v in V$ $d<0> leftarrow w(s ightarrow v)$ for $i leftarrow 1$ lớn $V-2$ for each $v in V$ for each $u ightarrow v in vecE$ if $(u ightarrow v)$ is tense Relax($u ightarrow v$) đầu ra $d$ as the shortest distance of $v$

Thực chất hai vòng for vào cùng chính là duyệt qua tất cả các cạnh của $G$ cùng nới lỏng các cạnh bị căng. Bởi đó, thu gọn lại thuật toán DynamicBellmanFordC ta vẫn thu được thuật toán Bellman-Ford ban đầu.

Remarks Như vẫn phân tích sống trên, ta nên tối đa $V-2$ vòng lặp (ngoài cùng) để nới lỏng các cung căng với sau $V-2$ vòng lặp đó, nhãn của các đỉnh chính là đường đi ngắn nhất. Khoác dù cho đến bây giờ chưa bao gồm thuật toán nào tất cả thời gian xuất sắc hơn $O(VE)$ về phương diện lý thuyết, ta vẫn hoàn toàn có thể tăng tốc thuật toán Bellman-Ford trong thực tế. Thừa nhận xét thấy trong giả mã BellmanFord làm việc trên, ta không suy xét thứ tự những đỉnh tốt cung mà lại ta đã nới lỏng.

Xem thêm: Xem Phim Cuộc Chiến Sắc Đẹp Tập 1 Vietsub, Cuộc Chiến Sắc Đẹp

Năm 1970, Yen <2> giới thiệu một đồ vật tự để nới lỏng những đỉnh, bớt số vòng lặp kế bên cùng xuống còn kích thước $V/2$. Năm 2012, Bannister với Eppstein <6> minh chứng rằng nếu đồ vật tự những đinh thả lỏng được chọn tự dưng thì sau $V/3$ vòng lặp, với phần trăm cao, họ sẽ kiếm được đường đi ngắn nhất.

Chú ý sau cuối đó là thuật toán Bellman-Ford không thể áp dụng được đến đồ thị vô hướng có trọng số âm. Vì sao là khi ta đưa mỗi cạnh vô phía thành nhị cạnh có hướng ngược chiều nhau, cạnh vô phía với trọng số âm đang trở thành quy trình âm trong thứ thị. Bài toán đường đi ngắn độc nhất trong đồ thị vô hướng không tồn tại chu trình âm cạnh tranh hơn khôn xiết nhiều.

Code đầy đủ: bellman-ford-matrix-representation, bellman-ford-list-represetation.

Tham khảo

<1> Bellman, Richard. On a routing problem. Quarterly of Applied Mathematics 16: 87–90, 1958.<2> Ford Jr., Lester R. Network Flow Theory. Paper P-923. Santa Monica, California: RAND Corporation, 1956.<3> Jeff Erickson. Lecture Notes on Single Source Shortest Paths, UIUC, 2014.<4> Uri Zwick. Lecture Notes on Shortest Paths, Tel Aviv University, 2009.<5> Yen, Jin Y. An algorithm for finding shortest routes from all source nodes khổng lồ a given destination in general networks. Quarterly of Applied Mathematics 27: 526–530, 1970.<6> Bannister, M. J.; Eppstein, D. Randomized speedup of the Bellman–Ford algorithm. Analytic Algorithmics & Combinatorics (ANALCO12), Kyoto, Japan. Pp. 41–47, 2012.