比较详细的解释请见：【转】彻底弄懂最短路径问题（图论）
前言：我先写一些总结性的话——
1.推荐使用优先队列优化后的Dijkstra算法，速度最快；
2.出现负边和判断负环都用Bellman-Ford算法（也就是SPFA算法）；
3.Floyd算法本质是DP或贪心思想，枚举出了所有路径的情况，一些“合法性”“可到达性”的题目可以用它。
1.Dijkstra算法
2.Bellman-Ford算法
3.SPFA算法
4.Floyd算法
原文：http://www.cnblogs.com/konjak/p/6031912.html