SPFA 模版

正文索引 [隐藏]

给定一个 n 个点,m 条边的有向图,可以使用 O(nm) 的时间复杂度,求出单源点的最短路。
通常复杂度较低,在网格图等特殊情况下将被卡到复杂度的上上界。

使用方法

void SPFA::init(int n); 传入点的数量 n,初始化图
void SPFA::addEdge(int x, int y, int w); 新建一条从 x 到 y 的有向边,边权为 w
void SPFA::solve(int src, int dst); 计算从 src 出发的单源最短路,并返回 src 到 dst 的最短路。

C++代码