1、深度或广度优先搜索算法（解决单源最短路径）
该方法通过DFS或BFS暴力遍历获取一顶点到目标顶点的路径，一一比对各路径的权值和来获取最短路径
2、Dijkstra算法（解决单源最短路径）
最短路径问题—Dijkstra算法详解
Dijkstra（迪杰斯特拉）算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止，相对于暴力简单的Floyd算法，Dijkstra算法更为有用且时间复杂度较为合理–O(N^2)。注意该算法要求图中不存在负权边！
3、Floyd算法（解决多源最短路径）
最短路径问题—Floyd算法详解
最短路径模板+解析——（FLoyd算法）
弗洛伊德算法是解决任意两点间的最短路径的一种算法，可以正确处理有向图或有向图或负权（但不可存在总权为负的回路)的最短路径问题，同时也被用于计算有向图的传递闭包。Floyd算法的时间复杂度为O(N3)，空间复杂度为O(N2)。
4、Bellman-Ford算法（解决负权边，解决单源最短路径）
深入理解Bellman-Ford（SPFA）算法
Bellman-ford（解决负权边）
Bellman-Ford算法是从DJ算法引申出来的，它可以解决带有负权边的最短路径问题。值得注意的是，Bellman-Ford算法是基于邻接表，从边的角度考量的，ford算法只能用邻接表实现。此外，Bellman-Ford算法可以检测一个图是否含有负权回路。
5、SPFA算法
最短路径问题—SPFA算法详解
SPFA(Shortest Path Faster Algorithm)算法是求单源最短路径的一种算法，它是Bellman-ford的队列优化，它是一种十分高效的最短路算法。
很多时候，给定的图存在负权边，这时类似Dijkstra等算法便没有了用武之地，而Bellman-Ford算法的复杂度又过高，SPFA算法便派上用场了。SPFA的复杂度大约是O(kE),k是每个点的平均进队次数(一般的，k是一个常数，在稀疏图中小于2)。
但是，SPFA算法稳定性较差，在稠密图中SPFA算法时间复杂度会退化。此外，SPFA算法还可以判断图中是否有负权环，即一个点入队次数超过N。
6、总结
图的最短路径：Dijkstra、Bellman-Ford、SPFA、Floyd、A*算法
适用情况
dj和ford算法用于解决单源最短路径，而floyd算法解决多源最短路径。
dj适用稠密图（邻接矩阵），因为稠密图问题与顶点关系密切；
ford算法适用稀疏图（邻接表），因为稀疏图问题与边关系密切。
floyd在稠密图（邻接矩阵）和稀疏图（邻接表）中都可以使用；
PS：dj算法虽然一般用邻接矩阵实现，但也可以用邻接表实现，只不过比较繁琐。而ford算法只能用邻接表实现。
dj算法不能解决含有负权边的图；
而Floyd算法和Ford算法可以解决含有负权边的问题，但都要求没有总和小于0的负权环路。
SPFA算法可以解决负权边的问题，而且复杂度比Ford低。形式上，它可以看做是dj算法和BFS算法的结合。
3种算法都是既能处理无向图问题，也能处理有向图问题。因为无向图只是有向图的特例，它们只是在邻接矩阵或邻接表的初始化时有所区别。
|