最短路径算法总结

单源最短路径又分为单源单汇与单源多汇问题，它们的复杂度几乎相同那么只考虑单源多汇问题。

本文递交已结束。

Dijkstra算法是一种基于贪心的最短路径算法，通过堆优化后可以实现 $\Theta(m\log n)$ 的复杂度。其算法实现流程如下：首先从起点出发，更新与起点相连所有点的dist 值为起点到该点的距离，再选定全局中dist 值最小的点重复上述过程，等到所有点都被作为起点拓展过一遍时算法结束。特别的该算法无法解决存在负边权的图的最短路问题。

该算法的证明也是显然的。

证明：对于上面的这一张图,若设定1 为起点，首先会将3、5、6节点更新，此时全局最小则为6号节点，可以证明在不存在负边权的情况下，起点到6 的最短路径一定是从1 到6，这是因为任何其他到达6 的路径都需要经过非1到6这条边，那么到达6 时的距离一定会大于直接从1到6。同理从6 再更新时也是如此。更严谨的来说是，全局最小的dist值的点的最短路径是确定的，再利用该已确定最短路径的点进行拓展一定可确定另一个或在此之前的已确定的比通过该最小点拓展更小的点为下一次的出发点，该出发点的最短路径也是确定了的。

SPFA是对Bellman-Ford算法的队列优化版本，其复杂度为 $\Theta(km)$ ，在段凡丁论文中提出 $k$ 是一个极小的常数是错误的，该算法的最坏复杂度为 $\Theta(nm)$ ，不如Dijkstra算法稳定，但对于一般的图而言（例如USACO热浪），SPFA效率是Dijkstra 的许多倍。其算法思路类似于Bellman-Ford算法，记录通过几次中转到达某地的最优情况，思路类似于BFS。队列优化后的代码非常好写。

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。