使用迪杰斯特拉算法求出任意两点的最短路径c语言代码

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

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

int edge[MAXN][MAXN]; // 邻接矩阵
int dis[MAXN][MAXN]; // 存储任意两点之间的最短路径长度
int vis[MAXN]; // 标记顶点是否已经被访问

// 迪杰斯特拉算法
void dijkstra(int s, int n) {
    memset(dis, INF, sizeof(dis)); // 初始化为无穷大
    memset(vis, 0, sizeof(vis)); // 初始化为未访问
    dis[s][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[s][j] < dis[s][k])) {
                k = j; // 找到距离源点s最近的未访问顶点
            }
        }
        if (k == 0) break; // 如果没有找到，则退出循环
        vis[k] = 1; // 标记为已访问
        // 更新距离
        for (int j = 1; j <= n; j++) {
            if (edge[k][j] != INF && dis[s][k] + edge[k][j] < dis[s][j]) {
                dis[s][j] = dis[s][k] + edge[k][j];
            }
        }
    }
}

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; // 记录边权
    }
    // 求解任意两点之间的最短路径
    for (int i = 1; i <= n; i++) {
        dijkstra(i, n);
    }
    // 输出任意两点之间的最短路径长度
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            printf("%d ", dis[i][j]);
        }
        printf("\n");
    }
    return 0;
}

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

注意，在dijkstra函数中，我们使用dis数组存储任意两点之间的最短路径长度，其中dis[s][t]表示从源点s到终点t的最短路径长度。我们还使用vis数组标记顶点是否已经被访问。

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