简介：
Dijkstra算法是解决单源最短路径问题的经典算法，由Edsger W. Dijkstra于1956年提出。 它采用贪心策略，逐步扩展已知最短路径集合，适用于非负权重的加权图。 算法通过初始化距离数组、优先队列和已处理顶点集合，迭代更新邻接顶点的最短距离。 时间复杂度取决于优先队列的实现方式：从O (V²)到O (E+VlogV)。 需要注意的是，该算法不能处理负权边。
更多请前往：https://baike.baidu.com/item/%E8%BF%AA%E5%85%8B%E6%96%AF%E7%89%B9%E6%8B%89%E7%AE%97%E6%B3%95/23665989
算法核心思想：
Dijkstra算法的核心思想
Dijkstra算法通过维护一个优先队列来存储待处理的节点及其当前到源点的最短距离估计值。每次从队列中取出距离最小的节点，对其邻接节点进行松弛操作。松弛操作是指如果通过当前节点到达邻接节点的路径比已知路径更短，则更新邻接节点的距离值。
贪心选择与松弛操作
算法维护一个优先队列（或最小堆），用于存储待处理的节点及其当前到源点的最短距离估计值。每次从队列中取出距离最小的节点，对其邻接节点进行松弛操作：若通过当前节点到达邻接节点的路径更短，则更新邻接节点的距离值。
松弛操作的数学表达为： [ \\text{dist}[v] = \\min(\\text{dist}[v], \\text{dist}[u] + w(u, v)) ] 其中 ( u ) 是当前节点，( v ) 是邻接节点，( w(u, v) ) 是边的权重。
动态维护最短路径
算法通过动态维护一个距离数组 dist[]，记录源点到各节点的最短距离。初始时，源点的距离设为0，其他节点设为无穷大。每次处理节点后，其最短距离即被确定，后续不再更新。
无负权边的必要性
Dijkstra算法要求图中无负权边，否则已确定的节点可能因后续松弛操作被重新更新，破坏贪心策略的正确性。对于含负权边的图，应采用Bellman-Ford算法。
专项题单：
【迪杰斯塔拉】Dijkstra – 题单 – 洛谷 | 计算机科学教育新生态
例题分析：
题目：P4779 【模板】单源最短路径（标准版） – 洛谷
题目代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct node{
int x,dis;
friend bool operator<(node n1, node n2){
return n1.dis > n2.dis;
}
};
priority_queue<node> pq;
vector<pair<int, int>> g[100005];
int dis[100005];
bool vis[100005];
int n, m, s;
void dijkstra(){
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
dis[s] = 0;
pq.push({s,0});
while (!pq.empty()){
int u = pq.top().x;
pq.pop();
if(vis[u]) continue;
vis[u] = true;
for(int i=0;i<g[u].size();i++){
int y = g[u][i].first;
int z = g[u][i].second;
if(dis[y] > dis[u] + z){
dis[y] = dis[u] + z;
pq.push({y, dis[y]}); // qp → pq
}
}
}
}
int main(){
cin>>n>>m>>s;
for (int i=0;i<m;i++){
int u,v,w;
cin>>u>>v>>w;
g[u].emplace_back(v, w);
}
dijkstra();
for (int i = 1; i <= n; i++) {
if (dis[i] == 0x3f3f3f3f) cout << -1 << " ";
else cout << dis[i] << " ";
}
cout << endl;
return 0;
}
本题思路：
代码结构：
- 结构体node: 包含两个字段x（节点编号）和dis（当前距离），并重载了<运算符以实现小顶堆（优先队列按dis升序排列）。
- 邻接表g: 使用vector<pair<int, int>>数组存储图的边结构，g[u]保存节点u的所有邻接节点及对应边权。
- 距离数组dis: 记录从起点s到各节点的当前最短距离，初始值为极大值（0x3f3f3f3f）。
- 访问标记vis: 标记节点是否已确定最短路径，避免重复处理。
执行步骤：
- 松弛操作：若通过u到y的路径比已知距离更短，则更新dis[y]并将y加入队列。
需注意细节：
- 优先队列优化: 使用小顶堆快速获取当前未处理节点中距离最小的节点，时间复杂度为O(m log n)。
- 重复处理判断: 通过vis数组避免同一节点多次出队，确保每个节点只被处理一次。
- 无穷大表示: 0x3f3f3f3f是一个较大的数，用于模拟无穷大且避免运算溢出。
复杂度分析：
- 时间复杂度: O(m log n)，其中m为边数，n为节点数。主要开销来自优先队列的插入和提取操作。
- 空间复杂度: O(n + m)，用于存储图结构和辅助数组。
代码总结：
该代码实现了 Dijkstra 算法，用于求解单源最短路径问题。给定一个有向加权图和起点，计算从起点到所有其他顶点的最短路径，本代码优化了传统Dijkstra，使用优先队列，可将时间复杂度优化至O((V+E)logV)。
算法拓展：
多目标扩展
可修改算法以支持多目标查询。在优先队列实现中，当所有目标节点都被访问时即可提前终止，避免计算全图的最短路径。
动态图处理
对于边权动态变化的图，可采用如下策略：
- 增量更新：当边权减小时，重新将受影响节点加入优先队列
- 完全重计算：当边权频繁变化时，建议使用更适应动态图的算法如A*
双向Dijkstra
从起点和终点同时执行Dijkstra搜索，当两边的搜索区域相遇时终止。这种优化平均可减少50%的搜索空间，尤其适用于大规模图的最短路径查询。
应用场景扩展
- 路径规划：结合A*算法启发式函数用于导航系统
- 网络路由：OSPF协议基于Dijkstra计算最优路径
- 社交网络：分析节点间的最短关系链
- 游戏AI：寻路算法的基础组件
算法局限性
- 负权边：不能处理含负权边的图（需使用Bellman-Ford）
- 稠密图：当E≈V²时优先队列优化效果有限
- 动态图：频繁边权变化时效率较低
变种算法
- A*算法：带启发式函数的Dijkstra改进
- 跳点搜索：基于Dijkstra的栅格路径优化
- 收缩层次：预处理加速大规模图查询
算法总结：
Dijkstra算法是一种解决单源最短路径问题的经典算法，由荷兰计算机科学家Edsger W. Dijkstra于1956年提出。它适用于带权有向图或无向图，且权重必须为非负数。算法的核心思想是通过贪心策略逐步扩展最短路径树，最终得到从源点到所有其他顶点的最短路径。
