Bellman-Fordアルゴリズム:最短経路問題の解決方法

#include <iostream>
#include <vector>
#include <limits>
struct Edge {
    int source, destination, weight;
};
void BellmanFord(std::vector<Edge>& edges, int numVertices, int source) {
    std::vector<int> distance(numVertices, std::numeric_limits<int>::max());
    distance[source] = 0;
    for (int i = 1; i < numVertices; ++i) {
        for (const auto& edge : edges) {
            if (distance[edge.source] != std::numeric_limits<int>::max() &&
                distance[edge.source] + edge.weight < distance[edge.destination]) {
                distance[edge.destination] = distance[edge.source] + edge.weight;
            }
        }
    }
// Negative cycle detection
    for (const auto& edge : edges) {
        if (distance[edge.source] != std::numeric_limits<int>::max() &&
            distance[edge.source] + edge.weight < distance[edge.destination]) {
            std::cout << "Negative cycle detected!" << std::endl;
            return;
        }
    }
// Print the shortest distances from the source
    for (int i = 0; i < numVertices; ++i) {
        std::cout << "Distance from " << source << " to " << i << " is " << distance[i] << std::endl;
    }
}
int main() {
    int numVertices = 5;
    std::vector<Edge> edges = {
        {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 source = 0;
    BellmanFord(edges, numVertices, source);
    return 0;
}

上記のコードは、ベルマンフォードアルゴリズムを使用してグラフ内の最短経路を見つける方法を示しています。コードは、与えられたグラフの辺のリストと頂点の数を受け取り、最短経路を計算し、結果を出力します。また、負のサイクルの検出も行います。

このコードを実行すると、指定したソース頂点から各頂点までの最短距離が表示されます。もし、負のサイクルが存在する場合は、「Negative cycle detected!」と表示されます。

以上が、C++でのベルマンフォードアルゴリズムの実装例です。このアルゴリズムを使用することで、グラフ内の最短経路を見つけることができます。