SPFA

队列优化版的Bellman Ford

基本没什么用的算法

SPFA (Only in China, useless)

use queue to optimize Bellman Ford

If there are negative edges
The time complexity is very hard to estimate.

SPFA

SPFA一般只用于费用流和判断负环，没有负环尽量使用SPFA。

其中判断负环的又分为几种情况。

  1. 从起点到终点的路上有负环，最短路为负无穷。
  2. 从起点可以到负环，但是一旦进入负环便无法到达终点，所以最短路存在。
  3. 存在负环，但是从起点无法到达。

其他变形

可能需要求解

  1. 最长路。把所有边取相反数即可
  2. 乘积最大。边权相乘，可以通过取对数转化为加法。

参考题目

Luogu P3371
最短路模板

Luogu P4779
最短路模板

Luogu P1821
正反两次最短路

Luogu P2419
传递闭包

参考资料

Dijkstra's algorithm

SPFA

≡