Dijkstra算法用于求解单源最短路径问题，适用于带权有向图或无向图为正权重的情况。在C++中，可以通过邻接表建图，结合优先队列（最小堆）高效实现该算法。
图的表示：邻接表
使用vector嵌套pair的方式存储图，每个节点保存其邻居和对应边的权重。
typedef pair
vector
// 添加边
void addEdge(int u, int v, int weight) {
graph[u].push_back({weight, v});
}
初始化与优先队列
从起点开始，维护一个距离数组dist[]，初始设为无穷大，起点为0。使用priority_queue模拟最小堆，按距离排序。
vector
priority_queue
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.second;
int w = edge.first;
if (dist[u] + w
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
完整示例代码
以下是一个简单调用示例：
#include
using namespace std;
void dijkstra(vector
int n = graph.size();
dist.assign(n, INT_MAX);
dist[start] = 0;
priority_queue
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.second;
int w = edge.first;
if (dist[u] + w
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
}
基本上就这些。只要图没有负权边，Dijkstra能正确计算出从起点到其余各点的最短距离。实际应用中注意节点编号范围和图的初始化
即可。
