SPFA算法的c语言实现
时间: 2023-07-24 18:22:13 浏览: 68
SPFA算法是一种基于Bellman-Ford算法的单源最短路径算法,其主要思想是通过队列来遍历节点,不断更新节点的距离值,直到所有节点的距离值都不再发生变化为止。以下是SPFA算法的C语言实现代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_N 1000
#define INF 0x7fffffff
typedef struct edge {
int to;
int w;
struct edge *next;
} Edge;
Edge *G[MAX_N + 1];
int dist[MAX_N + 1];
bool in_queue[MAX_N + 1];
void add_edge(int u, int v, int w) {
Edge *e = (Edge *)malloc(sizeof(Edge));
e->to = v;
e->w = w;
e->next = G[u];
G[u] = e;
}
void spfa(int s, int n) {
for (int i = 1; i <= n; i++) {
dist[i] = INF;
in_queue[i] = false;
}
dist[s] = 0;
in_queue[s] = true;
int q[MAX_N], head = 0, tail = 1;
q[head] = s;
while (head != tail) {
int u = q[head++];
if (head >= MAX_N) {
head = 0;
}
in_queue[u] = false;
for (Edge *e = G[u]; e != NULL; e = e->next) {
int v = e->to;
if (dist[v] > dist[u] + e->w) {
dist[v] = dist[u] + e->w;
if (!in_queue[v]) {
q[tail++] = v;
if (tail >= MAX_N) {
tail = 0;
}
in_queue[v] = true;
}
}
}
}
}
int main() {
int n, m, s;
scanf("%d%d%d", &n, &m, &s);
for (int i = 0; i < m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
add_edge(u, v, w);
}
spfa(s, n);
for (int i = 1; i <= n; i++) {
printf("%d ", dist[i]);
}
printf("\n");
return 0;
}
```
其中,`G`是邻接表,存储图的信息;`dist`是从源点到各个节点的最短距离数组;`in_queue`记录每个节点是否在队列中。`add_edge`函数用于添加边,`spfa`函数实现了SPFA算法的主体部分,`main`函数用于读入图的信息,调用`spfa`函数求解最短路径,并输出结果。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)