算法导论—路径算法总结

图算法

单源最短路径

Bellman-Ford算法：

• 顶点为V，边为E的图
  1. 对每条边松弛|V|-1次
  2. 边权可以为负值
  3. 若存在一个可以从源结点到达的权值为负值的环路，算法返回False
  4. 时间复杂度：O(VE)

有向无环图单源最短路径

• DAG-SHORTEST-PATHS
  1. 算法首先对有向无环图进行拓扑排序
  2. 即使存在权值为负的边，也因为没有权值为负的环路，最短路径是存在的
  3. 时间复杂度：O(V+E)对于邻接表表示的图，这个时间为线性级

Dijkstra算法

• 顶点为V，边为E的图
  1. 对每条边仅松弛1次
  2. 边权不可为负
  3. 运行过程维护一组结点集合S
  4. 使用贪心策略，每次选择集合V-S中最“近”的结点加入集合S
  5. 利用结点编号维持最小优先队列,时间复杂度为：O(V²+E)=O(V²)
     • 如果是稀疏图，可以利用二叉堆实现最小优先队列，时间复杂度:O(ElgV)
     • 利用斐波那契堆实现最小优先队列，时间复杂度：O(VlgV+E)

所有结点对的最短路径问题

Floyd-Warshall算法

• 顶点为V，边为E的图
  1. 使用动态规划公式解决所有结点对最短路径问题
  2. 时间复杂度：O(V³)
  3. 可以有负权值的边，但不可以有负权值环路

Johnson算法

• 用于稀疏图

1. 要么返回一个包含所有结点对的最短路径权重的矩阵，要么报告输入图包含一个权重为负值的环路
2. 通过重新赋值来生成非负权重
3. 时间复杂度：斐波那契堆：O(V²lgV+VE)，二叉最小堆：O(VElgV)
4. 运行中需要使用Dijkstra算法和Bellman-Ford算法作为自己的子程序