使用邻接表和优先队列实现Dijkstra算法，从源点出发，每次选取距离最短的未访问节点进行松弛，更新邻居距离，直至处理所有节点，得到单源最短路径。
在C++中实现Dijkstra最短路径算法，通常结合图论中的邻接表结构和优先队列来高效处理。该算法适用于带权有向或无向图，且权重非负的情况，能求出从一个源点到其他所有顶点的最短距离。
邻接表存储图结构
使用vector嵌套pair的方式构建邻接表，每个顶点保存其相邻顶点及对应边的权重。
typedef pair pii; // {距离, 目标节点}
vector> graph; // graph[u] 包含所有从u出发的边
添加边的操作如下：
void addEdge(int u, int v, int weight) {
graph[u].push_back({weight, v});
}
使用优先队列优化Dijkstra
Dijkstra的核心是贪心策略：每次取出当前距离最小的未访问节点进行松弛操作。使用priority_queue（最小堆）可以快速获取最小距离节点。
AMiner
AMiner——新一代智能型科技情报挖掘与服务系统，能够为你提供查找论文、理解论文、分析论文、写作论文四位一体一站式服务。
下载
立即学习“C++免费学习笔记（深入）”；
const int INF = 1e9;
vector dist;
priority_queue, greater> pq; // 小根堆 {距离, 节点}
void dijkstra(int start) {
dist.assign(graph.size(), INF);
dist[start] = 0;
pq.push({0, start});
while (!pq.empty()) {
int d = pq.top().first;
int u = pq.top().second;
pq.pop();
// 如果已找到更短路径，跳过
if (d > dist[u]) continue;
for (auto& edge : graph[u]) {
int w = edge.first;
int v = edge.second;
if (dist[u] + w 完整示例与输出结果
以下是一个完整的可运行示例：
#include
#include
#include
#include
using namespace std;
typedef pair pii;
vector> graph;
vector dist;
void addEdge(int u, int v, int w) {
graph[u].push_back({w, v});
}
void dijkstra(int start) {
dist.assign(graph.size(), INT_MAX);
priority_queue, greater> pq;
dist[start] = 0;
pq.push({0, start});
while (!pq.empty()) {
int d = pq.top().first;
int u = pq.top().second;
pq.pop();
if (d != dist[u]) continue;
for (auto& edge : graph[u]) {
int w = edge.first;
int v = edge.second;
if (dist[u] + w 输出结果为：
从0到0的最短距离: 0
从0到1的最短距离: 3
从0到2的最短距离: 1
从0到3的最短距离: 4
从0到4的最短距离: 7
基本上就这些。邻接表节省空间，优先队列提升效率，整体时间复杂度约为O((V+E)logV)，适合稀疏图使用。
