Dijkstra算法用于求解非负权图的单源最短路径，通过优先队列优化实现。1. 使用邻接表存储图，小根堆按距离排序选取最近节点。2. 维护dist数组记录起点到各点最短距离，初始化为无穷大，源点为0。3. 每次取出堆顶节点进行松弛操作，若经当前节点到邻居更近，则更新距离并入堆。4. 忽略已处理的过时节点，避免重复计算。5. 最终输出从源点到其余各点的最短距离。代码以C++实现，时间复杂度O((V+E)logV)，适用于稀疏图。
Dijkstra算法是解决单源最短路径问题的经典方法，适用于带权有向图或无向图，且所有边的权重必须为非负值。在C++中实现该算法，通常结合优先队列（堆）优化来提升效率。下面详细介绍如何用C++实现Dijkstra算法。
基本思路
Dijkstra算法通过贪心策略逐步确定从源点到其他各顶点的最短距离。核心思想是：
- 维护一个距离数组，记录起点到每个顶点的当前最短距离。
- 使用优先队列选择当前距离最小的未处理节点进行扩展。
- 对当前节点的所有邻接边进行松弛操作：如果通过当前节点到达邻居的距离更短，则更新距离。
数据结构设计
为了高效实现，常用以下结构：
- vector<vector<pair<int, int>>>：邻接表存储图，pair中第一个元素是邻居节点，第二个是边权。
- priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>：小根堆，按距离排序，每次取出距离最小的节点。
- vector<int>：dist数组，初始化为无穷大，源点为0。
代码实现
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
void dijkstra(vector<vector<pair<int, int>>>& graph, int start) {
int n = graph.size();
vector<int> dist(n, INT_MAX);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
dist[start] = 0;
pq.push({0, start});
while (!pq.empty()) {
int u = pq.top().second;
int d = pq.top().first;
pq.pop();
if (d > dist[u]) continue; // 跳过过时节点
for (auto& edge : graph[u]) {
int v = edge.first;
int w = edge.second;
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
// 输出结果
for (int i = 0; i < n; ++i) {
cout << "Distance from " << start << " to " << i << " is " << dist[i] << endl;
}
}
int main() {
int n = 5; // 节点数
vector<vector<pair<int, int>>> graph(n);
// 添加边：u -> v，权重w
graph[0].push_back({1, 10});
graph[0].push_back({3, 5});
graph[1].push_back({2, 1});
graph[1].push_back({3, 2});
graph[2].push_back({4, 4});
graph[3].push_back({1, 3});
graph[3].push_back({2, 9});
graph[3].push_back({4, 2});
graph[4].push_back({0, 7});
graph[4].push_back({2, 6});
dijkstra(graph, 0);
return 0;
}
注意事项与优化
实际使用中需要注意几点：
立即学习“C++免费学习笔记（深入）”；
- 确保图中没有负权边，否则应使用Bellman-Ford算法。
- 优先队列可能包含重复节点，需判断当前弹出的距离是否已过时。
- 若需要输出路径，可额外维护一个parent数组，在松弛时记录前驱节点。
- 稀疏图适合邻接表+堆优化，时间复杂度约为O((V+E)logV)。
