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[]数组，在松弛时更新前驱节点。
基本上就这些，不复杂但容易忽略细节。