[前言&胡扯]

说到最短路问题，我们无非就是用三种算法进行处理：

①：Floyd。②：Dijkstra。③：Spfa

对于最短路算法，学长之前给我们讲过，可是当时我因为不想听课，上课走神等原因，成功的没有学扎实，现在来重新 复习 重新学习一下

---

[Floyd]

• 定义：Floyd算法，是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。
• 时间&空间复杂度：
  Floyd算法的时间复杂度为$O(N^3)$，空间复杂度为$O(N^2)$。
  
• Floyd可以说是最暴力的一个算法了,用Floyd的时候，往往用邻接矩阵来存储。
  Q：为什么用邻接矩阵来存而不是邻接表来存呢？？
  A：没有那个必要啊，Floyd的时间复杂度是$O(N^3)$，$O(N^3)$能跑的范围，邻接矩阵完全可以存过来，不过你要是实在想写邻接表来存，我也不拦你用邻接表来存Floyd 1s 能跑过来的图。。。

以下是Floyd的模板：

#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long int 

using namespace std;

int map[5010][5010];
int n,m;

const int INF=0x7fffffff; 

signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            map[i][j]=INF;
        }
    }
    for(int i=1;i<=n;i++)
    {
        map[i][i]=0;
    }
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        map[u][v]=w;
        map[v][u]=w;
    }
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(map[i][j]>map[i][k]+map[k][j]&&k!=i&&k!=j&&i!=j)
                {
                    map[i][j]=map[i][k]+map[k][j];
                }               
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cout<<map[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
} 

/*样例输入
4 6 
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
输出：
0 2 4 3
2 0 2 1
4 2 0 3
3 1 3 0
*/

---

[Dijkstra]

• 定义：Dijkstra算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

• Q&A：
  Q:Dijkstra比Floyd好在哪里呢？？
  A:上面说过Dijkstra是典型的单源最短路径算法，何谓单 源最短路？？就是给定一个起始点和终点，求他们两个 之间的最短路，求一遍Dijkstra（非优化）的时间复杂度是$O(n^2)$，你要是想求出每个点到每个点的最短路，我还是建议你用Floyd，因为Dijkstra求n遍单源最短路的复杂度和Floyd一样都是$O(n^3)$，当然，这里说的都是未优化的情况，优化的Dijkstra下面会讲到。

• Dijkstra是一种类似于贪心的算法,具体步骤：
  • 当到一个时间点时，图上已经有一部分的点，最短路径已经确定，而部分点尚未确定。
  • 在所有未确定的点中选择离原点最近的点，把它认为是这两个点之间的最短距离。
  • 然后把这个点所有的出边都遍历一边，并更新所有点。