企业官网建设流程全解析

算法: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)：存储图和距离数组

限制条件

1. 不能处理负权边（会陷入死循环或得到错误结果）

2. 适用于有向图和无向图（本代码实现的是有向图）

3. 需要非负权值

五、输入输出示例

输入格式

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是源点

写得好就关注，点赞一下！