SPFA算法C语言代码实现
时间: 2023-10-27 17:16:08 浏览: 120
以下是SPFA算法的C语言实现:
```c
#include <stdio.h>
#include <string.h>
#define MAXN 1000 //节点数的最大值
#define MAXM 1000000 //边数的最大值
#define INF 0x3f3f3f3f //正无穷
struct Edge {
int to, next, w;
};
Edge e[MAXM];
int head[MAXN], num_edge;
int dis[MAXN], vis[MAXN], cnt[MAXN];
void add_edge(int u, int v, int w) {
e[++num_edge].to = v;
e[num_edge].w = w;
e[num_edge].next = head[u];
head[u] = num_edge;
}
int spfa(int s, int t) {
memset(dis, INF, sizeof(dis));
memset(vis, 0, sizeof(vis));
memset(cnt, 0, sizeof(cnt));
dis[s] = 0;
vis[s] = 1;
cnt[s] = 1;
int queue[MAXN * 10], front = 0, rear = 1;
queue[front] = s;
while (front < rear) {
int u = queue[front++];
vis[u] = 0;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to, w = e[i].w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
if (!vis[v]) {
vis[v] = 1;
queue[rear++] = v;
cnt[v]++;
if (cnt[v] > MAXN) {
return -1; //图中存在负环
}
}
}
}
}
return dis[t];
}
int main() {
int n, m;
printf("请输入图的节点个数和边的个数:\n");
scanf("%d%d", &n, &m);
printf("请输入每条边的起点、终点和边权:\n");
for (int i = 1; i <= m; ++i) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
add_edge(u, v, w);
}
int s, t;
printf("请输入源点和汇点:\n");
scanf("%d%d", &s, &t);
int ans = spfa(s, t);
if (ans == -1) {
printf("图中存在负环!\n");
} else {
printf("源点到汇点的最短路径长度为:%d\n", ans);
}
return 0;
}
```
请注意,这只是SPFA算法的一个基础实现,可能会存在一些效率问题和漏洞,在实际应用中需要进行优化和改进。
阅读全文