如何使用C++中的Bellman-Ford演算法

如何使用C 中的Bellman-Ford演算法

Bellman-Ford演算法是一種用於從單一來源點到圖中其他所有頂點求最短路徑的演算法.它可以處理包含負權邊的圖，因此廣泛應用於網路路由、金融市場分析等領域。本文將介紹如何使用C 中的Bellman-Ford演算法，並提供程式碼範例。

Bellman-Ford演算法核心概念是透過鬆弛操作（relaxation）不斷更新估計的最短路徑，直到達到最優解。它的時間複雜度為O(V * E)，其中V是圖中頂點的數量，E是邊的數量。

以下是使用C 實作Bellman-Ford演算法的範例程式碼：

#include <iostream>
#include <vector>

struct Edge {
    int source;
    int destination;
    int weight;
};

void BellmanFord(std::vector<Edge>& edges, int numVertices, int source) {
    std::vector<int> distance(numVertices, INT_MAX);
    distance[source] = 0;

    // Relaxation
    for (int i = 1; i < numVertices; i++) {
        for (const auto& edge : edges) {
            int u = edge.source;
            int v = edge.destination;
            int w = edge.weight;
            if (distance[u] != INT_MAX && distance[v] > distance[u] + w) {
                distance[v] = distance[u] + w;
            }
        }
    }

    // Check for negative cycle
    for (const auto& edge : edges) {
        int u = edge.source;
        int v = edge.destination;
        int w = edge.weight;
        if (distance[u] != INT_MAX && distance[v] > distance[u] + w) {
            std::cout << "图中存在负权回路
";
            return;
        }
    }

    // 输出最短路径
    for (int i = 0; i < numVertices; i++) {
        if (distance[i] == INT_MAX) {
            std::cout << "源点无法到达顶点 " << i << "
";
        } else {
            std::cout << "源点到顶点 " << i << " 的最短路径为: " << distance[i] << "
";
        }
    }
}

int main() {
    std::vector<Edge> graph = { 
        {0, 1, -1},
        {0, 2, 4},
        {1, 2, 3},
        {1, 3, 2},
        {1, 4, 2},
        {3, 2, 5},
        {3, 1, 1},
        {4, 3, -3}
    };
    int numVertices = 5;
    int source = 0;

    BellmanFord(graph, numVertices, source);

    return 0;
}

在上述程式碼中，我們定義了一個邊（Edge）結構體，包含邊的起始點（source） 、終止點（destination）和權重（weight）。

BellmanFord函數接收邊的列表、圖中頂點的數量和來源點作為參數。它先初始化距離數組distance，將源點的距離設為0，其他頂點的距離設為無限大。

接著進行V-1輪鬆弛操作，每次遍歷邊集合並嘗試更新最短路徑。如果通過某邊鬆弛操作可獲得較短的路徑，則更新目標頂點的距離。這樣就可以找到源點到其他頂點的最短路徑。

最後，我們再次遍歷所有邊，檢查是否有負權迴路。如果某邊在鬆弛操作後仍能更新目標頂點的距離，表示圖中存在負權迴路。

程式碼的最後輸出最短路徑。如果某個頂點的距離仍然是無窮大，表示源點無法到達該頂點；否則，輸出源點到該頂點的最短路徑。

以上就是使用C 實作Bellman-Ford演算法的程式碼範例。你可以根據自己的需求進行修改和擴展。這個演算法在處理有負權邊的圖表時非常有用，希望對你有幫助。

以上是如何使用C++中的Bellman-Ford演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！