AC君发布内容盲猜
2025-12-14 20:48:33
发布于：江苏
本来想问一下姓艾名哎的“入”迪杰斯特拉算法（AC君爆肝ING），结果……
我看不懂了，各位大佬看吧QAQ
迪杰斯特拉算法：从原理到 C++ 实战，掌握单源最短路径求解
迪杰斯特拉（Dijkstra）算法是图论领域解决单源最短路径问题的经典贪心算法，由荷兰计算机科学家艾兹赫尔・迪杰斯特拉于 1956 年提出。该算法适用于带非负权边的有向 / 无向图，能高效求解从单个起点到所有其他顶点的最短路径，广泛应用于地图导航、网络路由规划、资源调度等场景。本文将从核心原理出发，结合 C++ 代码实现，全方位讲解迪杰斯特拉算法。
一、算法核心原理
迪杰斯特拉算法的核心是 “贪心策略 + 松弛操作”，通过逐步锁定起点到各顶点的最短路径，最终得到全局最优解。具体步骤如下：1. 初始化定义距离数组dist[]，dist[v]表示起点到顶点v的当前最短距离，初始时起点dist[start] = 0，其余顶点dist[v] = ∞（无穷大）。定义布尔数组visited[]，标记顶点是否已确定最短路径，初始时所有顶点visited[v] = false。使用优先队列（小根堆）存储待处理的顶点（以 “当前最短距离 - 顶点编号” 的形式），初始时将起点(0, start)入队。2. 贪心选择每次从优先队列中取出当前距离起点最近的顶点 u（小根堆顶元素），若u已确定最短路径（visited[u] = true），则跳过；否则标记u为已确定（visited[u] = true）。3. 松弛操作遍历顶点u的所有邻接顶点v，计算 “起点→u→v” 的路径长度（dist[u] + weight(u, v)）。若该长度小于dist[v]，则更新dist[v]为该值，并将(dist[v], v)入队（即使v已入队，重复入队不影响，后续处理时会跳过已确定的顶点）。4. 终止条件当优先队列为空时，所有顶点的最短路径均已确定，算法结束。
二、算法关键特性权值限制：
必须保证所有边的权重非负，否则松弛操作无法保证后续不会出现更短路径（负权边场景需使用贝尔曼 - 福特算法或 SPFA 算法）。时间复杂度：邻接矩阵存储图：(O(n^2))（n为顶点数），每次遍历所有未确定顶点。邻接表 + 优先队列（二叉堆）：(O((n+e)logn))（e为边数），每个顶点和边最多处理一次，堆操作耗时logn。适用场景：单源最短路径（单个起点，多终点），支持有向图和无向图（无向图可视为双向有向图）。
三、C++ 代码实现（邻接表 + 优先队列版）
- 代码框架采用邻接表存储图（空间效率更高，适合稀疏图），优先队列使用 C++ STL 的priority_queue（默认大根堆，需自定义比较规则改为小根堆）。
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
// 边的结构体：to表示邻接顶点，weight表示边的权重
struct Edge {
int to;
int weight;
Edge(int t, int w) : to(t), weight(w) {}
};
// 优先队列的元素：first为当前最短距离，second为顶点编号
typedef pair<int, int> PII;
const int MAXN = 100010; // 最大顶点数，可根据需求调整
vector<Edge> adj[MAXN]; // 邻接表
int dist[MAXN]; // 起点到各顶点的最短距离
bool visited[MAXN]; // 标记顶点是否已确定最短路径
int n, m, start; // n：顶点数，m：边数，start：起点
// 迪杰斯特拉算法核心实现
void dijkstra() {
// 初始化距离数组为无穷大
fill(dist, dist + n + 1, INT_MAX);
fill(visited, visited + n + 1, false);
dist[start] = 0;
// 优先队列（小根堆）：优先弹出距离最小的顶点
priority_queue<PII, vector<PII>, greater<PII>> pq;
pq.push({0, start});
while (!pq.empty()) {
// 取出当前距离起点最近的顶点u
auto [d, u] = pq.top();
pq.pop();
// 若u已确定最短路径，跳过
if (visited[u]) continue;
visited[u] = true;
// 遍历u的所有邻接边，执行松弛操作
for (auto& edge : adj[u]) {
int v = edge.to;
int w = edge.weight;
// 若通过u到v的路径更短，更新dist[v]
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
}
int main() {
// 输入：顶点数n，边数m，起点start
cout << "请输入顶点数、边数、起点编号：" << endl;
cin >> n >> m >> start;
// 输入m条边：u v w（表示u到v的有向边，权重为w）
cout << "请输入" << m << "条边（格式：u v w）：" << endl;
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);
}
// 执行迪杰斯特拉算法
dijkstra();
// 输出起点到各顶点的最短距离
cout << "起点" << start << "到各顶点的最短距离：" << endl;
for (int i = 1; i <= n; i++) {
if (dist[i] == INT_MAX) {
cout << "到顶点" << i << "：不可达" << endl;
} else {
cout << "到顶点" << i << "：" << dist[i] << endl;
}
}
return 0;
}
- 代码说明
数据结构：
Edge结构体：存储邻接顶点和边的权重，用于构建邻接表。
PII（pair<int, int>）：优先队列的元素类型，第一个值为当前最短距离，第二个值为顶点编号。
邻接表adj[]：adj[u]存储顶点u的所有出边。
核心函数dijkstra()：
初始化距离数组和标记数组，将起点入队。
循环取出优先队列的堆顶元素，跳过已确定的顶点，遍历邻接边执行松弛操作。
松弛操作中，若更新了顶点v的最短距离，则将新的距离和顶点入队。
主函数：
读取输入（顶点数、边数、起点，以及各条边的信息）。
调用dijkstra()算法，输出起点到所有顶点的最短距离。 - 测试用例
输入示例（有向图）：
4 5 1
1 2 2
1 3 5
2 3 1
2 4 3
3 4 2
顶点说明：顶点 1 为起点，边 1→2（权重 2）、1→3（权重 5）、2→3（权重 1）、2→4（权重 3）、3→4（权重 2）。
输出结果：
起点1到各顶点的最短距离：
到顶点1：0
到顶点2：2
到顶点3：3
到顶点4：5
结果分析：起点 1 到顶点 2 的最短距离为 2（1→2）。起点 1 到顶点 3 的最短距离为 3（1→2→3）。起点 1 到顶点 4 的最短距离为 5（1→2→4 或 1→2→3→4）。
四、常见误区与注意事项负权边问题：
迪杰斯特拉算法无法处理负权边。例如，若存在边 3→2（权重 - 5），则算法会错误地认为顶点 3 的最短距离为 5，而实际 1→3→2 的距离为 0，导致结果偏差。优先队列重复元素：优先队列中可能存在同一顶点的多个距离记录，无需额外删除旧记录，只需在取出时判断visited[u]，跳过已确定的顶点即可（重复记录不影响最终结果，仅增加少量堆操作）。顶点编号范围：代码中顶点编号从 1 开始（符合常规输入习惯），若需从 0 开始，只需调整main函数中的输入和输出循环。无穷大取值：代码中使用INT_MAX（int类型的最大值）表示无穷大，需注意路径长度溢出问题（若边权较大，可改用long long类型存储距离）。
五、扩展优化斐波那契堆优化：
理论上可将时间复杂度降至(O(nlogn + e))，但斐波那契堆实现复杂，实际工程中极少使用。双向迪杰斯特拉：同时从起点和终点出发执行贪心策略，相遇时停止，可减少堆操作次数，适合求解两点间的最短路径。处理无向图：只需在添加边时，同时添加u→v和v→u两条边（代码中注释部分）。
总结
迪杰斯特拉算法是单源最短路径问题的核心解法，其贪心策略保证了在非负权边场景下的正确性和高效性。本文通过原理讲解、C++ 代码实现和测试用例，完整呈现了算法的应用过程。掌握该算法不仅能解决图论基础问题，也能为复杂场景（如带约束的路径规划）提供思路。在实际开发中，需根据图的稀疏程度选择邻接矩阵或邻接表存储，并注意避开负权边、重复入队等常见误区。
这里空空如也
有帮助，赞一个