最短路

Floyd算法
适用情况：
       求任意两点间的最短路，不能处理负权回路（负权环)，可处理负权边。
时间复杂度：O(N^3)
算法思想：
       如果要两点a,b间的路程变短，就需要引入新的顶点k1，k2,……kn，使a—>k1—>k2—>……—>kn—>b更短。即对a和b之间所有的其他点进行松弛。
       DP：状态状态转移方程：d[k][i][j] = min(d[k-1][i][j], d[k-1][i][k]+d[k-1][k][j])
           利用滚动数组优化：a[i][j]=min(a[i][j],a[i][k]+a[k][j])【动态规划：0/1背包问题】
           相关文章：https://blog.csdn.net/qq_40507857/article/details/80657007
核心代码：
for(int k = 1; k <=n; k++)
    for(int i = 1; i <=n; i++)
        for(int j = 1; j <=n; j++)
            a[i][j]=min(a[i][j],a[i][k]+a[k][j])；
  

Dijkstra算法
适用情况：
       求从一个顶点到其余各顶点的最短路径算法，不能处理负权边。
时间复杂度：O(N^2)
            利用堆优化；在边数M少于N^2的稀疏图来说，可以用邻接表代替邻接矩阵。可优化为O((M+N)logN)。
算法思想：
       类似BFS+贪心。通过边来松弛1号顶点到其余各点的距离。选择离起点最近的一个点，扩散出去。
       选择距离1号顶点最近的一个顶点作为确定的长度（因为边权值非负，所以距离1号顶点距离最短即意味着不可能通过其他的点中转来缩短距离。
       然后讨论从已选的点i到其他点j的距离是否能够更短，即dis[j]=min(dis[j],dis[i]+a[i][j])。
       如果book数组的值全为1，则1号点到所有的点的距离确定，即1号点到所有点的最短距离确定。
核心代码（伪代码）：
        for(i=1;i<=n;i++)
        {
                min1=maxn;
                遍历book数组，寻找距离1号顶点距离最短点，进行标记：u=j；
                book[u]=1;
                遍历此点到其他点的距离，松弛边：dis[v]=min(dis[v],dis[u]+a[u][v]);
        }
优化：
       堆优化（priority_queue）O((M+N)logN)
        用堆每次弹出最小值来代替每轮进行的最短边查找。堆用小根堆，可以保证每次在堆顶的元素是最小的。

Ford算法
适用情况：
       可以解决带负权边的图，可以判断是否存在负权回路（负权环）。
时间复杂度：O(NM)
            优化：可以用check来判断dis数组在本轮循环中是否发生变化。如果dis数组没有发生变化，即所求已经是最短路径，即可跳出循环。
算法思想：
       对所有的边进行n-1次松弛操作。
       进行k次松弛后，我们可以得到1号点最多经过k条边到其余点的最短距离。
       能否通过u[i]->v[i](权值为w[i])的边使1号顶点到v[i]的距离缩短，即：dis[v[i]]=min(dis[v[i]],dis[u[i]]+w[i])。
       对于正权回路，去掉的话，我们肯定可以得到更短的距离。
       对于负权回路，每循环一次都会得到更短的距离。所以我们可以通过进行n-1次循环之后，能不能继续松弛来判断图中是否存在负权回路。
核心代码：
       for(k=1;k<=n-1;k++)
            for(i=1;i<=m;i++)
                 dis[v[i]]=min(dis[v[i]],dis[u[i]]+w[i]);

SPFA算法（Ford算法的队列优化）
适用情况：
      同Ford算法。
时间复杂度：最坏情况O(NM)
算法思想：
       取出队首，对其出边进行松弛操作，将最短路径能够发生改变的点放入队尾。用数组book标识当前那些点已在队列中。
       形式上有些类似于BFS。
核心代码：
      用邻接表存图；队列操作。

像你这样的固体人不多了啊......