现在所学的图这一章有关找最短路径类（这个最短路径很多时候并不只是单纯指距离，根据现在刷的题来看，它可以统称为代价最小的路径）的问题，已有几种算法
宽度优先遍历 BFS
Dijkstra 算法
分层图最短路径算法
A*
Floyd
Bellman-Ford+SPFA 算法（单纯的 Bellman-Ford 意义不大，所以我们这里只看其优化的 Bellman-Ford+SPFA 算法）
现在我们总结对比下这几种算法所能应用的寻找最短路径的场景
宽度优先遍历 BFS
其中的点，就是单纯的坐标点，不考虑额外的状态
适用于图中边的权重都相同的单源最短路径寻找
适用于图中边的权重都相同的多源最短路径的寻找
其变种 01 BF 适用于图中边的权重只有 0 和 1 的最短路径寻找
Dijkstra 算法
其中点就是坐标点，不考虑额外的状态
适用于给定一个源点，求解从源点到每个点的最短路径长度。单源最短路径算法
适用于有向图、边的权值没有负数，且边的权值不相同的最短路径寻找
有普通堆版本和反向索引堆优化两个版本的模版写法
分层图最短路径
其中的点不再是坐标点，更多是到达某一个坐标点及其当前的状态组合为一个点，比如（x, y, status 1）,（x, y, status 2）虽然坐标值 x, y 相同，但是状态不一样，所以这是两个不同的点
适用于寻找最短路径时需要考虑当前状态进行扩散的问题，但是当确定状态后，对于后续寻找的过程是基本是使用 BFS/Dijkstra 进行寻找的
A* 算法
其点的含义基本上与 BFS/Dijkstra 一样
指定源点，指定目标点，求源点到达目标点的最短距离
但是增加了当前点到终点的预估函数，其余与 Dijkstra 算法相同
Floyd 算法
适用于任何图，不管有向无向、不管边权正负、但是不能有负环（保证最短路存在）
复杂度极高，适用于小规模数据
Bellman-Ford+SPFA 算法
解决有负边（没有负环）的图的单源最短路径问题
其它几个算法不能判断图中是否有负环，但是这个算法可以判定
可以判断从某个点出发是否能遇到负环，如果想判断整张有向图有没有负环，需要设置虚拟源点
复杂度高，适用于小规模数据