基本思想：动态规划.又称插点法。
//完美的博客
https://blog.csdn.net/anlian523/article/details/80925625#%E6%97%A0%E8%B4%9F%E6%9D%83%E7%8E%AF

算法过程：
将求最短路分阶段进行.
最开始图中两个点，假设只能经过3号点，暴力枚举看是否能够更新dp[i][j].
3号点更新完之后，再将4号点***来,继续去更新dp[i][j]
如此往复,将所有点都插入图中，最后求出dp[i][j].

解释:
①在插入第k个点的时候dp[i][j]的含义为i 到 j 只含前k个点的最短路.
应用：求最短路，最长路，传递闭包，求最小环
时间复杂度:O(n^3)
存储：邻接矩阵

代码实现:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int inf = 0x3f;
const int maxn = 1005;
int f[maxn][maxn];
int main()
{
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    int x,y,z;
    memset(f,inf,sizeof f);
    for(int i = 1;i<=n;i++)
          f[i][i] = 0;
    for(int i = 1;i<=m;i++)
    {
        cin>>x>>y>>z;
        f[x][y] = f[y][x] = z;
    }
    for(int k = 1;k<=n;k++)
        for(int i = 1;i<=n;i++)
            for(int j = 1;j<=n;j++)
                if(f[i][k] + f[k][j] < f[i][j])
                    f[i][j] =  f[i][k] + f[k][j];
    int q;
    cin>>q;
    //int x,y;
    while(q--)
    {
        cin>>x>>y;
        cout<<f[x][y]<<endl;
    }
    return 0;
}

拓展：Floyd求最小环(待补)

对于一个最小环，显然至少要包含三个点.
算法进行到第k阶段时,
对于图中所有点求 ans = min(ans,f[i][j] + dis[i][k]+dis[k][j]).
若图中有过k点的环，那么本阶段ans求得的是只允许松弛前k个点的最小环。
我们也只需要用k去更新前k-1个点就好.

证明(口胡):
假设图中没有环,那么ans为INF。
假设图中有m个环，
设为 c1 c2 c3 c4 ... cm.
其中 Cx为权值最小环.设Cx中点编号最大点为***,设环中直接与***相邻的两个点为i,j;
那么当进行到第G个阶段, ans = min(ans,f[i][j] + dis[i][G]+dis[G][j]).
此时f[i][j]已经是全局最短路(因为***是环中编号最大的点了).
所以求得的就是Cx的值，此后值不再变化，得证。

代码:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int inf = 0x3f;
const int maxn = 1005;
int f[maxn][maxn],dis[maxn][maxn];
int main()
{
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    int x,y,z;
   // memset(f,inf,sizeof f);   //注意 memset的inf*3 会爆int
    for(int i = 1;i<=maxn;i++)
        for(int j = 1;j<=maxn;j++)
            if(i == j) f[i][j] = 0;
            else f[i][j] = 9e7;
    for(int i = 1;i<=m;i++)
    {
        cin>>x>>y>>z;
        f[x][y] = f[y][x] = z;
        dis[x][y] = dis[y][x] = z;
    }
    int ans;
    memset(ans,inf,sizeof ans);
    for(int k = 1;k<=n;k++)
    {
        for(int i = 1;i<=k-1;i++)
            for(int j = i+1;j<=k-1;j++)
                    ans =  min(ans,f[i][j] + dis[i][k]+dis[k][j]);
        for(int i = 1;i<=n;i++)
            for(int j = 1;j<=n;j++)
                if(f[i][k] + f[k][j] < f[i][j])
                    f[i][j] =  f[i][k] + f[k][j];
    }
    int q;
    cin>>q;
    //int x,y;
    /*while(q--)
    {
        cin>>x>>y;
        cout<<f[x][y]<<endl;
    }*/
    return 0;
}


//

/*
4 5
1 2 1
2 4 1
1 4 10
1 3 1
3 4 20

*/

①无向图注意要处理重边，若有重边出现，取min
②求最小环的时候只能循环到k-1.

拓展二：Floyd链表判圈(面试)