前言：前面两篇文章介绍了生成图的最小生成树的算法，接下来两篇文章会介绍图的最短路径的算法，迪杰斯特拉算法和弗洛伊德算法。迪杰斯特拉算法是用来计算一个点到其他所有点的最短路径，这个点称之为源点。
一、实现流程
回忆一下我们之前学习的 Prim 算法，构建最小生成树。从一个顶点出发，不断地寻找离当前生成树最近的节点，将节点加入到生成树。而寻找源点到其他节点的最短路径的 Dijkstra 算法，和 Prim 算法非常的类似。
因为假设当前5号节点和0号节点之间有两条路径，利用 Prim 算法，我们生成一个最小生成树，那么在最小生成树中，0 号节点和 5 号节点之间的路径一定是最短的，也就是 Dijkstra 算法要找的最短路径。所以整个实现流程非常的相似。和 Prim 一样，时间复杂度也是 O(v^2)，只和顶点有关。
具体的实现流程大家可以参考 Prim算法，我就不赘述了，咱们来仔细看一下代码实现上有什么不一样
二、代码实现
1、初始化常量和数据类型
#define MAX_VEX 100
#define INFINITY INT_MAX // 使用 INT_MAX 代表无穷大// 图的结构体定义
typedef struct {int vexnum; // 节点数int arcnum; // 边数int arcs[MAX_VEX][MAX_VEX]; // 邻接矩阵
} MGraph;
首先我们要求源点到其他节点的最短路径 dist，就需要用一个数组，来保存当前源点到所有节点的路径长度。
我们需要一个数组来存储每个节点的 path，每次更新路径长度的时候，都需要更新当前节点的前驱结点。
另外为了防止对一个节点重复进行判断，我们需要一个数组 final，来记录一个节点是否已经找到最短路径 。
// 初始化
const int v0 = 0; // 将源点硬编码为0
int final[MaxVex]; // 记录节点有没有找到最短路径
int path[MaxVex]; // 记录每个节点的前驱结点
int dist[MaxVex]; // 记录源点到每个节点的最短路径
初始化的时候，根据邻接矩阵来初始化 dist 数组，为 0 号节点到其他节点的边的权值； final数组全部初始化为 0 表示都没有访问过，0号节点 final[0] 初始化为 1，表示已经访问过；path 数组和 0 号节点直接相连的节点的 path 记为 0 ，不直接相连的节点 path 记为 -1。
// --- 1. 初始化 ---for (int i = 0; i < G.vexnum; i++) {final[i] = 0; // 所有顶点初始都未找到最短路径dist[i] = G.arcs[v0][i]; // v0 到各点的直连距离if (dist[i] < INFINITY && i != v0) {path[i] = v0; // 如果有直连路径, 前驱为 v0} else {path[i] = -1; // 否则无前驱}}dist[v0] = 0; // 源点到自身的距离为 0final[v0] = 1; // 源点已找到最短路径path[v0] = -1; // 源点无前驱接下来就是主要的处理过程。首先外层需要 G.vexnum - 1 次循环，因为每次只能找到一个最近节点。内层有两个操作需要循环：一个是找当前最近的节点；另一个是以找到的最近节点更新剩下的 dist 数组。
还要初始化一个 k 变量，用来记录每次找到的距离 0 号节点最近的节点
// --- 2. 主循环: 每次找到一个顶点的最短路径 ---
int k = -1; // k 用于记录当前找到的最近顶点的索引
for (int i = 1; i < G.vexnum; i++) { // 循环 n-1 次, 找出 n-1 个顶点的最短路int min = INFINITY;// a. 寻找当前离源点最近的未访问顶点 kfor (int j = 0; j < G.vexnum; j++) {if (!final[j] && dist[j] < min) {min = dist[j];k = j;}}// b. 将 k 标记为已找到最短路径final[k] = 1;// c. 以 k 为跳板, 更新其他未访问顶点的距离for (int j = 0; j < G.vexnum; j++) {// 如果 j 未被访问, 且经过 k 到达 j 的距离更短if (!final[j] && (long)dist[k] + G.arcs[k][j] < dist[j]) {dist[j] = dist[k] + G.arcs[k][j]; // 更新距离path[j] = k; // 更新前驱}}
}
三、整体代码
// 迪杰斯特拉算法 源点到其他节点的最短路径
#include <stdio.h>
#include <stdlib.h>
#include <limits.h> // 用于 INT_MAX#define MAX_VEX 100
#define INFINITY INT_MAX // 使用 INT_MAX 代表无穷大// 图的结构体定义
typedef struct {int vexnum; // 节点数int arcnum; // 边数int arcs[MAX_VEX][MAX_VEX]; // 邻接矩阵
} MGraph;// 迪杰斯特拉算法 (源点默认为0)
void Dijkstra(MGraph G) {const int v0 = 0; // 将源点硬编码为0int final[MAX_VEX]; // final[i]=1 表示已找到从 v0 到 vi 的最短路径int path[MAX_VEX]; // path[i] 记录 vi 的前驱顶点int dist[MAX_VEX]; // dist[i] 记录从 v0 到 vi 的当前最短路径长度// --- 1. 初始化 ---for (int i = 0; i < G.vexnum; i++) {final[i] = 0; // 所有顶点初始都未找到最短路径dist[i] = G.arcs[v0][i]; // v0 到各点的直连距离if (dist[i] < INFINITY && i != v0) {path[i] = v0; // 如果有直连路径, 前驱为 v0} else {path[i] = -1; // 否则无前驱}}dist[v0] = 0; // 源点到自身的距离为 0final[v0] = 1; // 源点已找到最短路径path[v0] = -1; // 源点无前驱// --- 2. 主循环: 每次找到一个顶点的最短路径 ---int k = -1; // k 用于记录当前找到的最近顶点的索引for (int i = 1; i < G.vexnum; i++) { // 循环 n-1 次, 找出 n-1 个顶点的最短路int min = INFINITY;// a. 寻找当前离源点最近的未访问顶点 kfor (int j = 0; j < G.vexnum; j++) {if (!final[j] && dist[j] < min) {min = dist[j];k = j;}}// b. 将 k 标记为已找到最短路径final[k] = 1;// c. 以 k 为跳板, 更新其他未访问顶点的距离for (int j = 0; j < G.vexnum; j++) {// 如果 j 未被访问, 且经过 k 到达 j 的距离更短if (!final[j] && (long)dist[k] + G.arcs[k][j] < dist[j]) {dist[j] = dist[k] + G.arcs[k][j]; // 更新距离path[j] = k; // 更新前驱}}}// --- 3. 打印结果 ---printf("从源点 %d 到各顶点的最短路径和距离如下:\n", v0);for (int i = 0; i < G.vexnum; i++) {if (i == v0) continue;printf("顶点 %d: 距离 = %-5d, 路径: ", i, dist[i]);int temp_path[MAX_VEX];int count = 0;int p = i;while (p != -1) {temp_path[count++] = p;p = path[p];}for (int j = count - 1; j >= 0; j--) {printf("%d", temp_path[j]);if (j > 0) printf(" -> ");}printf("\n");}
}int main() {MGraph G;// 初始化图G.vexnum = 6; // 6个顶点 (0, 1, 2, 3, 4, 5)G.arcnum = 11; // 11条边for (int i = 0; i < G.vexnum; i++) {for (int j = 0; j < G.vexnum; j++) {if (i == j) {G.arcs[i][j] = 0;} else {G.arcs[i][j] = INFINITY;}}}// 构建一个全连通的有向图的邻接矩阵G.arcs[0][1] = 50;G.arcs[0][2] = 10;G.arcs[0][4] = 45;G.arcs[0][5] = 100;G.arcs[1][2] = 15;G.arcs[1][4] = 10;G.arcs[2][0] = 20;G.arcs[2][3] = 15;G.arcs[3][1] = 20;G.arcs[3][4] = 35;G.arcs[4][3] = 30;G.arcs[5][3] = 3;Dijkstra(G); // 调用函数, 无需传入源点return 0;
}
其实和 Prim 算法只有一点不一样，就是更新其他未访问顶点的距离中的条件
Prim 算法是 if(lowcost[j]!=0 && G.arcs[k][j]<lowcost[j])
Dijkstra 算法是 if (!final[j] && (long)dist[k] + G.arcs[k][j] < dist[j])
前半句都是判断节点是否已经被访问过，只有后半句不一样
Prim 算法是生成最小生成树，当加入一个节点的时候，这个节点和树中的其他节点形成一个整体，因此只要 k 这个节点到 j 的距离更小，说明 j 离生成树的距离还可以更近，就更新 j 节点的路径
Dijkstra 算法是计算源点到其他节点的距离，所以必须对比从 源点到k+k到j 和 dist[j]
)
