Floyd算法

我们知道通过BFS或者DFS可以求出两点之间的最短路径，所以进行n^2次搜索，即对每两个点都进行一次搜索，便可以求得任意两点之间的最短路径。
但懒人毕竟是懒人，有更快捷的代码何乐而不为呢？
如果要让任意两点之间的路程变短，只能引入第三个点（顶点k），并通过这个顶点k中转即i->k->j，才可能缩短原来从i点到j的路程。那么这个中转的顶点k是1~n中的哪个点呢？甚至有时候不只通过一个点，而是经过两个点或者更多点中转会更短，即i->k1->k2->j或者i->k1->k2…->kn->j。
那么我们就有了DP方程：

dist[i][j]=min(dist[i][k]+dist[k][j])

通过这种方法我们可以只用O(V3)求出任意两个点之间最短路径。
正是因为它实现起来非常容易，如果时间复杂度要求不高，使用Floyd-Warshall来求指定两点之间的最短路或者指定一个点到其余各个顶点的最短路径也是可行的,适用于点数很少的图。

//核心代码
for(k=1;k<=n;k++)   
  for(i=1;i<=n;i++)   
     for(j=1;j<=n;j++)   
       if(e[i][j]>e[i][k]+e[k][j])   
         e[i][j]=e[i][k]+e[k][j];
/*Floyd-Warshall算法不能解决带有“负权回路”（或者叫“负权环”）的图，
因为带有“负权回路”的图没有最短路。
例如下面这个图就不存在1号顶点到3号顶点的最短路径。
因为1->2->3->1->2->3->…->1->2->3这样路径中，
每绕一次1->-2>3这样的环，最短路就会减少1，永远找不到最短路。
其实如果一个图中带有“负权回路”那么这个图则没有最短路。*/

---

无权图的最短路

BFS

源点设置成0，和源点相连的设置成1，
以此类推，直到搜索结束所有点为止；
BFS能很好地解决单源最短路径的问题，
无权图中，将权值视为单位长度即可；
因为BFS本身是分层的，所以准确性是很有保障的
时间复杂度O(V+E)，很常用的的算法

//核心代码
这么简单的算法，你还让我贴代码？

Dijkstra算法

时间复杂度O(V^2)，类似Prim的想法，这么朴素的算法其实不怎么常用；

下面有能替代Dijkstra的国产算法SPFA；

请举起火把，紧张地往下看！

SPFA

队列优化的Bellman—Ford算法
1.把源点的最短值当做0，入列
2.遍历队首顶点的初值，尝试更新
3.如果某顶点的最短路径值可能会改变，将其入列
4.重复操作
时间复杂度O(kE)，上限O(VE)
k一般是一个2左右的常数，但是经常有BT的出题人喜欢借此卡你

判断负环

神奇的国产算法，记录每个点入列的次数，
当其超过总点数V的时候，就证明存在负环
注意：虽然SPFA是替代Dijkstra的，但是，请千万不要用Dijkstra判断负环！

堆优化

SPFA中直接将队列替换成单调队列，每一次取出一个最短路径估计值最小的顶点
当图中有负权边的时候，会瞬间变成指数级的时间复杂度··所以不要乱给SPFA优化