跳转至

图论

最短路#

Floyd 算法#

  • 时间复杂度 O(N^3) 空间复杂度 O(N^2)
  • 任意两个结点之间的最短路
  • 三个 for 循环需要注意顺序
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 通过队列记录哪些点可能需要松弛操作
  • LLLSLF 使用双端队列优化
  • 如何卡上面这些优化方法见 如何看待 SPFA 算法已死这种说法? - 知乎 (zhihu.com)

工业界#

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


最后更新: 2021-11-10

评论