使用迪杰斯特拉算法求出无向加权图中任意两点的最短路径并输出其路径c语言代码

迪杰斯特拉算法是一种求解单源最短路径的常用算法，适用于边权非负的有向图或无向图。下面是使用 C 语言实现的迪杰斯特拉算法，求解无向加权图中任意两点的最短路径，并输出其路径：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 100 // 最大顶点数
#define INF 0x3f3f3f3f // 无穷大

int edge[MAXN][MAXN]; // 邻接矩阵
int dis[MAXN]; // 存储源点到各个顶点的最短路径长度
int vis[MAXN]; // 标记顶点是否已经被访问

// 从源点s到终点t的路径
int path[MAXN], cnt;

// 迪杰斯特拉算法
void dijkstra(int s, int t, int n) {
    memset(dis, INF, sizeof(dis)); // 初始化为无穷大
    memset(vis, 0, sizeof(vis)); // 初始化为未访问
    dis[s] = 0; // 源点到自己的距离为0
    // 依次遍历所有顶点
    for (int i = 1; i <= n; i++) {
        int k = 0;
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && (k == 0 || dis[j] < dis[k])) {
                k = j; // 找到距离源点最近的未访问顶点
            }
        }
        if (k == 0) break; // 如果没有找到，则退出循环
        vis[k] = 1; // 标记为已访问
        // 更新距离
        for (int j = 1; j <= n; j++) {
            if (edge[k][j] != INF && dis[k] + edge[k][j] < dis[j]) {
                dis[j] = dis[k] + edge[k][j];
                path[j] = k; // 记录路径
            }
        }
    }
    // 输出路径
    cnt = 0;
    int u = t;
    while (u != s) {
        path[cnt++] = u;
        u = path[u];
    }
    path[cnt++] = s;
    // 反转路径
    for (int i = cnt - 1; i >= 0; i--) {
        printf("%d ", path[i]);
        if (i > 0) printf("-> ");
    }
    printf("\n");
}

int main() {
    int n, m; // n为顶点数，m为边数
    scanf("%d%d", &n, &m);
    memset(edge, INF, sizeof(edge)); // 初始化为无穷大
    for (int i = 1; i <= m; i++) {
        int u, v, w; // u和v为一条边的两个端点，w为边权
        scanf("%d%d%d", &u, &v, &w);
        edge[u][v] = edge[v][u] = w; // 记录边权
    }
    int s, t; // 源点s和终点t
    scanf("%d%d", &s, &t);
    dijkstra(s, t, n); // 求解最短路径
    printf("最短路径长度为：%d\n", dis[t]);
    return 0;
}

在输入时，我们先读入顶点数n、边数m和每条边的信息（起点、终点和边权）。然后，我们读入源点s和终点t，调用dijkstra函数求解最短路径。在dijkstra函数中，我们先将所有顶点的最短路径长度初始化为无穷大，源点到自己的距离为0。然后，我们依次遍历所有顶点，找到距离源点最近的未访问顶点，标记为已访问，并更新距离。最后，我们输出从源点到终点的最短路径和其长度。

注意，在dijkstra函数中，我们使用path数组记录路径，cnt记录路径长度。在输出路径时，我们先从终点t开始，倒序输出路径，并在每个顶点后输出"->"。最后，我们输出最短路径长度。

另外，我们使用INF表示无穷大，可以用一个足够大的整数代替。