在C++图论开发中，Dijkstra最短路径算法是求解带权有向图或无向图单源最短路的经典方案。当图的规模达到数万节点时，使用二维数组保存所有点之间距离的邻接矩阵会消耗过量内存，此时用邻接表描述图结构就成为更合理的选择。邻接表只记录真实存在的边，能显著降低空间占用，也为后续的堆优化提供了便利。
一、邻接表的设计与表示
邻接表的核心思路是为每一个顶点维护一个边集合，集合里存放从该顶点出发能够到达的邻居以及对应的边权。在C++中，最直观的做法是利用标准库里的动态数组：定义一个结构体保存目标点和权重，再用vector数组把每个点的出边链起来。这种方式书写简单，且能借助容器自动管理内存。
另一种常见写法是链式前向星，它通过数组模拟链表，用head、to、next、w四个数组表达边的关系，在竞赛场景中能减少动态分配开销。不过对于普通工程代码，vector版邻接表可读性更好，也更容易调试。下面给出结构体配合vector的定义示例。
#include <vector>
using namespace std;
struct Edge {
int to; // 到达的邻居节点编号
int weight; // 边的权重
Edge(int t, int w) : to(t), weight(w) {}
};
// 邻接表：每个节点对应一个Edge动态数组
vector<Edge> adj[100005];
// 添加一条从u到v、权值为w的有向边
void addEdge(int u, int v, int w) {
adj[u].push_back(Edge(v, w));
}
上述代码里，adj[u]就是节点u的邻接表，所有从u出发的边都顺序存放在里面。如果是无向图，调用addEdge时只需再反向添加一次即可。这种表示法在稀疏图（边数远小于顶点数平方）中非常高效，空间复杂度仅为O(V+E)。
二、朴素Dijkstra与堆优化原理
最基础的Dijkstra算法维护一个距离数组dist，每次从尚未确定最短路的顶点里挑出距离最小的那个，再利用它去松弛相邻顶点。朴素实现需要扫一遍所有点找最小值，整体复杂度为O(V^2)，在稠密图还尚可，遇到十万级顶点就难以承受。
堆优化版本把“找最小距离顶点”的过程交给优先队列（通常用小根堆）。每次从堆顶取出当前最近的点，对其邻接边执行松弛：若经过当前点到达邻居的距离更短，就更新dist并把这个新距离压入堆中。因为堆的插入和取最小都是O(logN)，总复杂度降为O(ElogV)。要注意C++的priority_queue默认是大根堆，必须配合greater或自定义比较器变成小根堆。
#include <queue>
#include <vector>
#include <climits>
// 小根堆元素：first为距离，second为节点编号
typedef pair<int, int> PII;
// 假设节点编号从1开始，n为总点数，s为起点
void dijkstra(int s, int n) {
vector<int> dist(n + 1, INT_MAX);
priority_queue<PII, vector<PII>, greater<PII>> pq;
dist[s] = 0;
pq.push({0, s});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue; // 堆里旧的较大距离，直接跳过
for (auto &e : adj[u]) {
int v = e.to;
int w = e.weight;
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
}
代码中的if (d > dist[u]) continue;非常关键。由于一个节点可能被多次松弛并多次入堆，堆里会存在同一节点的多个距离记录，只有第一次弹出的最小记录是有效的，其余更大的都是过期数据，必须丢弃，否则会重复松弛导致错误甚至死循环。
三、完整可运行示例
下面给出一个完整的C++程序，从标准输入读取顶点数、边数和起点，构造邻接表后跑堆优化Dijkstra，并输出起点到各点的最短距离。这个例子把前面讲的结构体、加边函数和算法主体组合在一起，方便直接编译测试。
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
struct Edge {
int to;
int weight;
Edge(int t, int w) : to(t), weight(w) {}
};
vector<Edge> adj[100005];
void addEdge(int u, int v, int w) {
adj[u].push_back(Edge(v, w));
}
void dijkstra(int s, int n) {
vector<int> dist(n + 1, INT_MAX);
priority_queue<pair<int, int>,
vector<pair<int, int>>,
greater<pair<int, int>>> pq;
dist[s] = 0;
pq.push({0, s});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue;
for (auto &e : adj[u]) {
int v = e.to;
int w = e.weight;
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
for (int i = 1; i <= n; i++) {
if (dist[i] == INT_MAX)
cout << "INF ";
else
cout << dist[i] << " ";
}
cout << endl;
}
int main() {
int n, m, s;
cin >> n >> m >> s;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
addEdge(u, v, w);
}
dijkstra(s, n);
return 0;
}
在编译运行这段程序时，输入格式应为：第一行是节点数n、边数m、起点s；接下来m行每行三个整数u、v、w表示一条有向边。程序最后打印从s到1到n每个点的最短距离，不可达则输出INF。通过调换addEdge的调用方式，也能轻松改为无向图测试。
四、常见误区与工程建议
不少人在写堆优化Dijkstra时会漏掉“跳过过期堆元素”的判断，结果算法看似能跑，却在带环或重复边较多的图上算出偏大距离。另外，如果图中含有负权边，Dijkstra不再适用，应改用SPFA或Bellman-Ford，这一点在选型时必须确认。
在工程落地时，若节点规模极大且边权可能为浮点数，可以把dist换成double类型，并把pair里的距离也相应调整。对于超大规模图，还可以用斐波那契堆进一步降低理论复杂度，但C++标准库未直接提供，通常优先队列已能满足绝大部分业务场景。