算法-最短路径总结

Posted on In

0. 图的分类

  • 有权图|无权图
    • 边权|点权
  • 有向图|无向图
  • 有环图|无环图
  • 有负权图|无负权图

1. Dijkstra 迪杰斯特拉算法

  • 单源最短路径的
  • 贪心算法
  • 每次选择当前未处理节点中距离源点最近的节点进行扩展
  • 不能处理负边

1.1 算法步骤

  1. 初始化源点到所有节点的距离为无穷大，源点到自身的距离为 0。
  2. 使用优先队列（最小堆）维护未处理节点的距离。
  3. 每次从队列中取出距离最小的节点，更新其邻接节点的距离。
  4. 重复上述步骤直到所有节点都被处理。

1.2 时间复杂度

  • 使用普通数组实现优先队列：$O(V^2)$
  • 使用二叉堆实现优先队列：$O((V + E) log V)$

2. DAG Shortest Path Algorithm 拓补最短路径

  • 单源最短路径的
  • DAG（有向无环图）的最短路径算法
  • 关键是利用拓补排序，前驱一定在后继之前被处理
  • 因此也能处理负权边，但是不能处理负环边

2.1 算法步骤

  1. 对图进行拓扑排序。
  2. 按照拓扑排序的顺序依次松弛每个节点的邻接边。

2.2 时间复杂度

  • $O(V + E)$

3. Bellman-Ford 算法

  • 单源最短路径的
  • 处理带负权边的图，并且能够检测负权环
  • 最原始的方法，尝试所有情况

3.1 算法步骤

  1. 初始化源点到所有节点的距离为无穷大，源点到自身的距离为 0。
  2. 对所有边进行 V-1 次松弛操作。
  3. 检查是否存在负权环：如果在第 V 次松弛操作中仍然可以更新距离，则存在负权环。

3.2 时间复杂度

  • $O(V * E)$

4. Floyd-Warshall 算法

  • 多源最短路径的
  • 动态规划算法
  • 三个循环，技巧性较差，比较原始

4.1 算法步骤

  1. 初始化距离矩阵，直接使用图的邻接矩阵表示。
  2. 对每个节点 k，更新所有节点对 (i, j) 的最短路径：dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])。
  3. 重复上述步骤直到所有节点都被处理。

4.2 时间复杂度

  • $O(V^3)$