bellman-ford算法代码c

下面是Bellman-Ford算法的C代码示例：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// 定义图的最大顶点数和最大边数
#define MAX_VERTICES 100
#define MAX_EDGES 100

// 定义图的顶点和边的结构体
typedef struct {
    int source, destination, weight;
} Edge;

typedef struct {
    int vertexCount, edgeCount;
    int distance[MAX_VERTICES];
    int predecessor[MAX_VERTICES];
    Edge edges[MAX_EDGES];
} Graph;

// 初始化图
void initializeGraph(Graph *graph, int vertexCount) {
    graph->vertexCount = vertexCount;
    graph->edgeCount = 0;
    for (int i = 0; i < vertexCount; i++) {
        graph->distance[i] = INT_MAX; // 将所有顶点的距离初始化为无穷大
        graph->predecessor[i] = -1; // 将所有顶点的前驱顶点初始化为-1
    }
}

// 添加边到图
void addEdge(Graph *graph, int source, int destination, int weight) {
    graph->edges[graph->edgeCount].source = source;
    graph->edges[graph->edgeCount].destination = destination;
    graph->edges[graph->edgeCount].weight = weight;
    graph->edgeCount++;
}

// 执行Bellman-Ford算法
bool bellmanFord(Graph *graph, int source) {
    graph->distance[source] = 0; // 将源顶点的距离设置为0

    // 对所有边进行松弛操作
    for (int i = 1; i <= graph->vertexCount - 1; i++) {
        for (int j = 0; j < graph->edgeCount; j++) {
            int u = graph->edges[j].source;
            int v = graph->edges[j].destination;
            int weight = graph->edges[j].weight;

            if (graph->distance[u] != INT_MAX && graph->distance[u] + weight < graph->distance[v]) {
                graph->distance[v] = graph->distance[u] + weight;
                graph->predecessor[v] = u;
            }
        }
    }

    // 检测是否存在负权回路
    for (int i = 0; i < graph->edgeCount; i++) {
        int u = graph->edges[i].source;
        int v = graph->edges[i].destination;
        int weight = graph->edges[i].weight;

        if (graph->distance[u] != INT_MAX && graph->distance[u] + weight < graph->distance[v]) {
            return false; // 存在负权回路
        }
    }

    return true; // 不存在负权回路
}

// 打印最短路径
void printShortestPath(Graph *graph, int source) {
    printf("顶点\t\t距离\t\t最短路径\n");
    for (int i = 0; i < graph->vertexCount; i++) {
        printf("%d\t\t%d\t\t", i, graph->distance[i]);

        // 打印最短路径
        int j = i;
        while (j != source) {
            printf("%d ", j);
            j = graph->predecessor[j];
        }
        printf("%d\n", source);
    }
}

int main() {
    Graph graph;
    int vertexCount, edgeCount, source;

    printf("请输入图的顶点数：");
    scanf("%d", &vertexCount);

    initializeGraph(&graph, vertexCount);

    printf("请输入图的边数：");
    scanf("%d", &edgeCount);

    printf("请输入边的起点、终点和权重：\n");
    for (int i = 0; i < edgeCount; i++) {
        int source, destination, weight;
        scanf("%d %d %d", &source, &destination, &weight);
        addEdge(&graph, source, destination, weight);
    }

    printf("请输入源顶点：");
    scanf("%d", &source);

    if (bellmanFord(&graph, source)) {
        printShortestPath(&graph, source);
    } else {
        printf("存在负权回路\n");
    }

    return 0;
}

这段代码实现了Bellman-Ford算法，包括图的初始化、边的添加、算法的执行以及最短路径的打印。你可以根据需要进行调整和使用。