SPFA算法C语言代码实现

下面是SPFA算法的C语言代码实现：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 1001
#define INF 0x7fffffff

typedef struct edge{
    int to, w, next;
}Edge;

int head[MAXN], vis[MAXN], dis[MAXN];
Edge edge[MAXN * MAXN];
int n, m, cnt, s;

void add_edge(int u, int v, int w){
    edge[++cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt;
}

void spfa(){
    int queue[MAXN * MAXN], front = 1, rear = 0;
    for(int i = 1; i <= n; i++){
        vis[i] = 0;
        dis[i] = INF;
    }
    queue[++rear] = s;
    vis[s] = 1;
    dis[s] = 0;
    while(front <= rear){
        int u = queue[front++];
        vis[u] = 0;
        for(int i = head[u]; i; i = edge[i].next){
            int v = edge[i].to;
            if(dis[v] > dis[u] + edge[i].w){
                dis[v] = dis[u] + edge[i].w;
                if(!vis[v]){
                    queue[++rear] = v;
                    vis[v] = 1;
                }
            }
        }
    }
}

int main(){
    scanf("%d%d%d", &n, &m, &s);
    for(int i = 1; i <= m; i++){
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add_edge(u, v, w);
        add_edge(v, u, w);
    }
    spfa();
    for(int i = 1; i <= n; i++){
        printf("%d ", dis[i]);
    }
    printf("\n");
    return 0;
}

其中，`add_edge`函数用于添加一条从u到v，边权为w的边；`spfa`函数实现SPFA算法，`queue`数组用于存储待访问的节点，`front`和`rear`分别表示队列的头和尾。