【模板】单源最短路径(Dijkstra算法)

题目

洛谷P4779【模板】单源最短路径(标准版)

题解

链式前向星(存边结构):与链表的结构和查找遍历方式相同,唯一的不同点就是插入的位置。链式前向星每次将新的元素插入链表头。为每一个节点建立一个链表,存入此节点的所有出边。

Dijkstra算法:这个算法要求所有边的权重都为非负值。定义d[i]为从起点到第i个节点的最短路径长度。

算法流程:假设起点为s。1.令d[s]=0 ,其它d[i]为无穷大 2.从没有被标记的节点中找出d[x]最小的节点x,然后标记x 3.枚举x的所有出边x->y(边权为w) ,若d[y]>d[x]+w,则用d[x]+w更新d[y] 4.重复2、3,直到所有节点都被标记。

算法原理:基于贪心思想。每次找到的d[x]最小的节点,不可能再被较大的d[y]更新,所以d[x]必然是s~x的最短路径。

算法优化:动态维护d[x]最小值,减少查找的时间。利用STL 优先队列(大根堆),用STL pair存d[x]和x,将d[x]转成-d[x]存入,把大根堆转化成小根堆。

代码

Subscribe
提醒
guest
1 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年8月17日 下午9:11

【小白解析】
这道题目初看非常骇人:现后有v,head,d,e四个数组和q这一个优先队列需要考虑,极易混淆。必须在解题过程中理清楚每个数组/队列的作用。

e数组
先从main函数入手:对于每一行数据,程序均做add()函数处理,实际上是与数组e相关联。e的作用非常基础:存储每个线路的目的地(to),到达其目的地的距离(w),以及上一个与它共享出发点的线路(nxt)。最后一个变量不太好下手,因而引入head数组。

head数组
head数组的本质作用是凭借每一个线路e[i]的nxt变量,储存所有同出发点的线路;head[from]表示从位置from出发的第一条线路在e中的下标,e[head[from]].nxt则表示从from出发的第二条线路下标,以此类推。可以将head数组比作一个接力棒:每一个从from出发的线路从head[from]那里接来上一个从from出发的线路下标,自己再将自己的下表传递给下一条线路;所有数据处理完后,head储存的则是一系列最后持有接力棒的线路下标。反之,第一个从from出发的线路,其nxt必然为0,为第25行的判断提供条件。

d数组
读完数据后进入di jkstra()算法。第18行为d数组每个成员附上无限大值;此处的d储存的是到每个点所需要的最短路径,d[i]表示的是从出发点s出发,至点i的最短路径。所有数据被初始化为inf是为了后续的贪心算法比较;第20行的d[s]=0表示到达出发点需要路径长度最短为0。随后第一个队列成分被压入队列q内。

q队列
q队列储存pair对象并将其自动从大到小排列;每个pair储存first和second两个变量:前者表示到达second点的最短距离的负数,后者表明目标点。
为什么是负数?若优先队列通过比较pair.first的大小,按照该值由大到小的排列方式,距离最长的点会被排在前,队列本身有没法从尾部弹出数据——这与我们所需要的的“最短路径”相悖,故取-pair.first(也就是31行的-d[y]),使其按照绝对值从小到大排列,达到需求。

v数组
目前步骤部署完毕后,可以开始最基本的遍历搜索了。21行开始,程序先获得当前队列中到达距离最短的pair,将其对应点pair.second赋值给x(第23行)——接下来的操作中,x将被当成新的出发点,进行一系列考察。第24行对于x做了一次判断,查看其是否已被考察过——基于贪心算法的过河拆桥属性,最优的x不需要验算,因而数组v被用于记录每个x是否被考察。

第25行开始有引入第二个循环,旨在从head[x]开始,通过每个e[head[x]].nxt逐一查看所有从head出发的线路:这一步中所有从x出发的线路均已考察,故不需要担心v的过度覆盖导致数据缺失;27行则将各线路的目的地赋值给y。此时开始贪心算法的精髓:判断现有的【到达y的距离d[y]】是否大于从【从s出发到x,再从x出发到y的距离d[x]+e[x].w】。若大于则将后者考虑为最优路径,取负值,随后将其目的地y一同存进新的pair对象中,推入q队列。这个循环结束后,所有从x出发的、当前的“最短路径”均被推入q中;此时回到21行,从星罗棋布的新出发点依次搜寻更多的最短路径。优先队列的本质保证了现有的最短路径最先被考察。

所有循环结束后,d数组储存的则是到达每个点的最短路径长。
*这么屑的题目背景有存在的必要吗?出题人,自裁,请。