【总结】最短路算法总结

写这篇辣鸡总结的目的

嗯我为什么会写一篇这么辣鸡的总结,主要是前几天我发现我的基础太不牢固了,连最短路都写不出来了。。。
以后要学会巩固基础,写熟基本算法。马上NOIP了,如果连这种模板都还会写错的话,大概就要退役了吧。
最短路算法,我这里想说的只有最基本的三种:Dijkstra,SPFA,Floyd。
n表示点数,m表示边数。

三种算法的基本思路和代码

松弛操作:计算到每个点时,看下相连的点能不能更新。

一、Dijkstra

说白了,就是贪心+DP
每次贪心地取当前dist最小的节点,然后进行松弛操作。堆优化:如果可以松弛,就把该点放入小根堆中,每次取堆顶的点,检查和它相连的点。
时间复杂度O(mlogn),只能处理正权边。

二、SPFA

其实就是BFS。每次访问到节点,就检查能否进行松弛操作。如果能就入队。
期望时间复杂度O(km),k为每点平均进队次数,出题人可以卡SPFA。
可以处理负权边,可以用来判断是否存在负环(一个点入队次数超过n次就存在负环)。

三、Floyd

思路就是DP,可求任意两点的最短路。代码非常简单。
时间复杂度O(n^3),常数非常小。

总结

背熟代码,理解思路,改变当前最短路的部分是松弛操作(其中Dijkstra和SPFA这部分是一样的)。
NOIP2017加油!