最短路径树

以一个节点为根，根节点到其他所有点的距离最短，从而形成了一棵树。

也可以理解为给有环形效应的图分配拓扑序从而建立拓扑图的算法

最短路 条数

边权为 1（BFS）

因为对其任意一条最短路径都不会存在环形效应（都为正权），将此图抽象为拓扑图， 对于属于最短路路径的点

将起点 看作 根，每个点的 后驱 看作 其叶子节点，用有向边连接。

求条数时情况有二。

1、有更小路径到达

即其前驱加 $1$ 大于原值，此时已知可到达此点的边必然经过其前驱，所以最短路条数 $=$ 到达其前驱的最短路条数

2、多条相等路径

将所有等值前驱的最短路条数相加即可。

边权为正数（Dijkstra）

因为 $Dijkstra$ 算法中每一个点只出队一次，且必为最短路径，可以直接加入最短路树

同样可以将原图的所有最短路径抽象成一个拓扑图。

求条数时情况有二。

1、有更小路径到达

即其前驱加 $w[i]$ 大于原值，此时已知可到达此点的边必然经过其前驱，所以最短路条数 $=$ 到达其前驱的最短路条数

2、多条相等路径

将所有等值前驱的最短路条数相加即可。

注意事项：

例题中除了邻接矩阵要保存边权外，邻接表也要保存。因为邻接矩阵保留的是最小边，但在最小边出现之前邻接表保存的边的边权可能 更大， 不能直接用最短边的边权，避免计入最短路径。

k 短路 条数

这里的 $k$ 短路是一个广义概念，指小于 最短路径长度 且 符合题目要求的 路径。

次短路（Dijkstra）

第 $k$ 短路

在 $Dijkstra$ 的贪心迭代中，通常都会取 长度最短 的路径，但这个路径很可能不是最优解。

从而浪费了时间，但这也给了我们一点启发，如果有题目要求你要跑 同一条路径 很多次。

就可以通过 $A*$ 算法，先预处理个反向 $Dijkstra$，来快速找出全局最优解。

差值短路

我们需要用 逆向思维 解决这一类问题，

将长度不超过 $d+K$ 的路线，转化为从某点出发，可以消耗 $K$ 个单位的冗余长度，最终到达 $n$ 。

枚举所有冗余，并用记忆化搜索解决。