[C言語] ベルマンフォード法を実装する方法

typedef struct {
    int src;    // 始点
    int dest;   // 終点
    int weight; // 重み
} Edge;

Edge edges[] = {
    {0, 1, -1},
    {0, 2, 4},
    {1, 2, 3},
    {1, 3, 2},
    {1, 4, 2},
    {3, 1, 1},
    {3, 4, -3},
    {4, 0, 2},
    {4, 3, 3}
};

void initialize(int distance[], int vertexCount, int startVertex) {
    for (int i = 0; i < vertexCount; i++) {
        distance[i] = (i == startVertex) ? 0 : INT_MAX; // 始点の距離は0、他は∞
    }
}

void relaxEdges(Edge edges[], int distance[], int edgeCount) {
    for (int i = 0; i < edgeCount; i++) {
        int u = edges[i].src;
        int v = edges[i].dest;
        int weight = edges[i].weight;
        if (distance[u] != INT_MAX && distance[v] > distance[u] + weight) {
            distance[v] = distance[u] + weight; // 距離を更新
        }
    }
}

int detectNegativeCycle(Edge edges[], int distance[], int edgeCount) {
    for (int i = 0; i < edgeCount; i++) {
        int u = edges[i].src;
        int v = edges[i].dest;
        int weight = edges[i].weight;
        if (distance[u] != INT_MAX && distance[v] > distance[u] + weight) {
            return 1; // 負の閉路が存在
        }
    }
    return 0; // 負の閉路は存在しない
}

void printResult(int distance[], int vertexCount) {
    printf("頂点への最短距離:\n");
    for (int i = 0; i < vertexCount; i++) {
        if (distance[i] == INT_MAX) {
            printf("頂点 %d: 到達不可\n", i);
        } else {
            printf("頂点 %d: %d\n", i, distance[i]);
        }
    }
}

#include <stdio.h>
#include <limits.h>
typedef struct {
    int src;    // 始点
    int dest;   // 終点
    int weight; // 重み
} Edge;
void initialize(int distance[], int vertexCount, int startVertex) {
    for (int i = 0; i < vertexCount; i++) {
        distance[i] = (i == startVertex) ? 0 : INT_MAX; // 始点の距離は0、他は∞
    }
}
void relaxEdges(Edge edges[], int distance[], int edgeCount) {
    for (int i = 0; i < edgeCount; i++) {
        int u = edges[i].src;
        int v = edges[i].dest;
        int weight = edges[i].weight;
        if (distance[u] != INT_MAX && distance[v] > distance[u] + weight) {
            distance[v] = distance[u] + weight; // 距離を更新
        }
    }
}
int detectNegativeCycle(Edge edges[], int distance[], int edgeCount) {
    for (int i = 0; i < edgeCount; i++) {
        int u = edges[i].src;
        int v = edges[i].dest;
        int weight = edges[i].weight;
        if (distance[u] != INT_MAX && distance[v] > distance[u] + weight) {
            return 1; // 負の閉路が存在
        }
    }
    return 0; // 負の閉路は存在しない
}
void printResult(int distance[], int vertexCount) {
    printf("頂点への最短距離:\n");
    for (int i = 0; i < vertexCount; i++) {
        if (distance[i] == INT_MAX) {
            printf("頂点 %d: 到達不可\n", i);
        } else {
            printf("頂点 %d: %d\n", i, distance[i]);
        }
    }
}
int main() {
    int vertexCount = 5; // 頂点数
    int edgeCount = 9;   // 辺数
    Edge edges[] = {
        {0, 1, -1},
        {0, 2, 4},
        {1, 2, 3},
        {1, 3, 2},
        {1, 4, 2},
        {3, 1, 1},
        {3, 4, -3},
        {4, 0, 2},
        {4, 3, 3}
    };
    int distance[vertexCount];
    initialize(distance, vertexCount, 0); // 始点を0に設定
    for (int i = 0; i < vertexCount - 1; i++) {
        relaxEdges(edges, distance, edgeCount); // 緩和操作
    }
    if (detectNegativeCycle(edges, distance, edgeCount)) {
        printf("負の閉路が存在します。\n");
    } else {
        printResult(distance, vertexCount); // 結果を出力
    }
    return 0;
}