探秘 Dijkstra 算法：从原理到实现，轻松掌握单源最短路径问题
一、引言在图论的世界里，最短路径问题是一个极具吸引力且应用广泛的领域。无论是导航系统中规划最优路线，还是网络路由中寻找最快的数据传输路径，最短路径算法都发挥着至关重要的作用。Dijkstra 算法作为解决单源最短路径问题的经典算法，自 1959 年由荷兰计算机科学家 Edsger Wybe Dijkstra 提出以来，凭借其高效性和可靠性，成为众多开发者和研究者的首选工具。本文将深入剖析 Dijkstra 算法的原理、实现过程，并通过代码示例帮助大家更好地理解和应用该算法。
二、Dijkstra 算法原理
（一）问题定义单源最短路径问题，即在一个带权有向图（也适用于无向图，可将无向图看作双向有向图）中，找到从一个指定源点到其他所有节点的最短路径。这里的 “最短” 通常指路径上所有边的权值之和最小。
（二）核心思想Dijkstra 算法采用贪心策略，以源点为中心，逐步向外扩展寻找最短路径。它维护两个集合：已确定最短路径的节点集合 S：初始时，该集合仅包含源点。未确定最短路径的节点集合 U：包含图中除源点外的所有节点。算法每次从集合 U 中选择距离源点最近（权值和最小）的节点，将其加入集合 S，并以该节点为跳板，更新集合 U 中其他节点到源点的距离。重复此过程，直到集合 U 为空，此时源点到所有节点的最短路径均已确定。
（三）具体步骤初始化：将源点到自身的距离设为 0，到其他节点的距离设为无穷大；将源点加入集合 S，其他节点加入集合 U。寻找最小距离节点：在集合 U 中找到距离源点最近的节点 v，将 v 从集合 U 中移除并加入集合 S。更新距离：遍历节点 v 的所有邻接节点 u，若通过 v 到达 u 的距离比当前记录的 u 到源点的距离更短，则更新 u 到源点的距离。重复步骤 2 和 3，直到集合 U 为空。
三、Dijkstra 算法实现
（一）数据结构在实现 Dijkstra 算法时，我们通常使用以下数据结构：图的存储：可以使用邻接矩阵或邻接表，邻接表在稀疏图中更节省空间，效率更高，因此是更常用的选择。距离数组 dist []：记录源点到每个节点的当前最短距离。集合 S 和 U：可以使用布尔数组或其他数据结构标记节点是否已加入集合 S。优先队列（堆）：为了快速找到集合 U 中距离源点最近的节点，优先队列是一个很好的选择，它能将查找最小距离节点的时间复杂度从(O(V))（V 为节点数）降低到(O(logV))。（二）C++ 代码示例下面是使用邻接表和优先队列实现 Dijkstra 算法的 C++ 代码：cpp#include
include
include
include
using namespace std;
// 定义边的结构体
struct Edge {
int to;
int weight;
Edge(int t, int w) : to(t), weight(w) {}
};
// Dijkstra算法函数
vector dijkstra(int n, int start, const vector
vector dist(n, INT_MAX);
dist[start] = 0;
// 优先队列，按照距离从小到大排序
priority_queue
pq.push({0, start});
while (!pq.empty()) {
int d = pq.top().first;
int u = pq.top().second;
pq.pop();
// 如果当前距离比已记录的距离大，跳过
if (d > dist[u]) {
continue;
}
// 遍历u的所有邻接边
for (const auto& edge : graph[u]) {
int v = edge.to;
int w = edge.weight;
// 如果通过u到达v的距离更短，更新距离并加入优先队列
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
return dist;
}
解决 “收集宝藏” 问题：
使用状态压缩与 Dijkstra 算法的巧妙结合在算法竞赛和实际编程中，路径规划和最短路问题是常见的经典题型。今天，我们就来剖析一道有趣的题目 ——“收集宝藏”，并通过状态压缩和 Dijkstra 算法的结合，巧妙地解决它。
一、题目背景与要求题目设定小 A 在一个由n个点、m条边构成的无向带权连通图迷宫中，起点为1，终点为n，迷宫里有三个宝藏，分别位于(x_1)、(x_2)、(x_3)。小 A 必须收集完所有宝藏后才能从终点离开，我们的目标是计算小 A 完成这一任务所需行走的最小总距离。
二、输入输出格式输入包含T组数据，每组数据第一行给出n、m、(x_1)、(x_2)、(x_3)，后续m行每行给出u、v、w，表示u和v之间存在一条边权为w的无向边。输出共T行，每行对应一组数据中小 A 需要行走的最短总距离。
三、解题思路（一）状态压缩由于只有三个宝藏，我们可以使用一个三位的二进制数来表示宝藏的收集状态，例如：
000 表示三个宝藏都未收集001 表示收集了第一个宝藏010 表示收集了第二个宝藏011 表示收集了前两个宝藏111 表示三个宝藏都已收集
（二）Dijkstra 算法Dijkstra 算法是用于求解单源最短路径的经典算法，我们在传统 Dijkstra 算法的基础上，将状态压缩融入其中。每次拓展节点时，根据到达节点是否存在宝藏，更新其状态，并计算相应的最短距离。四、代码实现详解下面我们结合具体的 C++ 代码来详细解读实现过程。
cpp#include
include
include
include
include
using namespace std;
// 定义状态结构体，记录当前节点的距离、节点编号和宝藏收集状态
struct State {
long long dist;
int u;
int mask;
State(long long d, int u_, int m) : dist(d), u(u_), mask(m) {}
// 重载比较运算符，用于优先队列的比较
bool operator>(const State& other) const {
return dist > other.dist;
}
};
int main() {
// 关闭同步流，加速输入输出
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n, m, x1, x2, x3;
cin >> n >> m >> x1 >> x2 >> x3;
// 邻接表存储图结构
vector
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
// 记录每个节点对应的宝藏状态掩码
vector
treasure_mask[x1] = 1 << 0;
treasure_mask[x2] = 1 << 1;
treasure_mask[x3] = 1 << 2;
// 二维数组存储从起点到每个节点在不同状态下的最短距离
vector
dist[1][0] = 0;
// 优先队列，按照距离从小到大排序
priority_queue
pq.emplace(0, 1, 0);
long long ans = LLONG_MAX;
while (!pq.empty()) {
State cur = pq.top();
pq.pop();
long long d = cur.dist;
int u = cur.u;
int mask = cur.mask;
// 如果到达终点且收集完所有宝藏，更新答案
if (u == n && mask == 0b111) {
ans = d;
break;
}
// 如果当前距离大于已记录的最短距离，跳过
if (d > dist[u][mask]) {
continue;
}
// 遍历当前节点的所有邻接边
for (const auto& edge : adj[u]) {
int v = edge.first;
int w = edge.second;
// 更新到达节点的宝藏收集状态
int new_mask = mask | treasure_mask[v];
long long new_dist = d + w;
// 如果新距离更短，更新最短距离并加入优先队列
if (new_dist < dist[v][new_mask]) {
dist[v][new_mask] = new_dist;
pq.emplace(new_dist, v, new_mask);
}
}
}
cout << ans << '\n';
}
return 0;
}
数据读取与初始化：首先读取测试数据组数T，对于每组数据，读取节点数n、边数m以及三个宝藏的位置。然后构建图的邻接表，并初始化每个节点对应的宝藏状态掩码。距离数组与优先队列：使用二维数组dist记录从起点到每个节点在不同状态下的最短距离，初始化为极大值，将起点在初始状态下的距离设为0。同时，创建一个优先队列pq，用于存储待拓展的节点状态。Dijkstra 算法核心逻辑：在循环中，每次取出优先队列中距离最小的节点状态，检查是否到达终点且收集完所有宝藏，如果是则更新答案。接着遍历该节点的所有邻接边，根据目标节点的宝藏情况更新状态和距离，如果新距离更短，则更新dist数组并将新状态加入优先队列。输出结果：最后输出小 A 收集完所有宝藏并到达终点的最短总距离。
五、总结通过状态压缩与 Dijkstra 算法的结合，我们巧妙地解决了 “收集宝藏” 这一问题。这种思路在处理具有多种状态的路径规划问题时非常有效，能够帮助我们在复杂的情况中找到最优解。希望这篇博客能帮助大家更好地理解这类问题的解法，在未来的算法学习和竞赛中有所启发！编辑分享给出具体的输入输出格式如何使用状态压缩与Dijkstra算法结合解决问题？代码实现中，如何表示状态压缩？