c语言实现 单源最短路径 实践Dijkstra算法

Dijkstra算法是解决单源最短路径问题的一种经典算法，它可以用于有向图和无向图，但是不能处理负权边。下面是用C语言实现Dijkstra算法的基本步骤：

1. 初始化：将源点s到各个顶点的距离d[i]初始化为无穷大，将源点s到自身的距离d[s]初始化为0，将所有顶点标记为未访问。

2. 选取顶点：从未访问的顶点中选取距离源点s最近的顶点v作为当前顶点。

3. 更新距离：对于当前顶点v的每个邻接顶点w，如果通过v可以使s到w的距离变小，则更新d[w]的值。

4. 标记顶点：将顶点v标记为已访问。

5. 重复步骤2~4，直到所有顶点都被访问过或者找不到更短的路径。

下面是一个简单的C语言实现：

#include <stdio.h>
#define INF 0x3f3f3f3f // 定义无穷大

int main()
{
    int n, m, s, i, j;
    int u, v, w, min, pos;
    int d[1001], vis[1001], G[1001][1001];

    // 输入n, m, s和邻接矩阵G
    scanf("%d%d%d", &n, &m, &s);
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            G[i][j] = INF;
    for (i = 1; i <= m; i++) {
        scanf("%d%d%d", &u, &v, &w);
        G[u][v] = w;
        G[v][u] = w; // 如果是无向图，这行可以去掉
    }

    // 初始化
    for (i = 1; i <= n; i++) {
        d[i] = G[s][i];
        vis[i] = 0;
    }
    d[s] = 0;
    vis[s] = 1;

    // Dijkstra算法
    for (i = 1; i < n; i++) {
        min = INF;
        for (j = 1; j <= n; j++) {
            if (!vis[j] && d[j] < min) {
                min = d[j];
                pos = j;
            }
        }
        vis[pos] = 1;
        for (j = 1; j <= n; j++) {
            if (!vis[j] && d[pos] + G[pos][j] < d[j])
                d[j] = d[pos] + G[pos][j];
        }
    }

    // 输出结果
    for (i = 1; i <= n; i++)
        printf("%d ", d[i]);
    printf("\n");

    return 0;
}

输入格式：

第一行包含三个整数n, m, s，表示图的顶点数、边数和起点。

接下来m行，每行包含三个整数u, v, w，表示一条边从u到v，权值为w。

输出格式：

输出从起点s到每个顶点的最短距离。

时间复杂度：O(n^2)

空间复杂度：O(n^2)