迪杰斯特拉（Dijkstra）算法

核心定义：一种基于贪心策略的图算法，用于求解带权有向/无向图中单个源点到其他所有顶点的最短路径，要求图中所有边的权值非负。

1. 核心思想

通过“逐步锁定最短路径”的贪心逻辑，每次从“未确定最短路径的顶点”中，选出距离源点最近的顶点，以该顶点为中间节点，更新其他未确定顶点到源点的距离，重复此过程直至所有顶点的最短路径都被确定。

2. 关键步骤

1. 初始化：

   • 设定一个距离数组，记录源点到每个顶点的距离，初始时源点到自身距离为0，到其他顶点距离为“无穷大”。
   • 设定一个标记数组，标记顶点是否已确定最短路径，初始时所有顶点均为“未确定”。

2. 迭代确定最短路径：

   • 从所有“未确定”的顶点中，选出距离源点最近的顶点（记为u），将其标记为“已确定”。
   • 以u为中间节点，遍历u的所有邻接顶点（记为v）：若“源点→u→v”的路径长度，小于当前记录的“源点→v”的距离，则更新“源点→v”的距离为更短的路径长度。

3. 终止：
   重复步骤2，直到所有顶点都被标记为“已确定”，此时距离数组中存储的就是源点到各顶点的最短路径长度。

#include <stdio.h>
#include <stdbool.h>

#define MAXVEX 100   // 最大顶点数
#define INF 65535    // 表示无穷大（大于所有边权之和）

// 邻接矩阵存储图
typedef struct {
    char vexs[MAXVEX];       // 顶点数组（固定为A、B、C、D）
    int arc[MAXVEX][MAXVEX]; // 邻接矩阵（存储边权）
    int numVexs, numArcs;    // 顶点数、边数（固定值）
} MGraph;

// 1. 初始化固定图（简化：无需手动输入，直接内置图数据）
void InitFixedGraph(MGraph *G) {
    // 1. 固定顶点：4个顶点（A、B、C、D）
    G->numVexs = 4;
    G->vexs[0] = 'A';
    G->vexs[1] = 'B';
    G->vexs[2] = 'C';
    G->vexs[3] = 'D';

    // 2. 固定边数：5条边（无向图）
    G->numArcs = 5;

    // 3. 初始化邻接矩阵为INF（无边），自身距离为0
    int i, j;
    for (i = 0; i < G->numVexs; i++) {
        for (j = 0; j < G->numVexs; j++) {
            G->arc[i][j] = INF;
        }
        G->arc[i][i] = 0;
    }

    // 4. 固定边权（无向图：双向赋值）
    G->arc[0][1] = 2;  // A-B：权2
    G->arc[1][0] = 2;
    G->arc[0][2] = 5;  // A-C：权5
    G->arc[2][0] = 5;
    G->arc[1][2] = 1;  // B-C：权1
    G->arc[2][1] = 1;
    G->arc[1][3] = 6;  // B-D：权6
    G->arc[3][1] = 6;
    G->arc[2][3] = 3;  // C-D：权3
    G->arc[3][2] = 3;

    // 打印提示：告知当前图结构
    printf("已初始化固定图：\n");
    printf("顶点：A(0)、B(1)、C(2)、D(3)\n");
    printf("边（无向）：A-B(2)、A-C(5)、B-C(1)、B-D(6)、C-D(3)\n");
}

// 2. 迪杰斯特拉算法（核心：起点固定为A(0)，贴合基础学习）
void Dijkstra(MGraph G, int startVex, int dist[], int prev[]) {
    bool visited[MAXVEX]; // 标记顶点是否已确定最短路径
    int i, j, u, min;

    // 初始化辅助数组
    for (i = 0; i < G.numVexs; i++) {
        dist[i] = G.arc[startVex][i]; // 初始距离=起点到i的直接边权
        visited[i] = false;           // 所有顶点初始未确定
        prev[i] = (dist[i] != INF) ? startVex : -1; // 记录前驱（无路径为-1）
    }

    // 起点A自身：距离0，已确定
    dist[startVex] = 0;
    visited[startVex] = true;

    // 循环3次（确定剩余3个顶点的最短路径）
    for (i = 1; i < G.numVexs; i++) {
        // 步骤1：选dist中未确定且最小的顶点u
        min = INF;
        for (j = 0; j < G.numVexs; j++) {
            if (!visited[j] && dist[j] < min) {
                min = dist[j];
                u = j;
            }
        }
        visited[u] = true; // 标记u为已确定

        // 步骤2：以u为中间点，更新未确定顶点的dist
        for (j = 0; j < G.numVexs; j++) {
            if (!visited[j] && G.arc[u][j] != INF && (dist[u] + G.arc[u][j] < dist[j])) {
                dist[j] = dist[u] + G.arc[u][j]; // 更新最短距离
                prev[j] = u;                     // 更新前驱顶点
            }
        }
    }
}

// 3. 回溯打印最短路径（从终点到起点，递归实现）
void PrintPath(int prev[], int startVex, int endVex, char vexs[]) {
    if (endVex == startVex) {
        printf("%c", vexs[startVex]); // 终止：打印起点A
        return;
    }
    PrintPath(prev, startVex, prev[endVex], vexs); // 递归找前驱
    printf("→ %c", vexs[endVex]);                   // 正向打印路径
}

// 主函数：直接运行，无需手动输入
int main() {
    MGraph G;
    int startVex = 0; // 固定起点为A(0)，简化操作
    int dist[MAXVEX], prev[MAXVEX]; // 存储最短距离和前驱
    int i;

    // 1. 初始化固定图（无需输入）
    InitFixedGraph(&G);

    // 2. 执行迪杰斯特拉算法
    Dijkstra(G, startVex, dist, prev);

    // 3. 输出结果
    printf("\n=== 起点%c到各顶点的最短路径结果 ===\n", G.vexs[startVex]);
    for (i = 0; i < G.numVexs; i++) {
        if (i == startVex) continue; // 跳过起点A
        if (dist[i] == INF) {
            printf("到%c：无可达路径\n", G.vexs[i]);
        } else {
            printf("到%c：最短距离=%d，路径：", G.vexs[i], dist[i]);
            PrintPath(prev, startVex, i, G.vexs);
            printf("\n");
        }
    }

    return 0;
}

时空复杂度分析

• 时间复杂度：​\boxed{O(n^2)}（n 为顶点数），由两层遍历顶点的嵌套循环主导。
• 空间复杂度：​\boxed{O(n^2)}，主要源于 ​n \times n 的邻接矩阵存储。

迪杰斯特拉算法核心函数（Dijkstra函数）深度解析

Dijkstra函数是整个算法的核心，严格遵循严蔚敏教材中“贪心策略+逐步确定最短路径”的逻辑，负责计算起点到所有顶点的最短距离及路径前驱。以下从参数含义、初始化、核心循环（2个关键步骤） 三部分拆解，结合固定图数据（A为起点）举例说明，让每个细节都清晰可见。

一、函数参数含义（先明确“输入输出”）

函数定义：void Dijkstra(MGraph G, int startVex, int dist[], int prev[])
4个参数各司其职，对应算法的“输入条件”和“输出结果”：

参数名	类型	作用
G	MGraph	输入：已初始化的邻接矩阵图（固定图中包含A/B/C/D顶点及边权）
startVex	int	输入：起点的序号（固定为0，对应顶点A）
dist[]	int	输出：存储“起点到各顶点的最短距离”（如 dist[1]是A到B的最短距离）
prev[]	int	输出：存储“最短路径的前驱顶点序号”（如 prev[2]=1表示A到C的路径中，C的前一个顶点是B）

二、第一步：初始化辅助数组（算法的“初始状态”）

初始化是为了给算法设定“起点视角的初始认知”——刚开始只知道起点到各顶点的“直接距离”，不知道是否有更短的间接路径。代码如下：

// 遍历所有顶点，初始化3个核心数组
for (i = 0; i < G.numVexs; i++) {
    // 1. dist[i]：初始距离 = 起点到i的直接边权（邻接矩阵中直接读取）
    dist[i] = G.arc[startVex][i]; 
    // 2. visited[i]：标记是否已确定最短路径（初始都未确定，设为false）
    visited[i] = false;   
    // 3. prev[i]：前驱顶点（有直接边则前驱是起点，无边则为-1表示无路径）
    prev[i] = (dist[i] != INF) ? startVex : -1; 
}
// 起点自身特殊处理：距离为0，且已确定最短路径（自己到自己只有一种可能）
dist[startVex] = 0;
visited[startVex] = true;

结合固定图的初始化结果（起点A，序号0）

固定图中邻接矩阵 G.arc[0][...]（A到各顶点的直接边权）为：A→A(0)、A→B(2)、A→C(5)、A→D(INF)，因此初始化后数组状态如下：

顶点序号	顶点	dist[]（A到该顶点的初始距离）	visited[]（是否确定）	prev[]（前驱顶点序号）
0	A	0	true	0（自己）
1	B	2（A直接到B）	false	0（前驱是A）
2	C	5（A直接到C）	false	0（前驱是A）
3	D	INF（A到D无直接边）	false	-1（无路径）

三、第二步：核心循环（贪心策略的核心，执行n-1次）

因为起点已经确定最短路径，剩下 n-1个顶点（固定图n=4，所以循环3次），每次循环做两件事：选“当前最短路径顶点”→用该顶点更新其他顶点的距离，逐步把“不确定的路径”变成“确定的最短路径”。

循环逻辑：每次确定1个顶点的最短路径

// 循环n-1次（固定图n=4，循环3次，确定B、C、D的最短路径）
for (i = 1; i < G.numVexs; i++) {
    // --------------------------
    // 子步骤1：选dist中“未确定且距离最小”的顶点u（贪心的关键）
    // --------------------------
    min = INF; // 用min记录当前最小距离（初始设为无穷大）
    for (j = 0; j < G.numVexs; j++) {
        // 条件：j未确定（visited[j]=false）且距离比当前min小
        if (!visited[j] && dist[j] < min) {
            min = dist[j]; // 更新min为更小的距离
            u = j;         // 记录这个“距离最小的顶点”序号u
        }
    }
    visited[u] = true; // 标记u为“已确定最短路径”（后续不再修改）

    // --------------------------
    // 子步骤2：以u为中间点，更新所有“未确定顶点”的dist和prev
    // --------------------------
    for (j = 0; j < G.numVexs; j++) {
        // 条件：j未确定 + u到j有边（G.arc[u][j]≠INF） + “A→u→j”比“当前A→j”短
        if (!visited[j] && G.arc[u][j] != INF && (dist[u] + G.arc[u][j] < dist[j])) {
            dist[j] = dist[u] + G.arc[u][j]; // 更新A到j的最短距离
            prev[j] = u;                     // 更新j的前驱为u（路径变成A→...→u→j）
        }
    }
}

结合固定图的循环过程拆解（3次循环，逐步确定路径）

以固定图（A为起点）为例，逐次分析循环中数组的变化，理解“贪心策略如何工作”：

第1次循环（i=1）：确定第一个顶点的最短路径

• 子步骤1：选u：遍历未确定顶点（B、C、D），dist[1]=2（A→B）最小，所以 u=1（顶点B），标记 visited[1]=true（B的路径已确定）。

• 子步骤2：用u=B更新其他顶点：检查未确定顶点C、D：

  • 对C（j=2）：A→B→C的距离=dist[1]（2）+ G.arc[1][2]（1）=3，比当前dist[2]（5）小 → 更新 dist[2]=3，prev[2]=1（C的前驱从A变成B）。
  • 对D（j=3）：A→B→D的距离=2+6=8，比当前dist[3]（INF）小 → 更新 dist[3]=8，prev[3]=1（D的前驱从-1变成B）。

  此时数组状态：

  顶点	dist[]	visited[]	prev[]
  A	0	true	0
  B	2	true	0
  C	3	false	1
  D	8	false	1

第2次循环（i=2）：确定第二个顶点的最短路径

• 子步骤1：选u：遍历未确定顶点（C、D），dist[2]=3（A→B→C）最小，所以 u=2（顶点C），标记 visited[2]=true（C的路径已确定）。

• 子步骤2：用u=C更新其他顶点：
  只检查未确定顶点D（j=3）：
  A→B→C→D的距离=dist[2]（3）+ G.arc[2][3]（3）=6，比当前dist[3]（8）小 → 更新 dist[3]=6，prev[3]=2（D的前驱从B变成C）。

  此时数组状态：

  顶点	dist[]	visited[]	prev[]
  A	0	true	0
  B	2	true	0
  C	3	true	1
  D	6	false	2

第3次循环（i=3）：确定第三个顶点的最短路径

• 子步骤1：选u：只剩未确定顶点D（j=3），dist[3]=6，所以 u=3（顶点D），标记 visited[3]=true（D的路径已确定）。
• 子步骤2：用u=D更新其他顶点：所有顶点都已确定，无更新。

四、函数最终输出（算法的“结果”）

循环结束后，dist[]和 prev[]数组就存储了完整的最短路径信息：

• dist[] = [0, 2, 3, 6] → A到A(0)、A到B(2)、A到C(3)、A到D(6)；
• prev[] = [0, 0, 1, 2] → 路径回溯：D的前驱是C，C的前驱是B，B的前驱是A → A→B→C→D。

这就是 Dijkstra函数的核心逻辑：通过“每次选当前最短路径顶点，并用它优化其他路径”的贪心策略，最终确定起点到所有顶点的最短路径，完全贴合严蔚敏教材的实现思路。