有权值图的广度优先搜索c语言实现

以下是基于邻接表的带权值图的广度优先搜索的C语言实现。其中，变量n表示图中顶点的个数，变量m表示图中边的个数，变量s表示起点，变量t表示终点。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 1000   // 最大顶点数
#define INF 0x3f3f3f3f  // 无穷大

typedef struct EdgeNode {  // 边结点
    int to;      // 边的终点
    int weight;  // 边的权值
    struct EdgeNode* next;  // 指向下一条边的指针
} EdgeNode;

typedef struct Graph {  // 邻接表表示的带权值图
    EdgeNode* head[MAXN];  // 指向每个顶点的边链表的指针数组
    int dist[MAXN];  // 起点到每个顶点的最短距离
    int visited[MAXN];  // 标记每个顶点是否被访问过
} Graph;

void addEdge(Graph* graph, int from, int to, int weight) {  // 添加一条边
    EdgeNode* edge = (EdgeNode*)malloc(sizeof(EdgeNode));
    edge->to = to;
    edge->weight = weight;
    edge->next = graph->head[from];
    graph->head[from] = edge;
}

void bfs(Graph* graph, int s) {  // 广度优先搜索
    memset(graph->visited, 0, sizeof(graph->visited));  // 初始化visited数组
    memset(graph->dist, INF, sizeof(graph->dist));  // 初始化dist数组
    graph->dist[s] = 0;  // 起点到自身的距离为0
    graph->visited[s] = 1;  // 标记起点已被访问
    int queue[MAXN];  // 队列
    int front = 0, rear = 0;  // 队头和队尾指针
    queue[rear++] = s;  // 将起点入队
    while (front < rear) {  // 队列不为空
        int u = queue[front++];  // 取出队头
        EdgeNode* p = graph->head[u];  // 遍历与u相邻的所有顶点
        while (p) {
            int v = p->to;
            if (!graph->visited[v]) {  // 如果v未被访问过
                graph->visited[v] = 1;  // 标记v已被访问
                graph->dist[v] = graph->dist[u] + p->weight;  // 更新起点到v的最短距离
                queue[rear++] = v;  // 将v入队
            }
            p = p->next;
        }
    }
}

int main() {
    Graph graph;
    int n, m, s, t;
    scanf("%d%d%d%d", &n, &m, &s, &t);
    memset(graph.head, 0, sizeof(graph.head));  // 初始化邻接表
    for (int i = 0; i < m; i++) {
        int from, to, weight;
        scanf("%d%d%d", &from, &to, &weight);
        addEdge(&graph, from, to, weight);  // 添加一条边
    }
    bfs(&graph, s);  // 从起点开始广度优先搜索
    printf("%d\n", graph.dist[t]);  // 输出起点到终点的最短距离
    return 0;
}

该程序的时间复杂度为O(m+n)，其中m为边数，n为顶点数。