无向图迪杰斯特拉算法C

无向图迪杰斯特拉算法（Dijkstra算法）是一种用于计算单源最短路径的贪心算法。它的基本思想是从起点开始，逐步扩大已经找到的最短路径集合，直到覆盖所有节点为止。下面是无向图迪杰斯特拉算法的C语言实现：

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

#define MAX_VERTICES 1000

typedef struct {
    int v;
    int weight;
} edge;

int n; // 节点数
int m; // 边数
int s; // 起点
int t; // 终点
int visited[MAX_VERTICES]; // 标记节点是否已经访问
int dis[MAX_VERTICES]; // 存储起点到各个节点的最短距离
edge net[MAX_VERTICES][MAX_VERTICES]; // 存储图的邻接矩阵

void dijkstra(int s) {
    int i, j, k, min;
    for (i = 0; i < n; i++) {
        visited[i] = 0;
        dis[i] = net[s][i].weight;
    }
    visited[s] = 1;
    dis[s] = 0;
    for (i = 1; i < n; i++) {
        min = INT_MAX;
        for (j = 0; j < n; j++) {
            if (!visited[j] && dis[j] < min) {
                min = dis[j];
                k = j;
            }
        }
        visited[k] = 1;
        for (j = 0; j < n; j++) {
            if (!visited[j] && dis[k] + net[k][j].weight < dis[j]) {
                dis[j] = dis[k] + net[k][j].weight;
            }
        }
    }
}

int main() {
    int i, j, u, v, w;
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            net[i][j].weight = INT_MAX;
        }
    }
    for (i = 0; i < m; i++) {
        scanf("%d%d%d", &u, &v, &w);
        net[u][v].weight = w;
        net[v][u].weight = w;
    }
    dijkstra(s);
    printf("%d\n", dis[t]);
    return 0;
}