How to use the Bellman-Ford algorithm in C++

How to use the Bellman-Ford algorithm in C

The Bellman-Ford algorithm is a method used to find the shortest path from a single source point to all other vertices in the graph. algorithm. It can handle graphs containing negative weight edges, so it is widely used in network routing, financial market analysis and other fields. This article explains how to use the Bellman-Ford algorithm in C and provides code examples.

The core idea of ​​the Bellman-Ford algorithm is to continuously update the estimated shortest path through relaxation operation (relaxation) until the optimal solution is reached. Its time complexity is O(V * E), where V is the number of vertices in the graph and E is the number of edges.

The following is a sample code using C to implement the Bellman-Ford algorithm:

#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;
}

In the above code, we define an edge (Edge) structure, including the starting point of the edge (source) , destination and weight.

The BellmanFord function receives a list of edges, the number of vertices in the graph, and the source point as parameters. It first initializes the distance array distance, sets the distance of the source point to 0, and sets the distance of other vertices to infinity.

Then perform V-1 rounds of relaxation operations, traversing the edge set each time and trying to update the shortest path. If a shorter path can be obtained by relaxing an edge, the distance to the target vertex is updated. In this way, the shortest path from the source point to other vertices can be found.

Finally, we traverse all edges again and check whether there is a negative weight cycle. If an edge can still update the distance of the target vertex after the relaxation operation, it means that there is a negative weight loop in the graph.

The final output of the code is the shortest path. If the distance to a vertex is still infinite, it means that the source point cannot reach the vertex; otherwise, the shortest path from the source point to the vertex is output.

The above is a code example of using C to implement the Bellman-Ford algorithm. You can modify and extend it according to your needs. This algorithm is very useful when dealing with graphs with negative weight edges. I hope it will be helpful to you.

The above is the detailed content of How to use the Bellman-Ford algorithm in C++. For more information, please follow other related articles on the PHP Chinese website!