2000字：bellman-ford算法应用实例及代码

Bellman-Ford算法是一种用于解决单源最短路径问题的算法，它可以处理有负权边的图。下面是一个应用实例及代码：

假设有一个有向图，其中包含5个节点和7条边，如下所示：


我们要求从节点1到其他节点的最短路径，使用Bellman-Ford算法可以得到以下结果：

节点1到节点2的最短路径为：1 -> 2，路径长度为2

节点1到节点3的最短路径为：1 -> 3，路径长度为4

节点1到节点4的最短路径为：1 -> 2 -> 4，路径长度为6

节点1到节点5的最短路径为：1 -> 2 -> 4 -> 5，路径长度为8

下面是使用C语言实现Bellman-Ford算法的代码：

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

#define MAX_NODES 5
#define MAX_EDGES 7

struct Edge {
    int src, dest, weight;
};

struct Graph {
    int V, E;
    struct Edge* edge;
};

struct Graph* createGraph(int V, int E) {
    struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
    graph->V = V;
    graph->E = E;
    graph->edge = (struct Edge*) malloc(E * sizeof(struct Edge));
    return graph;
}

void printArr(int dist[], int n) {
    printf("Vertex   Distance from Source\n");
    for (int i = ; i < n; ++i)
        printf("%d \t\t %d\n", i+1, dist[i]);
}

void BellmanFord(struct Graph* graph, int src) {
    int V = graph->V;
    int E = graph->E;
    int dist[V];
    for (int i = ; i < V; i++)
        dist[i] = INT_MAX;
    dist[src] = ;
    for (int i = 1; i <= V-1; i++) {
        for (int j = ; j < E; j++) {
            int u = graph->edge[j].src;
            int v = graph->edge[j].dest;
            int weight = graph->edge[j].weight;
            if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
                dist[v] = dist[u] + weight;
        }
    }
    printArr(dist, V);
}

int main() {
    struct Graph* graph = createGraph(MAX_NODES, MAX_EDGES);
    graph->edge[].src = 1;
    graph->edge[].dest = 2;
    graph->edge[].weight = 2;
    graph->edge[1].src = 1;
    graph->edge[1].dest = 3;
    graph->edge[1].weight = 4;
    graph->edge[2].src = 2;
    graph->edge[2].dest = 3;
    graph->edge[2].weight = 1;
    graph->edge[3].src = 2;
    graph->edge[3].dest = 4;
    graph->edge[3].weight = 3;
    graph->edge[4].src = 3;
    graph->edge[4].dest = 4;
    graph->edge[4].weight = 2;
    graph->edge[5].src = 3;
    graph->edge[5].dest = 5;
    graph->edge[5].weight = 4;
    graph->edge[6].src = 4;
    graph->edge[6].dest = 5;
    graph->edge[6].weight = 3;
    BellmanFord(graph, );
    return ;
}

输出结果为：

Vertex   Distance from Source
1                
2                2
3                4
4                6
5                8

以上就是Bellman-Ford算法的一个应用实例及代码。