Thuật toán Bellman Ford và ứng dụng

Thứ Sáu, 07/10/2022

Tram Ho

Tổng quan

Thuật toán Bellman-Ford là thuật toán dùng để tìm đường đi ngắn nhất từ một đỉnh tới các đỉnh còn lại trong đồ thị có trọng số. Cùng một vấn đề nhưng thuật toán Bellman-Ford chậm hơn so với thuật toán Dijsktra nhưng lại đa năng hơn ở chỗ thuật toán có thể xử lý trên đồ thị có cạnh mang trọng số âm. Thuật toán được đề xuất lần đầu tiên bởi Alfonso Shimbel (1955), nhưng được đặt tên theo Richard Bellman và Lester Ford Jr. Hai người đã công bố thuật toán lần lượt vào năm 1958 và 1956.

Kĩ thuật

Đặt vấn đề

Cho đồ thị như sau:

Tìm đường đi ngắn nhất giữa đỉnh 1 với các đỉnh còn lại trong đồ thị.

Nếu đồ thị có cạnh trọng số âm, cách cài đặt thuật toán tìm đường đi ngắn nhất Dijkstra cổ điển sẽ thất bại. Cách cài đặt cải tiến sẽ giúp cho thuật toán Dijkstra khắc phục vấn đề này. Tuy nhiên khi đồ thị có chu trình âm, cách cài đặt cải tiến này cũng không sử dụng được do thuật toán sẽ thực hiện vòng lặp vô hạn.

Thuật toán Bellman Ford sẽ giải quyết vấn đề này. Ý tưởng chính rất đơn giản đó là

Mô tả thuật toán

Ta xét ví dụ với đồ thị có hướng trên (giả định các đường đi là một chiều, chỉ đi từ đỉnh có số thứ tự thấp hơn tới đỉnh có số thứ tự cao hơn, số có màu đỏ cạnh mỗi đỉnh là độ dài đường đi ngắn nhất từ gốc tới đỉnh đó, và đỉnh gốc là đỉnh 1).

Khởi tạo:

Imgur

Thực hiện lần duyệt đầu tiên, ta cập nhật được đường đi ngắn nhất thông qua các cạnh (1, 2); (1, 3); (1, 4):

Imgur

Tương tự với lần duyệt thứ 2, cạnh (2, 5) và (3, 4) là các cạnh tối ưu:

Imgur

Với lần duyệt thứ 3, chỉ có cạnh (4, 5) cải tiến đường đi tối ưu:

Imgur
Tới lần duyệt thứ 4, ta thấy không còn cạnh nào có thể tối ưu hóa bất kỳ đường đi ngắn nhất nào nữa. Tới đây, ta hoàn toàn có thể dừng duyệt (vì chắc chắn việc không còn cạnh có thể tối ưu cũng đồng nghĩa với việc không có chu trình âm trong đồ thị).

Mã giả:

 function <span class="token function">BellmanFord</span><span class="token punctuation">(</span>danh_sách_đỉnh<span class="token punctuation">,</span> danh_sách_cung<span class="token punctuation">,</span> nguồn<span class="token punctuation">)</span>
   <span class="token comment">// hàm yêu cầu đồ thị đưa vào dưới dạng một danh sách đỉnh, một danh sách cung</span>
   <span class="token comment">// hàm tính các giá trị khoảng_cách và đỉnh_liền_trước của các đỉnh,</span>
   <span class="token comment">// sao cho các giá trị đỉnh_liền_trước sẽ lưu lại các đường đi ngắn nhất.</span>

   <span class="token comment">// bước 1: khởi tạo đồ thị</span>
   <span class="token keyword">for</span> each v in danh_sách_đỉnh<span class="token operator">:</span>
       <span class="token keyword">if</span> v is nguồn then khoảng_cá<span class="token function">ch</span><span class="token punctuation">(</span>v<span class="token punctuation">)</span><span class="token operator">:</span><span class="token operator">=</span> <span class="token number">0</span>
       <span class="token keyword">else</span> khoảng_cá<span class="token function">ch</span><span class="token punctuation">(</span>v<span class="token punctuation">)</span><span class="token operator">:</span><span class="token operator">=</span> vô cùng
       đỉnh_liền_trướ<span class="token function">c</span><span class="token punctuation">(</span>v<span class="token punctuation">)</span><span class="token operator">:</span><span class="token operator">=</span> null

   <span class="token comment">// bước 2: kết nạp cạnh</span>
   <span class="token keyword">for</span> i from <span class="token number">1</span> to <span class="token function">size</span><span class="token punctuation">(</span>danh_sách_đỉnh<span class="token punctuation">)</span><span class="token operator">-</span><span class="token number">1</span><span class="token operator">:</span>
       <span class="token keyword">for</span> <span class="token function">each</span> <span class="token punctuation">(</span>u<span class="token punctuation">,</span>v<span class="token punctuation">)</span> in danh_sách_cung<span class="token operator">:</span>
           <span class="token keyword">if</span> khoảng_cá<span class="token function">ch</span><span class="token punctuation">(</span>v<span class="token punctuation">)</span> <span class="token operator">&gt;</span> khoảng_cá<span class="token function">ch</span><span class="token punctuation">(</span>u<span class="token punctuation">)</span> <span class="token operator">+</span> trọng_số<span class="token punctuation">(</span>u<span class="token punctuation">,</span>v<span class="token punctuation">)</span><span class="token operator">:</span>
               khoảng_cá<span class="token function">ch</span><span class="token punctuation">(</span>v<span class="token punctuation">)</span><span class="token operator">:</span><span class="token operator">=</span> khoảng_cá<span class="token function">ch</span><span class="token punctuation">(</span>u<span class="token punctuation">)</span> <span class="token operator">+</span> trọng_số<span class="token punctuation">(</span>u<span class="token punctuation">,</span>v<span class="token punctuation">)</span>
               đỉnh_liền_trướ<span class="token function">c</span><span class="token punctuation">(</span>v<span class="token punctuation">)</span><span class="token operator">:</span><span class="token operator">=</span> u

   <span class="token comment">// bước 3: kiểm tra chu trình âm</span>
   <span class="token keyword">for</span> <span class="token function">each</span> <span class="token punctuation">(</span>u<span class="token punctuation">,</span>v<span class="token punctuation">)</span> in danh_sách_cung<span class="token operator">:</span>
       <span class="token keyword">if</span> khoảng_cá<span class="token function">ch</span><span class="token punctuation">(</span>v<span class="token punctuation">)</span> <span class="token operator">&gt;</span> khoảng_cá<span class="token function">ch</span><span class="token punctuation">(</span>u<span class="token punctuation">)</span> <span class="token operator">+</span> trọng_số<span class="token punctuation">(</span>u<span class="token punctuation">,</span>v<span class="token punctuation">)</span><span class="token operator">:</span>
           error <span class="token string">"Đồ thị chứa chu trình âm"</span>

function BellmanFord(danh_sách_đỉnh, danh_sách_cung, nguồn)

// hàm yêu cầu đồ thị đưa vào dưới dạng một danh sách đỉnh, một danh sách cung

// hàm tính các giá trị khoảng_cách và đỉnh_liền_trước của các đỉnh,

// sao cho các giá trị đỉnh_liền_trước sẽ lưu lại các đường đi ngắn nhất.

// bước 1: khởi tạo đồ thị

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):= vô cùng

đỉnh_liền_trước(v):= null

// bước 2: kết nạp cạnh

for i from 1 to 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)

// bước 3: kiểm tra chu trình âm

error "Đồ thị chứa chu trình âm"

Cài đặt

Code:


<span class="token comment">// Thuat toan voi do thi khong co chu trinh am</span>

<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;bits/stdc++.h&gt;</span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>

<span class="token keyword">typedef</span> pair<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token punctuation">,</span> <span class="token keyword">int</span><span class="token operator">&gt;</span> ii<span class="token punctuation">;</span>
vector<span class="token operator">&lt;</span>ii<span class="token operator">&gt;</span> a<span class="token punctuation">[</span><span class="token number">181220</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> n<span class="token punctuation">,</span> m<span class="token punctuation">;</span>

<span class="token keyword">int</span> d<span class="token punctuation">[</span><span class="token number">181220</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">bool</span> inqueue<span class="token punctuation">[</span><span class="token number">181220</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> pre<span class="token punctuation">[</span><span class="token number">181220</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span>path<span class="token punctuation">;</span>

<span class="token keyword">void</span> <span class="token function">bellman</span><span class="token punctuation">(</span><span class="token keyword">int</span> u<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token comment">//Buoc 1: Khoi tao</span>
    queue<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> qu<span class="token punctuation">;</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> d<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">99999999</span><span class="token punctuation">;</span>
    d<span class="token punctuation">[</span>u<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
    qu<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>u<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">//push u vào queue</span>
    inqueue<span class="token punctuation">[</span>u<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token boolean">true</span><span class="token punctuation">;</span> <span class="token comment">//Đánh dấu đỉnh u đã trong queue</span>
    <span class="token comment">// Buoc 2: Lap</span>
    <span class="token keyword">while</span> <span class="token punctuation">(</span>qu<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        u <span class="token operator">=</span> qu<span class="token punctuation">.</span><span class="token function">front</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">//Lấy giá trị đầu của queue</span>
        inqueue<span class="token punctuation">[</span>u<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token boolean">false</span><span class="token punctuation">;</span> <span class="token comment">//Đánh dấu là đỉnh u đã pop ra khỏi queue (hay không còn trong queue)</span>
        qu<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// pop đỉnh u ra khỏi queue</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> a<span class="token punctuation">[</span>u<span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// Duyệt các đỉnh kề u</span>
            <span class="token keyword">int</span> v <span class="token operator">=</span> a<span class="token punctuation">[</span>u<span class="token punctuation">]</span><span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>second<span class="token punctuation">;</span>
            <span class="token keyword">int</span> uv <span class="token operator">=</span> a<span class="token punctuation">[</span>u<span class="token punctuation">]</span><span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>first<span class="token punctuation">;</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>d<span class="token punctuation">[</span>v<span class="token punctuation">]</span> <span class="token operator">&gt;</span> d<span class="token punctuation">[</span>u<span class="token punctuation">]</span> <span class="token operator">+</span> uv<span class="token punctuation">)</span> <span class="token punctuation">{</span>
                d<span class="token punctuation">[</span>v<span class="token punctuation">]</span> <span class="token operator">=</span> d<span class="token punctuation">[</span>u<span class="token punctuation">]</span> <span class="token operator">+</span> uv<span class="token punctuation">;</span>
                pre<span class="token punctuation">[</span>v<span class="token punctuation">]</span> <span class="token operator">=</span> u<span class="token punctuation">;</span>
                <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span>inqueue<span class="token punctuation">[</span>v<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// Nếu đỉnh v chưa trong queue</span>
                    qu<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>v<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// Cho v vào queue</span>
                    inqueue<span class="token punctuation">[</span>v<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token boolean">true</span><span class="token punctuation">;</span> <span class="token comment">// Đánh dấu là đỉnh v đã trong queue</span>
                <span class="token punctuation">}</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">int</span> u<span class="token punctuation">,</span> v<span class="token punctuation">;</span> <span class="token comment">// dinh nguon va dinh dich</span>
    <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%d%d%d%d"</span><span class="token punctuation">,</span> <span class="token operator">&amp;</span>n<span class="token punctuation">,</span> <span class="token operator">&amp;</span>m<span class="token punctuation">,</span> <span class="token operator">&amp;</span>u<span class="token punctuation">,</span> <span class="token operator">&amp;</span>v<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">while</span> <span class="token punctuation">(</span>m<span class="token operator">--</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">int</span> p<span class="token punctuation">,</span> q<span class="token punctuation">,</span> w<span class="token punctuation">;</span>
        <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%d%d%d"</span><span class="token punctuation">,</span> <span class="token operator">&amp;</span>p<span class="token punctuation">,</span> <span class="token operator">&amp;</span>q<span class="token punctuation">,</span> <span class="token operator">&amp;</span>w<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token comment">// Do thi vo huong</span>
        a<span class="token punctuation">[</span>p<span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span><span class="token function">ii</span><span class="token punctuation">(</span>w<span class="token punctuation">,</span> q<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        a<span class="token punctuation">[</span>q<span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span><span class="token function">ii</span><span class="token punctuation">(</span>w<span class="token punctuation">,</span> p<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    <span class="token function">bellman</span><span class="token punctuation">(</span>u<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%dn"</span><span class="token punctuation">,</span> d<span class="token punctuation">[</span>v<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> v<span class="token punctuation">;</span> i <span class="token operator">!=</span> u<span class="token punctuation">;</span>  i <span class="token operator">=</span> pre<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span> path<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span>i<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// them dinh vao duong di</span>
    path<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span>u<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">reverse</span><span class="token punctuation">(</span>path<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> path<span class="token punctuation">.</span><span class="token function">end</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"Duong di: "</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> path<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
    	<span class="token keyword">if</span><span class="token punctuation">(</span>i <span class="token operator">==</span> path<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
    		<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%d"</span><span class="token punctuation">,</span> v<span class="token punctuation">)</span><span class="token punctuation">;</span>
    		<span class="token keyword">break</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>
   	<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%d -&gt; "</span><span class="token punctuation">,</span>path<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>

// Thuat toan voi do thi khong co chu trinh am

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> ii;

vector<ii> a[181220];

int n, m;

int d[181220];

bool inqueue[181220];

int pre[181220];

vector<int>path;

void bellman(int u) {

//Buoc 1: Khoi tao

queue<int> qu;

for (int i = 1; i <= n; i++) d[i] = 99999999;

d[u] = 0;

qu.push(u); //push u vào queue

inqueue[u] = true; //Đánh dấu đỉnh u đã trong queue

// Buoc 2: Lap

while (qu.size()) {

u = qu.front(); //Lấy giá trị đầu của queue

inqueue[u] = false; //Đánh dấu là đỉnh u đã pop ra khỏi queue (hay không còn trong queue)

qu.pop(); // pop đỉnh u ra khỏi queue

for (int i = 0; i < a[u].size(); i++) { // Duyệt các đỉnh kề u

int v = a[u][i].second;

int uv = a[u][i].first;

if (d[v] > d[u] + uv) {

d[v] = d[u] + uv;

pre[v] = u;

if (!inqueue[v]) { // Nếu đỉnh v chưa trong queue

qu.push(v); // Cho v vào queue

inqueue[v] = true; // Đánh dấu là đỉnh v đã trong queue

}

int main() {

int u, v; // dinh nguon va dinh dich

scanf("%d%d%d%d", &n, &m, &u, &v);

while (m--) {

int p, q, w;

scanf("%d%d%d", &p, &q, &w);

// Do thi vo huong

a[p].push_back(ii(w, q));

a[q].push_back(ii(w, p));

}

bellman(u);

printf("%dn", d[v]);

for(int i = v; i != u; i = pre[i]) path.push_back(i); // them dinh vao duong di

path.push_back(u);

reverse(path.begin(), path.end());

printf("Duong di: ");

for(int i = 0; i < path.size(); i++){

if(i == path.size() - 1){

printf("%d", v);

break;

}

printf("%d -> ",path[i]);

}

Độ phức tạp thời gian trong trường hợp tốt nhất:
$O (∣ E ∣)$
Độ phức tạp thời gian trung bình:
$O (∣ E ∣.∣ V ∣)$
Độ phức tạp thời gian trong trường hợp xấu nhất:
$O (∣ E ∣.∣ V ∣)$

Ứng dụng thuật toán

Một biến thể phân tán của thuật toán Bellman-Ford được dùng trong các giao thức định tuyến vector khoảng cách, chẳng hạn giao thức RIP (Routing Information Protocol). Đây là biến thể phân tán vì nó liên quan đến các nút mạng (các thiết bị định tuyến) trong một hệ thống tự động (autonomous system), ví dụ một tập các mạng IP thuộc sở hữu của một nhà cung cấp dịch vụ Internet (ISP).

Thuật toán gồm các bước sau:

Mỗi nút tính khoảng cách giữa nó và tất cả các nút khác trong hệ thống tự động và lưu trữ thông tin này trong một bảng.
Mỗi nút gửi bảng thông tin của mình cho tất cả các nút lân cận.
Khi một nút nhận được các bảng thông tin từ các nút lân cận, nó tính các tuyến đường ngắn nhất tới tất cả các nút khác và cập nhật bảng thông tin của chính mình.

Nhược điểm chính của thuật toán Bellman-Ford trong cấu hình này là:

Không nhân rộng tốt.
Các thay đổi của tô-pô mạng không được ghi nhận nhanh do các cập nhật được lan truyền theo từng nút một.
Đếm dần đến vô cùng (nếu liên kết hỏng hoặc nút mạng hỏng làm cho một nút bị tách khỏi một tập các nút khác, các nút này vẫn sẽ tiếp tục ước tính khoảng cách tới nút đó và tăng dần giá trị tính được, trong khi đó còn có thể xảy ra việc định tuyến thành vòng tròn).

Tổng kết

Đặc điểm đồ thị	BFS O(V+E)O(V+E) $O (V + E)$	Dijsktra O((V+E)log⁡V)O((V+E) log V) $O ((V + E) lo g V)$	Bellman Ford O(VE)O(VE) $O (V E)$	Floyd Warshall O(V3)O(V^3) $O (V^{3})$
Kích thước đồ thị có thể áp dụng	V,E≤10MV,E le 10M $V, E \leq 10 M$	V,E≤300KV,E le 300K $V, E \leq 300 K$	VE≤10MVE le 10M $V E \leq 10 M$	V≤400V le 400 $V \leq 400$
Không trọng số	Tốt nhất	Ổn	Tệ	Đa phần là tệ
Có trọng số	WA	Tốt nhất	Ổn	Đa phần là tệ
Trọng số âm	WA	Ổn	Ổn	Đa phần là tệ
Chu trình âm	Không xác định được	Không xác định được	Xác định được	Xác định được
Đồ thị nhỏ	WA nếu có trọng số	Lấy dao mổ trâu giết gà	Lấy giao mổ trâu giết gà	Tốt nhất

Tài liệu tham khảo

Giải thuật và lập trình – Thầy Lê Minh Hoàng
cp-algorithms.com
Handbook Competitive Programming – Antti Laaksonen
Competitve programming 3 – Steven Halim, Felix Halim
https://sites.google.com/site/kc97ble/algorithm-graph/fordbellmanqueue-cpp

Chia sẻ bài viết ngay

Nguồn bài viết : Viblo

Thuật toán Bellman Ford và ứng dụng

Tổng quan

Kĩ thuật

Đặt vấn đề

Mô tả thuật toán

Cài đặt

Ứng dụng thuật toán

Tổng kết

Tài liệu tham khảo

TikTok trở thành nền tảng mảng xã hội lớn thứ hai ở Nam Phi

Mất giá nhanh nhất sau 9 tháng ra mắt, iPhone 14 Pro Max tiếp tục phá đáy tại Việt Nam

Hướng dẫn sử dụng ngôn ngữ R cho người mới bắt đầu

10 plugin cần thiết của SublimeText dành cho các lập trình viên JavaScript