最短路
题单介绍
图论里的最短路指的是一个点到另外一个点的最短距离。在边上有权值，表示这条边的长度。
最短路算法有多种，每种都有自己的优缺点，尽量全部掌握。
最短路算法一般都会有一个操作：松弛操作。具体的想法为：对于一条u到v的边，起点s到v的距离d[v]若大于d[u]+a[u][v]，那么用d[u]+a[u][v]更新d[v]的距离。其中a[u][v]为这条边的长度。
* dijkstra算法：
想法是每次找到离起点最近的点，用这个点连出来的边更新其他点的距离。直到所有点都被找过一次为止。
```
集合S=所有点
d[s]=0
d[其他点]=INF
for i=1 to n:
x=S中离s最近的点
for 所有以x为起点的边x->y:
更新d[y]
将x从S中删去
```
这种算法是一种贪心算法，因为离起点最近的点以后不会再被更新，所以当每个点都被选过之后就能算出起点到所有点的最短路。
优点：速度最快最稳定，加入堆优化后复杂度为O(m+nlogn)。（n为点的个数，m为边的个数，下同）
缺点：如果边权是负的，就会导致贪心的证明错误，也会导致算法出错。
* SPFA算法：
想法是每次把被**成功**更新过的点加入队列，每次从队列里拿出一个点，用以他为起点的边更新其他点。成功更新指的是起点到这个点的距离在这次松弛操作中变小了。
```
队列q
将起点s加入队列q
while q不为空:
取出q的队首x
for 所有以x为起点的边x->y:
if y的距离能被更新:
更新y的距离
if y不在队列q里:
将y加入队列q
```
优点：能处理负边，而且在大部分情况下速度接近O(m)
缺点：如果数据出的比较针对，复杂度会退化到O(nm)
* Bellman-Ford算法：
由于最短路径一定不会有重复点（可以自己证明），所以这条路径最多只有n-1条边。我们只要按这条路径的边的顺序依次进行松弛操作，即可得到最短距离。
我们不知道这条路径上的第i条边到底是哪一条。但可以肯定的是这条边肯定是这张图里的一条边。那就把所有边都松弛一遍，一定能松弛到这条边。
```
for n-1次:
for 每条边:
对这条边进行松弛操作
```
优点：想法简单，实现简单。能判断出是否存在负环（若存在负环，那么再松弛的时候，还能松弛成功）
缺点：慢，时间复杂度为O(nm)
* Floyd算法：
以每个点为中间点，更新其他点对之间的距离。
```
for k=1 to n:
for i=1 to n:
for j=1 to n:
if d[i][j]>d[i][k]+d[k][j]:
d[i][j]=d[i][k]+d[k][j]
```
优点：能求出所有点对之间的最短距离，实现非常简单
缺点：慢，$O(n^3)$