最短路径总结

求最短路径的方法有很多种，要根据情况采用不同的方法。

单元最短路：（附带基础题目）（e为图中的边数）

Dijkstra算法：利用贪婪,解决无负权边的带权有向图或无向图的单源最短路问题，O(n^2)http://blog.csdn.net/deepseazbw/article/details/77076300

算法讲解https://blog.csdn.net/mu399/article/details/50903876

Bellman_Ford: 利用松弛操作，解决含负权边的带权有向图的单源最短路问题（必须无负权回路），邻接表浏览完所有的边 O（e），邻接矩阵浏览完所有的边，O(n^2)，但在算法执行过程中，我们可以对他进行改进，如果所有点到源点的最短路径都没有发生变化则可以终止循环http://blog.csdn.net/deepseazbw/article/details/76919070

SPFA：基于Bellman_Ford算法的优化，使用队列动态更新dist[],O(e)http://blog.csdn.net/deepseazbw/article/details/76919070

Dijkstra+堆：Dijkstra的堆优化算法（多数用优先队列实现）,O(elog(n))http://blog.csdn.net/deepseazbw/article/details/76907331

任意点对最短路：

FLOYD算法,求每一对顶点之间的最短路径，有向图，无向图均可，也可以有负权边

http://blog.csdn.net/deepseazbw/article/details/79571710

转载自：https://blog.csdn.net/deepseazbw/article/details/77140625