Dijkstra - 单源最短路径
算法:Dijkstra [堆优化(优先队列)]
求解:单源最短路径
核心思想：贪心,每次从未确定最短距离的节点中,选择距离源点最近的节点,用该节点更新其邻接点的距离。
这是一个堆优化的Dijkstra最短路径算法实现。让我为您详细解析每个部分：
一、数据结构解析
1. 邻接表存储（链式前向星）
邻接表存储图
int h[1005],e[1005],ne[1005],idx,w[1005];//邻接表存储图2. 优先队列（最小堆）
优先队列 q 用于存储 {距离, 节点} 对
greater<pair<int,int>> 确保队列按距离从小到大排序
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;3. 辅助数组
bool s[1005];//标记数组，记录节点是否已确定最短距离 int dis[1005];//存储源点到各节点的最短距离dis[1005]: 源点到各点的最短距离s[1005]: 标记节点是否已确定最短路径
二、核心算法流程
1.输入
memset(h,-1,sizeof(h)); cin>>n>>m; for(int i=1; i<=m; i++) { int a,b,c; cin>>a>>b>>c; if(c<0) return 0; add(a,b,c); }同时，加边函数：
void add(int a,int b,int c)//邻接表的边添加函数，用于构建图的邻接表存储结构 { e[idx]=b;//终点 ne[idx]=h[a];//下一条边的索引 w[idx]=c;//边的权值 h[a]=idx++;//更新头节点的下一条边索引 }2. 初始化
memset(dis,0x3f,sizeof(dis));//初始化距离为无穷大 dis[1]=0;//源点到自身距离为0 q.push({0,1});//源点入队2. 主循环
while(!q.empty()) { auto t=q.top();//取出距离源点最近的节点 q.pop(); if(s[t.second]) continue;//如果该节点已确定最短距离,则跳过 s[t.second]=1;//标记该节点为已确定 for(int i=h[t.second]; i!=-1; i=ne[i])//遍历该节点的所有邻接边 { if(dis[e[i]]>t.first+w[i])//如果通过当前节点到达邻接节点的距离更短 { dis[e[i]]=t.first+w[i];//更新距离 q.push({dis[e[i]],e[i]});//邻接节点入队 } } }4.输出
if(dis[n]==0x3f3f3f3f) cout<<-1;//如果目标节点不可达,输出-1 else cout<<dis[n];//输出源点到目标节点的最短距离三、关键代码详解
边添加函数add()
示例：添加边 1→2(3)，1→3(5)
初始：h[1] = -1 添加1→2(3)：e[0]=2, ne[0]=-1, h[1]=0, idx=1 添加1→3(5)：e[1]=3, ne[1]=0, h[1]=1, idx=2 结果形成链表：1 → 边1(1→3) → 边0(1→2) → -1
四、算法特性
时间复杂度
普通Dijkstra: O(n²) - 适合稠密图
堆优化Dijkstra: O((n+m)log n) - 适合稀疏图（本实现）
空间复杂度
O(n + m)：存储图和距离数组
限制条件
不能处理负权边（会陷入死循环或得到错误结果）
适用于有向图和无向图（本代码实现的是有向图）
需要非负权值
五、输入输出示例
输入格式
n m a1 b1 c1 a2 b2 c2 ... am bm cm
示例
4 5 1 2 2 1 3 5 2 3 1 2 4 4 3 4 3
计算过程：
初始：dis = [0, ∞, ∞, ∞] 第1轮：节点1出队，更新dis[2]=2, dis[3]=5 第2轮：节点2出队，更新dis[3]=3, dis[4]=6 第3轮：节点3出队，更新dis[4]=6（不变） 结果：dis[4] = 6
六、算法优化点（AI所说）
1. 懒惰删除技巧
if(s[t.second]) continue; // 避免重复处理
同一个节点可能多次入队，但只处理第一次出队的情况
2. 无穷大表示
0x3f3f3f3f ≈ 1.06×10⁹
使用这个值作为无穷大，两个无穷大相加不会溢出
3. 堆优化的优势
相比普通Dijkstra的O(n²)，堆优化：
减少查找最小距离节点的时间
适合边数远小于n²的稀疏图
七、常见问题
1. 对于负权边
Dijkstra基于贪心策略，假设"当前最小距离就是最终最短距离"。负权边会破坏这个假设。
2. 对于无向图
添加边时调用两次：
add(a,b,c); add(b,a,c);3. 源点不是节点1：
只需修改初始化：
dis[source]=0; q.push({0,source}); //source是源点写得好就关注，点赞一下！