bellmanford算法c语言实现
时间: 2024-09-24 15:06:47 浏览: 0
Bellman-Ford算法是一种用于求解单源最短路径问题的动态规划方法,尤其适用于存在负权边的情况。以下是C语言的一个简单实现:
```c
#include <stdio.h>
#include <limits.h>
#define V 9 // 图的顶点数
// 定义邻接矩阵表示图
int graph[V][V];
void bellman_ford(int src, int dist[]) {
int i, j, edge;
// 初始化所有顶点到源的距离为无穷大,除了源节点本身为0
for (i = 0; i < V; i++) {
if (i == src)
dist[i] = 0;
else
dist[i] = INT_MAX;
}
// 进行V-1次松弛操作
for (i = 0; i < V - 1; i++) {
for (j = 0; j < V; j++) {
// 检查是否存在u-v边,并更新距离
for (edge = 0; edge < V; edge++)
if (graph[j][edge] && dist[j] != INT_MAX &&
dist[j] + graph[j][edge] < dist[edge])
dist[edge] = dist[j] + graph[j][edge];
}
}
// 检查是否有负环,如果存在则会发现不止一次的缩短
for (i = 0; i < V; i++) {
for (j = 0; j < V; j++) {
if (graph[j][i] && dist[j] != INT_MAX &&
dist[j] + graph[j][i] < dist[i]) {
printf("Graph contains negative weight cycle.\n");
return;
}
}
}
}
int main() {
int src, v, u, w;
printf("Enter the number of vertices and edges\n");
scanf("%d", &V);
// 输入邻接矩阵
printf("Enter the weighted adjacency matrix:\n");
for (v = 0; v < V; v++) {
for (u = 0; u < V; u++) {
scanf("%d", &w);
graph[v][u] = w; // 如果w非零,则存在从v到u的有向边
}
}
printf("Source vertex: ");
scanf("%d", &src);
int dist[V]; // 存储每个顶点到源的最短距离
bellman_ford(src, dist);
printf("Shortest path from %d to all other vertices:\n", src);
for (v = 0; v < V; v++) {
if (dist[v] != INT_MAX)
printf("Distance to vertex %d is %d\n", v, dist[v]);
else
printf("Vertex %d is unreachable\n", v);
}
return 0;
}
```