用c写一个邻接链表的spfa算法
时间: 2023-05-11 13:01:45 浏览: 76
好的,以下是用 C 语言实现邻接链表的 SPFA 算法的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAXN 100005
#define INF 0x3f3f3f3f
typedef struct Edge {
int to, w, nxt;
} Edge;
Edge edge[MAXN << 1];
int head[MAXN], dis[MAXN], cnt[MAXN];
bool vis[MAXN];
int n, m, s, t, tot;
void addEdge(int u, int v, int w) {
edge[++tot].to = v;
edge[tot].w = w;
edge[tot].nxt = head[u];
head[u] = tot;
}
bool spfa(int s, int t) {
for (int i = 1; i <= n; i++) {
dis[i] = INF;
vis[i] = false;
cnt[i] = 0;
}
dis[s] = 0;
vis[s] = true;
cnt[s] = 1;
int queue[MAXN], front = 0, rear = 0;
queue[rear++] = s;
while (front != rear) {
int u = queue[front++];
if (front == MAXN) front = 0;
vis[u] = false;
for (int i = head[u]; i; i = edge[i].nxt) {
int v = edge[i].to, w = edge[i].w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
if (!vis[v]) {
vis[v] = true;
queue[rear++] = v;
if (rear == MAXN) rear = 0;
if (++cnt[v] > n) return false;
}
}
}
}
return true;
}
int main() {
scanf("%d%d%d%d", &n, &m, &s, &t);
for (int i = 1; i <= m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
addEdge(u, v, w);
addEdge(v, u, w);
}
if (spfa(s, t)) printf("%d\n", dis[t]);
else printf("No solution!\n");
return 0;
}
```
希望这个代码能够帮到你!