SPFA: Shortest Path Faster Algorithm
- 看到名字不禁为之一颤,SPFA算法是西南交通大学段凡丁于1994年发表的。
- SPFA 也是竞赛中最常见的算法之一,不仅仅用来解决带负权的单源最短路
而且是求解差分约束问题的专用算法,也常用它和最大流合作解决最小费问题
SPFA 算法的最坏复杂度为 O(2*E)。。
SPFA 和dijkstra 格式很接近,只是加了个队列或栈就变得无比神奇了。
这里用邻接表形式写下spfa 的模板
后面再介绍它的其它功能,这里只知道它处理最短路很快即可