图论

最短路

Floyd 算法

• 时间复杂度 $O(N^3)$ 空间复杂度 $O(N^2)$
• 任意两个结点之间的最短路
• 三个 for 循环需要注意顺序

cpp for (k = 1; k <= n; k++) { for (x = 1; x <= n; x++) { for (y = 1; y <= n; y++) { f[x][y] = min(f[x][y], f[x][k] + f[k][y]); } } }

Dijkstra 算法

• 图中不能有负边
• 复杂度 $O(m \log m)$
• 优先队列维护还没有访问过的点
• 程序员的浪漫 D[i][j][k] str(a)

Bellman-Ford 算法

• 根据三角形不等式对边进行松弛操作
• 复杂度 $O(nm)$
• 针对有负边的图，会有结点被松弛成功 n 次

相关优化

• 核心：尝试使队列效率接近优先队列。大部分出题人会有意识去卡这些优化。没有负边的问题，建议使用 Dijkstra 算法。
• SPFA 通过队列记录哪些点可能需要松弛操作
• LLL 和 SLF 使用双端队列优化
• 如何卡上面这些优化方法见 如何看待 SPFA 算法已死这种说法？ - 知乎 (zhihu.com)

工业界

中国这张图大概是 1 亿条边，5 千万个点。Dijkstra 之类算法无法满足性能要求，常用算法有 CH、CCH 和 CRP。加速思路是减少搜索空间，先对图进行预处理（建立一些虚拟连接的边），然后使用双向算法进行搜索。这一类算法主要使用图的先验信息，没有考虑车辆轨迹等后验信息。

---

最后更新: 2022-11-15

评论