Dijkstra算法用于求解单源最短路径问题，适用于非负权有向或无向图。采用邻接表存储图，结合最小堆优化优先队列，从起点开始逐步松弛各节点距离，最终得到到所有节点的最短路径。
Dijkstra算法用于求解单源最短路径问题，适用于带权有向图或无向图（权重非负）。在C++中，可以通过邻接表结合优先队列（最小堆）高效实现该算法。以下是具体实现方法。
1. 数据结构选择
使用以下结构存储图和距离信息：
- 邻接表：用vector<vector<pair<int, int>>>表示，每个节点保存其邻居及边权。
- 距离数组：用vector<int>记录起点到各点的最短距离，初始设为无穷大。
- 优先队列：用priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>实现最小堆，按距离排序。
2. 算法步骤
核心流程如下：
- 初始化起点距离为0，其余为无穷大，将起点加入优先队列。
- 取出当前距离最小的未处理节点。
- 遍历其所有邻接边，尝试通过该节点更新邻居的距离（松弛操作）。
- 若找到更短路径，则更新距离并将新状态入队。
- 重复直到队列为空。
3. 完整C++代码示例
以下是一个可运行的Dijkstra实现：
立即学习“C++免费学习笔记（深入）”；
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
void dijkstra(vector<vector<pair<int, int>>>& adj, int start) {
int n = adj.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 : adj[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>>> adj(n);
// 添加边：u -> v，权重w
adj[0].push_back({1, 10});
adj[0].push_back({4, 5});
adj[1].push_back({2, 1});
adj[1].push_back({4, 2});
adj[2].push_back({3, 4});
adj[3].push_back({0, 7});
adj[4].push_back({1, 3});
adj[4].push_back({2, 9});
adj[4].push_back({3, 2});
dijkstra(adj, 0);
return 0;
}
4. 注意事项与优化
实际使用中需注意：
- 确保图中无负权边，否则应使用Bellman-Ford算法。
- 优先队列可能包含重复节点，通过检查if (d > dist[u]) continue;跳过无效项。
- 若需记录路径，可增加parent[]数组，在松弛时更新前驱节点。
