笔记汇总

$Dijkstra$ 是一个以 贪心 为核心思想的图论算法，每次都找一个距上一个点最近的点

主要通过 维护局部最优值 的方式来维护图上携带的信息。

通常需要一个标记数组，标记其堆弹出过的节点为最优，之后不再加入堆中。

此算法通常复杂度为 $O(mlogm)$，但可用 斐波那契堆 优化为 $O(nlogn + m)$.

作为比赛上最常用的最短路算法，$Dijkstra$ 的局限性非常之大，比如说：

它不能跑 负权边，因为 $Dijkstra$ 基于贪心，但如果存在负权，贪心解在之后可能会劣于其它解。

例如，对于同起点、终点的两条路径，有权值 $c < a$ 且 $a + b < c$，如果用 $Dijkstra$ 就会直接排除 $a + b$，而选 $c$ 了。

正因如此，故它只能传递 加法、乘法$(>= 1)$ 类信息。

但是，它有一项其它最短路算法难以替代的功能，它可以求 最短路方案数

启发式优化

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

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

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