SPFA 学习笔记 2024-6-02 10:48 | 162| 0| 算法| 2024-6-02 10:48 | ztrztr 327 字| 4 分钟 SPFA学习笔记 SPFA,他死了!——某次 noi T1 的出题人。 感觉和 DIJ 很像。 使用范围:负边权,判断负环,随机图 不适用于构造图。容易超时。 思路: 对于出发的点,向所有可以到达,并且没到达过的点的边都进行松弛(见 图论——dijkstra),将松弛的点入队,注意是队列不是优先队列。 继续重复上面的操作,直到队列为空。 #incl… OI最短路算法