图的最短路径迪杰斯特拉算法原理实现详解

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 全源最短路等）有很大帮助。建议读者在理解原理的基础上，进一步学习堆优化版本以应对大规模图数据。