最短路概述

单源最短路

一到其他
不存在负权边
1. 朴素[[Dijkstra]]算法
  1. 时间复杂度O(n^2)
  2. 稠密图使用
2. 堆优化版Djikstra算法
  1. 时间复杂度O(mlogn)
  2. 稀疏图使用(m一般为n^2量级)
存在负权边
1. [[Bellman-Ford]]
  1. O(nm)
  2. 如对经过边数有限制，则只能用bellman
2. [[SPFA]]（优化版bellman）
  1. O(m)一般情况
  2. 最坏O(nm)
松弛操作
过程：
1. 测试是否可以对从\(s\)到\(v\)的最短路径进行改善
2. 测试方法：
  1. 将从节点\(s\)到节点\(u\)之间的最短路径距离加上节点\(u\)到节点\(v\)之间的边权重，并于当前的\(s\)到\(v\)的最短路径进行比较，如果更小则进行更新
松弛时唯一导致最短路径估计和前驱节点发生变化的操作，
算法之间的不同之处是对每一条边进行松弛的次数和松弛边的次序有所不同
1. Dijkstra:对每一条边仅松弛一次
2. Bellman-Ford:对每条边都松弛\(\lvert V \rvert - 1\) 次
最短路的性质：两个节点之间的一条最短路径包含着其他最短路径