Thuật toán Floyd

Phạm vi sử dụng:

Ban đầu, thuật toán được sử dụng để tìm đường đi ngắn nhất giữa hai điểm trong một đồ thị có hướng. Tuy nhiên, sau này, thuật toán đã được mở rộng để tính toán đường đi ngắn nhất giữa tất cả các cặp đỉnh trong một đồ thị có hướng, cũng như trong đồ thị vô hướng.

Chi Tiết Kỹ Thuật Thuật Toán Floyd:

• Khởi tạo Ma trận Khoảng cách: Bước đầu tiên là khởi tạo một ma trận 2 chiều dist có kích thước VxV, trong đó V là số lượng đỉnh trong đồ thị. Ban đầu, các ô của ma trận này được gán giá trị vô cùng lớn (đại diện cho vô cùng) hoặc một giá trị khác biệt đủ lớn để biểu diễn khoảng cách không có đường đi. Sau đó, các đường chéo chính của ma trận sẽ được gán giá trị 0, vì khoảng cách từ một đỉnh tới chính nó là 0.

• Cập Nhật Khoảng Cách Trực Tiếp: Tiếp theo, thuật toán sẽ duyệt qua tất cả các cặp đỉnh và cập nhật ma trận dist dựa trên các đường đi trực tiếp từ một đỉnh tới đỉnh kế tiếp. Nếu có đường đi trực tiếp từ đỉnh u tới v với chi phí nhỏ hơn giá trị hiện tại của dist[u][v], thì giá trị của dist[u][v] sẽ được cập nhật.

• Cập Nhật Khoảng Cách Thông Qua Đỉnh Trung Gian: Sau khi cập nhật khoảng cách trực tiếp, thuật toán sẽ tiếp tục duyệt qua tất cả các cặp đỉnh và cập nhật dist thông qua đỉnh trung gian k. Mục tiêu là tìm đường đi ngắn nhất từ một đỉnh tới một đỉnh khác thông qua một đỉnh trung gian k. Nếu tổng khoảng cách từ đỉnh u tới k và từ k tới v nhỏ hơn giá trị hiện tại của dist[u][v], thì dist[u][v] sẽ được cập nhật.

• Kiểm tra Chu Trình Âm: Cuối cùng, sau khi hoàn thành việc cập nhật ma trận khoảng cách, thuật toán kiểm tra xem có chu trình âm nào không bằng cách duyệt qua các đường chéo chính của ma trận dist. Nếu bất kỳ giá trị dist[i][i] nào nhỏ hơn 0, đồ thị chứa chu trình âm.

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

function FloydWarshall(graph[][], V):
    // Khởi tạo ma trận khoảng cách
    dist[][] = new int[V][V]
    for i = 0 to V-1:
        for j = 0 to V-1:
            if i == j:
                dist[i][j] = 0  // Khoảng cách từ một đỉnh tới chính nó là 0
            else if graph[i][j] != 0:
                dist[i][j] = graph[i][j]  // Khởi tạo khoảng cách từ đỉnh i tới j bằng trọng số của cạnh (i, j)
            else:
                dist[i][j] = INF  // Khởi tạo khoảng cách từ đỉnh i tới j bằng vô cùng (không có cạnh nối trực tiếp)

    // Cập nhật khoảng cách trực tiếp và thông qua đỉnh trung gian
    for k = 0 to V-1:
        for i = 0 to V-1:
            for j = 0 to V-1:
                // Cập nhật khoảng cách từ i tới j thông qua đỉnh trung gian k
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    // Kiểm tra chu trình âm
    for i = 0 to V-1:
        if dist[i][i] < 0:
            return "Do thi co chu trinh am"

    // Trả về ma trận khoảng cách
    return dist
 

code C++:

#include <bits/stdc++.h>

using namespace std;

#define V 5
#define INF INT_MAX

// Khởi tạo ma trận trọng số ban đầu
void initializeDistanceMatrix(int dist[V][V], const int graph[V][V]) {
    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
            if (i == j) {
                dist[i][j] = 0;
            } else if (graph[i][j] != 0) {
                dist[i][j] = graph[i][j];
            } else {
                dist[i][j] = INF;
            }
        }
    }
}

// Cập nhật ma trận trọng số
void updateDistanceMatrix(int dist[V][V], int k) {
    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
            if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {
                dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }
}

// Kiểm tra có chu trình âm hay không
bool hasNegativeCycle(const int dist[V][V]) {
    for (int i = 0; i < V; ++i) {
        if (dist[i][i] < 0) {
            return true;
        }
    }
    return false;
}

// In ma trận trọng số
void printDistanceMatrix(const int dist[V][V]) {
    cout << "Ma tran khoang cach ngan nhat giua cac cap dinh:\n";
    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
            if (dist[i][j] == INF) {
                cout << "INF\t";
            } else {
                cout << dist[i][j] << "\t";
            }
        }
        cout << endl;
    }
}

// Thuật toán Floyd-Warshall
void floydWarshall(int graph[V][V]) {
    int dist[V][V];
    initializeDistanceMatrix(dist, graph);

    for (int k = 0; k < V; ++k) {
        updateDistanceMatrix(dist, k);
    }

    printDistanceMatrix(dist);

    if (hasNegativeCycle(dist)) {
        cout << "Do thi co chu trinh trong so am." << endl;
    }
}

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

    floydWarshall(graph);

    return 0;
}