企业官网建设流程全解析

苏州专业网站建设的公司,国际婚恋网站做翻译合法吗,h5游戏源码网,江门网站制作系统算法:Dijkstra [堆优化(优先队列)]求解:单源最短路径核心思想#xff1a;贪心,每次从未确定最短距离的节点中,选择距离源点最近的节点,用该节点更新其邻接点的距离。这是一个堆优化的Dijkstra最短路径算法实现。让我为您详细解析每个部分#xff1a;一、数据结构解析1. 邻接表…算法:Dijkstra [堆优化(优先队列)]求解:单源最短路径核心思想贪心,每次从未确定最短距离的节点中,选择距离源点最近的节点,用该节点更新其邻接点的距离。这是一个堆优化的Dijkstra最短路径算法实现。让我为您详细解析每个部分一、数据结构解析1. 邻接表存储链式前向星邻接表存储图int h[1005],e[1005],ne[1005],idx,w[1005];//邻接表存储图2. 优先队列最小堆优先队列 q 用于存储 {距离, 节点} 对greaterpairint,int 确保队列按距离从小到大排序priority_queuepairint,int,vectorpairint,int,greaterpairint,int q;3. 辅助数组bool s[1005];//标记数组记录节点是否已确定最短距离 int dis[1005];//存储源点到各节点的最短距离dis[1005]: 源点到各点的最短距离s[1005]: 标记节点是否已确定最短路径二、核心算法流程1.输入memset(h,-1,sizeof(h)); cinnm; for(int i1; im; i) { int a,b,c; cinabc; if(c0) 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 tq.top();//取出距离源点最近的节点 q.pop(); if(s[t.second]) continue;//如果该节点已确定最短距离,则跳过 s[t.second]1;//标记该节点为已确定 for(int ih[t.second]; i!-1; ine[i])//遍历该节点的所有邻接边 { if(dis[e[i]]t.firstw[i])//如果通过当前节点到达邻接节点的距离更短 { dis[e[i]]t.firstw[i];//更新距离 q.push({dis[e[i]],e[i]});//邻接节点入队 } } }4.输出if(dis[n]0x3f3f3f3f) cout-1;//如果目标节点不可达,输出-1 else coutdis[n];//输出源点到目标节点的最短距离三、关键代码详解边添加函数add()示例添加边 1→2(3)1→3(5)初始h[1] -1 添加1→2(3)e[0]2, ne[0]-1, h[1]0, idx1 添加1→3(5)e[1]3, ne[1]0, h[1]1, idx2 结果形成链表1 → 边1(1→3) → 边0(1→2) → -1四、算法特性时间复杂度普通Dijkstra: O(n²) - 适合稠密图堆优化Dijkstra: O((nm)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是源点写得好就关注点赞一下