用C语言Write down a program for bellman-ford algorithm and also add your output/result screenshots of your program.
时间: 2024-12-06 12:24:46 浏览: 18
当然,贝尔曼-福特算法(Bellman-Ford Algorithm)是用于求解带有权重的有向图中从源节点到所有其他节点的最短路径的算法。这里是一个简单的C程序示例,演示了如何实现该算法:
```c
#include <stdio.h>
#include <stdbool.h>
#define V 9 // 图中的顶点数
// 定义邻接矩阵表示图
int graph[V][V] = {
{0, -1, 4, 0, 0, 0, 0, 8, 0},
{-1, 0, 10, 0, 0, 0, 0, 5, -1},
{4, 10, 0, 8, 0, 0, 2, 0, 7},
{0, 0, 8, 0, 2, 5, 4, 11, 0},
{0, 0, 0, 2, 0, 14, 0, 0, 2},
{0, 0, 0, 5, 14, 0, 9, 0, 6},
{0, 0, 2, 4, 0, 9, 0, 7, 2},
{8, 5, 0, 11, 0, 0, 7, 0, 9},
{0, -1, 7, 0, 2, 6, 2, 9, 0}
};
// 函数定义
void bellmanFord(int src, int V) {
int dist[V]; // 存储每个顶点到源的距离
bool negativeCycle; // 标记是否存在负权环
dist[src] = 0;
// 进行V-1次迭代,每次增加一条边的最大长度
for (int i = 0; i < V - 1; i++) {
for (int u = 0; u < V; u++) {
for (int v = 0; v < V; v++) {
if (graph[u][v] != -1 && dist[u] != INF && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
}
// 再进行一次检查以发现负权环
negativeCycle = false;
for (int u = 0; u < V; u++) {
for (int v = 0; v < V; v++) {
if (graph[u][v] != -1 && dist[u] != INF && dist[u] + graph[u][v] < dist[v]) {
printf("Graph contains negative weight cycle.\n");
negativeCycle = true;
break;
}
}
if (negativeCycle)
break;
}
// 输出结果
for (int i = 0; i < V; i++) {
printf("Vertex %d is at distance %d from source\n", i + 1, dist[i]);
}
}
int main() {
int src = 0; // 假设源节点为0
bellmanFord(src, V);
return 0;
}
```
当你运行这个程序时,它会输出每个顶点到源节点的最短距离。如果存在负权循环,则会在输出中检测到。
由于这里无法提供实际的截图,你可以自己在本地编译并运行这个C程序,查看结果。如果你需要帮助理解和执行代码,请随时提问。
阅读全文