Dijkstra算法：图的最短路径

最短路径算法：Dijkstra（迪杰斯特拉算法）

Dijkstra 算法是图论中解决最短路径问题的经典算法，专门用于求解边权非负的图（包括有向图和无向图）中单源最短路径问题。该算法以其简洁高效的设计，成为最常被优先考虑的最短路径算法之一。

Dijkstra 算法的核心思想可概括为贪心策略：每次从尚未确定最短路径的顶点中，选出当前距离最小的顶点，将其最短路径锁定；随后以该顶点为中转站，更新其邻居顶点的距离。重复执行该过程 n-1 轮，即可得到图中所有顶点的最短路径。

一、算法简介

Dijkstra 算法专门用于解决单源最短路径问题，其适用前提为图中所有边的权值均为非负数。算法的基本策略是：每次从尚未确定最短路径的顶点中，选出当前距离最小的顶点，将其标记为已确定；随后借助该顶点，更新其未被标记的邻居顶点的距离。重复上述过程，直至所有顶点均被确定。

二、辅助数组说明

三、算法步骤

Step 1 选定起点，将起点能够直接到达的顶点的距离初始化为对应边的权值。

Step 2 在尚未确定最短路径的顶点中，选取当前距离最小的顶点——该顶点的最短路径在此刻被锁定。由于所有边权非负，不存在其他路径能够比当前路径更短。

Step 3 以该顶点为中转站，检查其邻居顶点：若经过该顶点的路径比邻居顶点原有的距离更短，则更新邻居顶点的距离，并记录路径。

Step 4 重复 Step 2 和 Step 3 共 n-1 次，即可得到所有顶点的最短路径。

四、完整代码实现（邻接矩阵版）

#include
#include
#include
#define INF 10001

// n（<=100）个点，m 条边的带权无向图（边权 < 10000）
// 求起点 s 到其他点的最短路径，保证起点一定能走到其他点
// 顶点编号 0 ~ n-1

int n, m, v;
int g[105][105]; // 邻接矩阵
int dist[105];    // 最短距离
int flag[105];    // 标记是否已确定
int pre[105];     // 前驱顶点

void Dijkstra(int s) // 时间复杂度 O(n)
{
    // === 初始化起点 ===
    dist[s] = 0;
    flag[s] = 1;

    // === 第一步：更新起点的邻接点 ===
    for (int i = 0; i < n; i++)
    {
        if (g[s][i] < INF) // i 是 s 的邻接点
        {
            dist[i] = g[s][i];
            pre[i] = s;
        }
    }
    pre[s] = -1; // 起点的前驱设为 -1

    // === 核心循环：执行 n-1 次，每次确定一个顶点的最短路径 ===
    int k;      // 当前轮选中的顶点
    int minn;   // 当前轮最小的 dist 值

    for (int j = 1; j <= n - 1; j++)
    {
        // --- Step 1：在未标记的顶点中找 dist 最小的顶点 ---
        k = -1;
        minn = INF;
        for (int i = 0; i < n; i++)
        {
            if (flag[i] == 0 && dist[i] < minn)
            {
                k = i;
                minn = dist[i];
            }
        }

        // 找不到可达顶点 → 起点无法到达所有点
        if (k == -1)
        {
            v = 1;
            break;
        }

        // --- Step 2：标记 k，其最短路径已确定 ---
        flag[k] = 1;

        // --- Step 3：以 k 为中转点，松弛其邻接点 ---
        for (int i = 0; i < n; i++)
        {
            if (flag[i] == 0 && dist[k] + g[k][i] < dist[i])
            {
                dist[i] = dist[k] + g[k][i];
                pre[i] = k; // 记录路径
            }
        }
    }
}

int main()
{
    scanf("%d %d", &n, &m);

    // === 初始化邻接矩阵和辅助数组 ===
    for (int i = 0; i < n; i++)
    {
        dist[i] = INF;
        pre[i] = -1;
        for (int j = 0; j < n; j++)
        {
            g[i][j] = INF;
            if (i == j) g[i][j] = 0; // 自己到自己的距离为 0
        }
    }

    // === 读入边 ===
    int x, y, w;
    for (int i = 1; i <= m; i++)
    {
        scanf("%d %d %d", &x, &y, &w);
        g[x][y] = g[y][x] = w; // 无向图双向赋值
    }

    int s;
    scanf("%d", &s);
    Dijkstra(s);

    // === 输出结果 ===
    if (v == 1)
    {
        printf("起点无法到达所有的点n");
    }
    for (int i = 0; i < n; i++)
    {
        printf("%d到%d的最短路径长度是%d，其路径为：%d ", s, i, dist[i], i);
        int p = pre[i];
        while (p != -1)
        {
            printf("%d ", p);
            p = pre[p];
        }
        printf("n");
    }
    return 0;
}

/*测试数据：
9 16
0 1 1
0 2 5
1 2 3
1 3 7
1 4 5
2 4 1
2 5 7
3 4 2
3 6 3
4 5 3
4 6 6
4 7 9
5 7 5
6 7 2
6 8 7
7 8 4
*/

五、关键代码分析

5.1 初始化阶段（第 38-46 行）

dist[s] = 0;
flag[s] = 1;
for (int i = 0; i < n; i++)
    if (g[s][i] < INF) {
        dist[i] = g[s][i];
        pre[i] = s;
    }
pre[s] = -1;

• 起点 s 的 dist 设为 0，并标记为已确定。
• 遍历所有顶点，将起点 s 能直接到达的邻接点的 dist 初始化为边权值，前驱指向 s。
• pre[s] = -1 作为路径回溯的终止条件。

5.2 寻找未标记的最小 dist 顶点（第 56-64 行）

k = -1;
minn = INF;
for (int i = 0; i < n; i++)
    if (flag[i] == 0 && dist[i] < minn) {
        k = i;
        minn = dist[i];
    }

• 线性扫描所有顶点，在未被标记的顶点中挑选 dist 值最小的。
• k = -1 作为哨兵值：若循环结束后 k 仍为 -1，说明剩余顶点均不可达（连通性判断）。
• 贪心选择正确性：由于边权非负，当前全局最小的 dist[k] 不可能再被其他路径缩短，因此 k 的最短路径可以立即确定。

5.3 松弛操作（第 73-79 行）

for (int i = 0; i < n; i++)
    if (flag[i] == 0 && dist[k] + g[k][i] < dist[i]) {
        dist[i] = dist[k] + g[k][i];
        pre[i] = k;
    }

• 以 k 为中转点，遍历所有顶点检查能否缩短距离。
• 条件 dist[k] + g[k][i] < dist[i] 即为三角不等式的松弛判断。
• 只有未被标记的顶点需要更新（已标记的顶点最短路径已确定，不可能更短）。
• 更新 pre[i] 记录路径，便于后续回溯输出。

5.4 路径回溯（第 97-102 行）

printf("%d到%d的最短路径长度是%d，其路径为：%d ", s, i, dist[i], i);
int p = pre[i];
while (p != -1) {
    printf("%d ", p);
    p = pre[p];
}

• 从目标顶点 i 开始，通过 pre[] 数组不断回溯到前驱，直到 pre[p] == -1（到达起点）。
• 由于是从终点向起点回溯，输出的顶点顺序是反向的（实际路径中 i 在前，起点在最后）。

六、复杂度分析

时间复杂度：O(n)

• 外层循环：n-1 轮确定 n-1 个顶点。
• 每轮内部执行两次线性扫描：
  • 寻找最小 dist：扫描 n 个顶点 → O(n)
  • 松弛邻接点：扫描 n 个顶点 → O(n)
• 总复杂度：n × (n + n) = O(n)

空间复杂度：O(n)

• 邻接矩阵 g[105][105] 占用 O(n) 空间。
• 辅助数组 dist[]、flag[]、pre[] 各占用 O(n)。

当 n 较大（> 10）时，邻接矩阵版将超时或超内存，此时应改用邻接表 + 优先队列优化（堆优化 Dijkstra，复杂度 O((n+m)log n)）。

七、算法特性总结

八、总结

Dijkstra 算法是图论中最基础、最常用的最短路径算法之一。其代码实现简洁清晰，核心逻辑可以概括为三个步骤的循环：

1. 选点 — 从未标记的顶点中选 dist 最小的
2. 标记 — 该点最短路径确定
3. 松弛 — 用该点更新邻接点的 dist

掌握 Dijkstra 的思想对于理解更复杂的图论算法（如 A* 搜索、Johnson 全源最短路等）有很大帮助。建议读者在理解原理的基础上，进一步学习堆优化版本以应对大规模图数据。