# 单源最短路

1. 如果有多个目标函数，问题变为 NP-Complete，可以得到一个多维空间，每条路径是其中的一个点，最终集合中每个点都在某些维度上是最优的，但是在其他维度上不一定是最优的，这样的点称为 Pareto 最优解

2. 一条边的权重可变时，问题也会比较复杂

3. 以下讨论的算法大多是集中式的，但实际应用中会有需要分布式的算法

4. Bellman-Ford 算法：$O(|V||E|)$，可以处理负权边，但不能处理负权环，可以检测负权环；易于分布式实现

5. 有向无环图中的最短路：$O(|V|+|E|)$，拓扑排序后，按拓扑序依次更新点的最短路

6. Dijkstra 算法：$O(|E|+|V|\log|V|)$，不能处理负权边