图的最短路径Dijkstra

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

先把话说在前面：Dijkstra 算法，可以说是图论世界里的“老朋友”了，但凡涉及最短路径问题，它几乎总是最先被想到的那个。它的适用场景非常明确——边权非负的图，无论是有向还是无向，单源最短路径的求解，它都能漂亮地完成。

它的核心逻辑其实很简单，就四个字：

。什么意思呢？就是每一次，都从那些还没确定最短路径的顶点里，挑出一个当前距离最小的，然后认定它的最短路径就是它了。接着，用这个顶点当中转站，去更新它邻居们的距离。就这么重复 n-1 轮，整个图的最短路径就全出来了。

一、算法简介

Dijkstra 算法专治单源最短路径问题，前提条件是所有边的权值非负。它的策略说起来也不复杂：每次从还没确定最短路径的顶点里，选一个当前距离最小的，把它标记为“已确定”。然后，借助这个顶点，去更新它那些还没被标记的邻居们的距离。重复这个过程，直到所有顶点都确定下来。

二、辅助数组说明

数组	作用
dist[]	记录每个顶点到起点的当前最短距离
flag[]	标记顶点是否已经确定了最短路径（0 未确定，1 已确定）
pre[]	记录最短路径中每个顶点的上一个顶点，用于回溯路径

三、算法步骤

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)）。

七、算法特性总结

特性	说明
适用范围	边权非负的带权图（无向图 / 有向图）
算法思想	贪心：每次取未确定中 dist 最小的顶点
数据结构	邻接矩阵（本实现）/ 邻接表 + 优先队列
时间复杂度	O(n²)（邻接矩阵版）/ O((n+m)log n)（堆优化版）
空间复杂度	O(n²)（邻接矩阵版）
局限性	无法处理负权边（负权边可能导致已确定的 dist 被后续更短的路径违反）

八、总结

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

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

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