Toán tin vuotlen.com

Thuật toán Bellman-Ford

 

Phân loại Thông tin
Tên thuật toán Bellman-Ford (sử dụng cả ma trận kề và danh sách kề)
Phân loại thuật toán Quy hoạch động (Dynamic Programming), thuật toán tìm đường đi ngắn nhất
Cấu trúc dữ liệu Ma trận kề hoặc danh sách kề
Độ phức tạp thời gian (Worst Case) - O(V³) với ma trận kề
  - O(VE) với danh sách kề và hàng đợi ưu tiên
Độ phức tạp dung lượng - O(V²) với ma trận kề
  - O(V + E) với danh sách kề
Độ phức tạp bộ nhớ - O(V²) với ma trận kề
  - O(V + E) với danh sách kề
Phạm vi sử dụng Tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh khác trong đồ thị có trọng số không âm hoặc âm
Khả năng xử lý trọng số âm Có
Khả năng xử lý chu trình âm Có, nhưng chỉ báo cáo nếu tồn tại chu trình âm
Người phát hiện đầu tiên Richard Bellman (1958), Lester Ford (1956)
Ứng dụng ban đầu Tìm đường đi ngắn nhất trong mạng lưới
Ứng dụng hiện đại Phân tích tài chính, định tuyến mạng, tối ưu hóa, kiểm tra chu trình âm

 

Phân loại Thông tin
Ưu điểm - Có thể xử lý đồ thị với trọng số âm.
  - Phát hiện chu trình âm trong đồ thị.
  - Linh hoạt với cả ma trận kề và danh sách kề.
Nhược điểm - Độ phức tạp thời gian cao, đặc biệt là với đồ thị lớn khi sử dụng ma trận kề.
  - Đối với danh sách kề, cần sử dụng hàng đợi ưu tiên, làm tăng độ phức tạp thời gian.
  - Tiêu tốn nhiều bộ nhớ với đồ thị lớn.

Phạm vi sử dụng:

Thuật toán Bellman-Ford được sử dụng để tìm đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh khác trong một đồ thị có trọng số, với điều kiện đồ thị không có chu trình âm và có trọng số âm. Thuật toán này phù hợp cho các đồ thị có hướng (directed) và vô hướng (undirected).

Các ứng dụng của thuật toán Bellman-Ford:

Thuật toán Bellman-Ford có nhiều ứng dụng quan trọng trong các lĩnh vực khác nhau nhờ khả năng xử lý đồ thị có trọng số âm và phát hiện chu trình âm. Dưới đây là một số ứng dụng cụ thể của thuật toán này:

1. Mạng máy tính

Định tuyến (Routing)

2. Tài chính và Kinh tế

Phát hiện cơ hội arbitrage (Arbitrage Detection)

3. Định tuyến trong Hệ thống Giao thông

Định tuyến và Logistics

4. Mạng lưới Điện (Power Grid Networks)

Phân phối và Điều khiển

5. Lý thuyết đồ thị và Tối ưu hóa

Phân tích đồ thị

6. Hệ thống thông tin địa lý (GIS)

Phân tích mạng lưới

Chi Tiết Kỹ Thuật Thuật Toán Bellman-Ford:

Pseudo-code của thuật toán Bellman-Ford:

function BellmanFord(G, src):
    dist = [∞] * len(G)            // Khởi tạo khoảng cách từ nguồn đến tất cả các đỉnh là vô cùng
    pred = [-1] * len(G)           // Khởi tạo mảng tiền nhiệm cho mỗi đỉnh
    dist[src] = 0                  // Khoảng cách từ nguồn đến chính nó là 0

    for i from 1 to len(G)-1:      // Lặp lại V-1 lần (với V là số đỉnh trong đồ thị)
        for (u, v, w) in edges of G: // Duyệt qua tất cả các cạnh của đồ thị
            if dist[u] + w < dist[v]: // Nếu khoảng cách qua đỉnh u ngắn hơn khoảng cách hiện tại đến đỉnh v
                dist[v] = dist[u] + w // Cập nhật khoảng cách ngắn nhất đến đỉnh v
                pred[v] = u         // Cập nhật đỉnh tiền nhiệm của v là u

    for (u, v, w) in edges of G:    // Kiểm tra chu trình âm
        if dist[u] + w < dist[v]:   // Nếu có thể thư giãn thêm một lần nữa thì có chu trình âm
            print("Graph contains a negative-weight cycle") // Thông báo có chu trình âm
            return None             // Trả về None để biểu thị lỗi

    return dist, pred               // Trả về mảng khoảng cách và mảng tiền nhiệm


code C++:

//https://www.youtube.com/watch?v=yYLtkvqmEVk&ab_channel=MsIT
#include <iostream>
#include <vector>
#include <climits>
#include <queue>
#include <algorithm>

using namespace std;

#define V 5
#define INF INT_MAX

typedef pair<int, int> iPair;

// Mảng ánh xạ chỉ số đỉnh thành ký hiệu
char dinhKyHieu[V] = {'A', 'B', 'C', 'D', 'E'};

// Khởi tạo khoảng cách và đỉnh cha
void initializeSingleSource(int dist[], int truoc[], int source) {
    fill(dist, dist + V, INF);  // Đặt khoảng cách ban đầu của tất cả các đỉnh là vô hạn
    fill(truoc, truoc + V, -1); // Đặt tất cả các đỉnh cha là -1 (chưa có đỉnh cha)
    dist[source] = 0;           // Khoảng cách từ đỉnh nguồn đến chính nó là 0
}

// Relax các cạnh trong đồ thị
void relaxEdges(int graph[V][V], int dist[], int truoc[], priority_queue<iPair, vector<iPair>, greater<iPair>>& pq) {
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        for (int v = 0; v < V; ++v) {
            if (graph[u][v] != 0 && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];  // Cập nhật khoảng cách đến đỉnh v
                truoc[v] = u;                     // Ghi nhận đỉnh cha của v là u
                pq.push({dist[v], v});            // Thêm đỉnh v vào hàng đợi ưu tiên
            }
        }
    }
}

// Kiểm tra xem có chu trình trọng số âm không
bool detectNegativeCycle(int graph[V][V], int dist[]) {
    for (int u = 0; u < V; ++u) {
        for (int v = 0; v < V; ++v) {
            if (graph[u][v] != 0 && dist[u] != INF && dist[u] + graph[u][v] < dist[v]) {
                return true;  // Phát hiện chu trình trọng số âm
            }
        }
    }
    return false;
}

// In ra khoảng cách ngắn nhất từ đỉnh nguồn đến tất cả các đỉnh khác và đường đi tương ứng
void printSolution(int dist[], int truoc[], int source) {
    cout << "Dinh \t Khoang cach \t Duong di\n";
    for (int i = 0; i < V; i++) {
        cout << dinhKyHieu[source] << " -> " << dinhKyHieu[i] << "\t";
        if (dist[i] == INF)
            cout << "INF";
        else
            cout << dist[i];
        cout << "\t\t";
        if (dist[i] != INF) {
            vector<int> path;
            for (int v = i; v != -1; v = truoc[v]) {
                path.push_back(v);
            }
            reverse(path.begin(), path.end());  // Đảo ngược đường đi để in từ đỉnh nguồn đến đỉnh đích
            for (size_t j = 0; j < path.size(); j++) {
                cout << dinhKyHieu[path[j]];
                if (j < path.size() - 1)
                    cout << " -> ";
            }
        }
        cout << "\n";
    }
}

// Thuật toán Bellman-Ford
void bellmanFord(int graph[V][V], int source) {
    int dist[V];
    int truoc[V];

    initializeSingleSource(dist, truoc, source);  // Khởi tạo khoảng cách và đỉnh cha

    priority_queue<iPair, vector<iPair>, greater<iPair>> pq; // Priority queue lưu cặp (khoảng cách, đỉnh)
    pq.push({0, source});

    // Relax tất cả các cạnh (V-1) lần để chuẩn bị cho việc kiểm tra chu trình âm
    for (int i = 1; i < V; ++i) {
        relaxEdges(graph, dist, truoc, pq);
    }

    if (detectNegativeCycle(graph, dist)) {  // Kiểm tra chu trình trọng số âm
        cout << "Do thi chua chu trinh trong so am\n";
    } else {
        // Relax các cạnh lần nữa để tìm khoảng cách ngắn nhất
        relaxEdges(graph, dist, truoc, pq);
        printSolution(dist, truoc, source);  // In kết quả
    }
}

int main() {
    // Ma trận kề đồ thị
    int graph[V][V] = {
    //   A  B  C  D  E
        {0, 1, 0, 0, 5}, // A
        {0, 0, 3, 3, 8}, // B
        {0, 0, 0, 1, -5},// C
        {0, 0, 0, 0, 0}, // D
        {0, 0, 0, 4, 0}  // E
    };

    // Đỉnh nguồn
    int source = 0;

    // Gọi hàm Bellman-Ford
    bellmanFord(graph, source);

    return 0;
}