从基础到优化：深入理解Dijkstra最短路径算法
引言：为什么需要最短路径算法？
想象一下，你正在使用导航软件规划从家到公司的路线。导航会快速为你推荐一条「最优路径」——可能是最短时间、最少红绿灯或最低油耗。这种场景背后，正是最短路径算法在发挥作用。其中，Dijkstra算法是解决非负权图最短路径问题的经典方法。本文将从基础实现出发，逐步讲解其优化思路，并通过代码对比帮助初学者建立系统性认知。
一、基础Dijkstra算法：逐层探索的智慧
1.1 算法核心思想
Dijkstra算法基于贪心策略，通过不断确定当前已知的「最短路径节点」来逐步扩展搜索范围。其核心步骤可以概括为：
1.初始化：起点距离设为0，其他节点设为无穷大。
2.选择未访问的最小距离节点。
3.松弛操作：更新该节点邻居的最短距离。
4.重复上述步骤直到所有节点被访问。
1.2 代码实现解析（邻接表版）
// 链式前向星存储结构
struct Edge {
int to; // 目标节点
int w; // 边权
int next; // 下一条边的索引
} edges[10005];
// Dijkstra算法实现（适用于非负权图）
void dijkstra() {
memset(dis, 0x3f, sizeof(dis)); // 初始化所有节点距离为INF
memset(vis, 0, sizeof(vis)); // 初始化所有节点未访问
dis[s] = 0; // 起点到自身距离为0
// 遍历n次，每次确定一个节点的最短路径
for (int cnt = 0; cnt < n; ++cnt) {
// 寻找当前未访问节点中距离最小的节点u
int u = -1, min_dis = INF;
for (int i = 1; i <= n; ++i) {
if (!vis[i] && dis[i] < min_dis) {
min_dis = dis[i];
u = i;
}
}
// 若未找到可达节点，提前退出
if (u == -1) break;
vis[u] = 1; // 标记u的最短路径已确定
// 松弛操作：遍历u的所有邻接边，更新邻接节点的距离
for (int i = head[u]; i != -1; i = edges[i].next) {
int v = edges[i].to;
int w = edges[i].w;
// 若通过u到v的距离更短，则更新dis[v]
if (!vis[v] && dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
}
}
}
}
关键点说明：
链式前向星：高效存储稀疏图的邻接表结构，head[x]指向节点x的第一条边索引。
时间复杂度：O(V²)，适合节点数较少的场景（V≤10³）。
局限性：每次需要遍历所有节点寻找最小值，效率较低。
二、优化版Dijkstra：优先队列加速
2.1 优化思路：用空间换时间
基础实现的瓶颈在于「寻找最小距离节点」。优化思路是使用优先队列（小顶堆）：
队列存储(距离, 节点)对
每次弹出当前距离最小的节点
时间复杂度降为O((V+E)logV)
2.2 优化核心代码实现
priority_queue
void dijkstra() {
memset(dis, 0x3f, sizeof(dis)); // 初始化为极大值（0x3f3f3f3f约等于10^9）
dis[s] = 0; // 起点到自身距离为0
q.push({0, s}); // 初始状态入队
while (!q.empty()) {
PII t = q.top(); // 取出当前距离最小的节点
q.pop();
int u = t.second; // 当前节点编号
int d = t.first; // 当前距离
if (flag[u]) continue; // 如果已确定最短路径，跳过
flag[u] = 1; // 标记为已处理
// 遍历所有邻接边（链式前向星遍历方式）
for (int i = head[u]; i != -1; i = e[i].next) {
int v = e[i].to; // 邻接顶点
int w = e[i].w; // 边权
// 松弛操作：发现更短路径时更新
if (!flag[v] && dis[v] > dis[u] + w) {
dis[v] = dis[u] + w; // 更新最短距离
q.push({dis[v], v}); // 新路径入队
}
}
}
}
优化亮点：
堆优化：用O(logV)的时间完成最小值查找。
懒惰删除：允许队列中存在多个相同节点的不同距离值，通过flag数组过滤过时数据。
适用场景：更适合边数较多的稀疏图（如社交网络、交通路线）。
三、两种实现的对比与选型
特性基础版本优先队列优化版时间复杂度O(V²)O((V+E)logV)空间复杂度O(V+E)O(V+E)最佳适用场景稠密图（V较小）稀疏图（E≈V）实现难度简单需理解优先队列特性扩展性难以处理大规模数据支持更大规模数据选择建议：
竞赛场景：优先使用优化版，应对各种规模的数据。
教学场景：建议先掌握基础版，再理解优化思路。
工程实践：结合具体图特征选择，超大规模数据可考虑更高级的优化。
四、总结与升华
通过这两个版本的代码对比，我们能看到算法优化的典型思路：用数据结构换取时间效率。Dijkstra算法的核心思想从未改变，但通过引入优先队列，我们让算法焕发了新的生命力。
建议初学者：
先手写基础版，理解每个变量的含义
用纸笔模拟小规模图的运行过程
尝试修改代码处理无向图或输出路径
最后挑战优先队列优化版
最后完整代码附上：
基础Dijkstra算法
#include
using namespace std;
const int MAX_N = 105; // 最大节点数
const int INF = 0x3f3f3f3f; // 表示无穷大的值（方便memset初始化且足够大）
// 边结构定义（链式前向星存储方式，用于高效存储稀疏图）
struct Edge {
int to; // 目标节点编号
int w; // 边的权值
int next; // 同一源节点的下一条边在edges数组中的索引
} edges[10005]; // 预分配的边数组（静态存储）
int n, m, s; // 节点数、边数、起点编号
int dis[MAX_N]; // 记录起点到各节点的最短距离
int vis[MAX_N]; // 标记节点是否已确定最短路径
int head[MAX_N]; // 邻接表头指针数组，head[x]表示节点x的第一条边索引
int edge_cnt; // 当前边的数量，用于动态添加边
// 添加有向边（x -> y，权值为w）
void add_edge(int x, int y, int w) {
edges[edge_cnt].to = y;
edges[edge_cnt].w = w;
edges[edge_cnt].next = head[x]; // 新边的next指向原头边
head[x] = edge_cnt++; // 更新头指针为当前边，并递增计数器
}
// Dijkstra算法实现（适用于非负权图）
void dijkstra() {
memset(dis, 0x3f, sizeof(dis)); // 初始化所有节点距离为INF
memset(vis, 0, sizeof(vis)); // 初始化所有节点未访问
dis[s] = 0; // 起点到自身距离为0
// 遍历n次，每次确定一个节点的最短路径
for (int cnt = 0; cnt < n; ++cnt) {
// 寻找当前未访问节点中距离最小的节点u
int u = -1, min_dis = INF;
for (int i = 1; i <= n; ++i) {
if (!vis[i] && dis[i] < min_dis) {
min_dis = dis[i];
u = i;
}
}
// 若未找到可达节点，提前退出
if (u == -1) break;
vis[u] = 1; // 标记u的最短路径已确定
// 松弛操作：遍历u的所有邻接边，更新邻接节点的距离
for (int i = head[u]; i != -1; i = edges[i].next) {
int v = edges[i].to;
int w = edges[i].w;
// 若通过u到v的距离更短，则更新dis[v]
if (!vis[v] && dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
}
}
}
}
int main() {
// 初始化邻接表头指针（-1表示无出边）
memset(head, -1, sizeof(head));
edge_cnt = 0;
cin >> n >> m >> s;
// 读取m条边并构建邻接表
for (int i = 0; i < m; ++i) {
int x, y, w;
cin >> x >> y >> w;
add_edge(x, y, w); // 添加有向边x->y
}
dijkstra();
// 输出结果（节点编号从1开始）
for (int i = 1; i <= n; ++i) {
if (dis[i] == INF)
cout << "INF "; // 不可达节点
else
cout << dis[i] << " ";
}
return 0;
}
Dijkstra算法（优先队列优化版）
#include
using namespace std;
typedef pair
// 全局变量定义
int n; // 顶点总数
int m; // 边总数
int s; // 起点编号
int dis[105]; // 存储起点到各顶点的最短距离（节点编号从1开始）
int flag[105];// 标记顶点是否已确定最短路径
int cut; // 边计数器（用于链式前向星）
// 边结构体（链式前向星）
struct Edge {
int to; // 目标顶点
int w; // 边权重
int next; // 下一条边的索引
} e[10005]; // 边存储池（足够大的空间存储所有边）
int head[105]; // 邻接表头指针数组（初始化为-1）
priority_queue
/* 添加有向边到邻接表
* 参数：
* x - 起点
* y - 终点
* w - 边权
*/
void add(int x, int y, int w) {
e[cut].to = y; // 设置目标顶点
e[cut].w = w; // 设置边权
e[cut].next = head[x];// 插入到链表头部
head[x] = cut; // 更新头指针
cut++; // 边计数器递增
}
/* Dijkstra算法实现 */
void dijkstra() {
memset(dis, 0x3f, sizeof(dis)); // 初始化为极大值（0x3f3f3f3f约等于10^9）
dis[s] = 0; // 起点到自身距离为0
q.push({0, s}); // 初始状态入队
while (!q.empty()) {
PII t = q.top(); // 取出当前距离最小的节点
q.pop();
int u = t.second; // 当前节点编号
int d = t.first; // 当前距离
if (flag[u]) continue; // 如果已确定最短路径，跳过
flag[u] = 1; // 标记为已处理
// 遍历所有邻接边（链式前向星遍历方式）
for (int i = head[u]; i != -1; i = e[i].next) {
int v = e[i].to; // 邻接顶点
int w = e[i].w; // 边权
// 松弛操作：发现更短路径时更新
if (!flag[v] && dis[v] > dis[u] + w) {
dis[v] = dis[u] + w; // 更新最短距离
q.push({dis[v], v}); // 新路径入队
}
}
}
}
int main() {
// 输入初始化
cin >> n >> m >> s;
memset(head, -1, sizeof(head)); // 初始化邻接表头指针（-1表示空）
// 读入边数据
int x, y, w;
for (int i = 1; i <= m; i++) {
cin >> x >> y >> w;
add(x, y, w); // 添加有向边
}
// 执行算法
dijkstra();
// 输出结果（节点从1开始编号）
for (int i = 1; i <= n; i++) {
cout << dis[i] << " ";
/* 输出说明：
* 若结果仍为0x3f3f3f3f，表示该节点不可达
* 示例输入：
* 4 5 1
* 1 2 2
* 1 3 1
* 2 3 3
* 2 4 4
* 3 4 5
* 对应输出应为：0 2 1 6
*/
}
return 0;
}
正如计算机科学家Edsger Dijkstra所说：「程序测试可以证明存在错误，但永远无法证明没有错误。」在掌握算法后，不妨尝试构造各种测试用例，在实践中深化理解。