SPFA算法的C语言实现

下面是SPFA算法的C语言实现:

#include <stdio.h>
#include <string.h>
#define MAXN 1000
#define INF 0x3f3f3f3f

int n, m; // n表示点数，m表示边数
int head[MAXN], dist[MAXN], cnt[MAXN]; // head[]表示链式前向星的头指针，dist[]表示源点到各点的最短距离，cnt[]表示各点入队的次数
int vis[MAXN]; // 标记数组，表示某个点是否在队列中
struct Edge {
    int v, w, nxt; // v表示该边指向的点，w表示该边的权值，nxt表示该边的下一条边
} edge[MAXN];

void addEdge(int u, int v, int w, int& idx) {
    edge[idx].v = v;
    edge[idx].w = w;
    edge[idx].nxt = head[u];
    head[u] = idx++;
}

int SPFA(int s, int t) {
    memset(vis, 0, sizeof(vis));
    memset(cnt, 0, sizeof(cnt));
    memset(dist, INF, sizeof(dist));
    dist[s] = 0;
    vis[s] = 1;
    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] = 0;
        for (int i = head[u]; i != -1; i = edge[i].nxt) {
            int v = edge[i].v, w = edge[i].w;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (!vis[v]) {
                    vis[v] = 1;
                    queue[rear++] = v;
                    if (rear == MAXN) rear = 0;
                    if (++cnt[v] > n) return -1; // 存在负环
                }
            }
        }
    }
    return dist[t] == INF ? -2 : dist[t]; // 不存在路径或源点和目标点不连通
}

int main() {
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    int idx = 0;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        addEdge(u, v, w, idx);
        addEdge(v, u, w, idx); // 如果是无向图，还需要添加反向边
    }
    int s, t;
    scanf("%d%d", &s, &t);
    int ans = SPFA(s, t);
    if (ans == -1) printf("存在负环\n");
    else if (ans == -2) printf("源点和目标点不连通\n");
    else printf("%d\n", ans);
    return 0;
}

注意：该代码实现的是 SPFA 算法的基础版，可能存在负环的情况。在实际使用过程中，应该对其进行优化，避免出现负环。