【学习笔记】单源次短路径

算法思想

通过改进dijkstra的更新逻辑来实现单源次短路径。

当我们从队首得到一个新的点$u$和$s$到$u$的距离$d$时，会有以下三种情况：

其中的$d_i$表示$s$到$i$的最短路径，$ld_i$表示$s$到$i$的次短路径。

• $dis < d_u$，可以更新最短路和次短路，那么次短路更新成原来的最短路，然后更新最短路。
• $d_i < dis < ld_i$，可以更新次短路，直接更新。
• $dis > ld_i$，都更新不了。

根据这个逻辑，我们就能够做好啦！

代码+例题