Floyd algorithm
Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。
求解多源最短路问题的2种方法：
1.直接把Dijkstra调用|V|遍，时间复杂度为O(V^3);
2.Floyd算法更简洁，但算法复杂度仍为O(V^3)。
算法思路
遍历每个结点对，对每个结点对做松弛操作。结点对的松弛操作在图论里会经常用到，松弛操作用来求一个结点对之间的最短路径。假设图中有n个点，对图中结点对的松弛操作的思路为（以结点对1和n为例）：
1.建图，用一个二维数组edge[i][j]来表示i到j之间的距离。遍历每个结点对，松弛操作中edge数组表示两个点之间当前的最短距离。
2.允许经过前一个点，即2，进行中转，判断edge[1][n]和edge[1][2]+edge[2][n]之间的大小。若edge[1][2]+edge[2][n]更小，则表示通过点2中转的话1到n的距离比不中转更短。此时更新edge[1][n]的值为edge[1][2]+edge[2][n]。由于edge数组表示两个点之间当前的最短距离，则这时经过点2中转的结果已经隐含体现在了edge[1][n]中，之后的松弛操作都是在这一基础上进行。
3.重复2过程，允许经过前3~n-1个结点进行中转，保存每一次中转与否最短路径的变化。最后得到的edge[1][n]就是1到n的最短路径的路径和。
4.对图中的每一个结点对都进行松弛操作，此时edge[i][j]，就是从i到j的最短路径，不管i和j是几，都能得到答案。
算法图解
暑假，小万准备去一些城市旅游。有些城市之间有公路，有些城市之间则没有，如下图7。为了节省经费以及方便计划旅程，小万希望在出发之前知道任意两个城市之前的最短路程。
上图中有4个城市8条公路，公路上的数字表示这条公路的长短。请注意这些公路是单向的。我们现在需要求任意两个城市之间的最短路程，也就是求任意两个点之间的最短路径。这个问题这也被称为“多源最短路径”问题。
现在需要一个数据结构来存储图的信息，我们仍然可以用一个4x4的矩阵（二维数组e）来存储。比如1号城市到2号城市的路程为2，则设e[1][2]的值为2。2号城市无法到达4号城市，则设置e[2][4]的值为∞。另外此处约定一个城市自己是到自己的也是0，例如e[1][1]为0，具体如下图2所示。
现在回到问题：如何求任意两点之间最短路径呢？通过之前的学习我们知道通过深度或广度优先搜索可以求出两点之间的最短路径。所以进行n2遍深度或广度优先搜索，即对每两个点都进行一次深度或广度优先搜索，便可以求得任意两点之间的最短路径。可是还有没有别的方法呢？
我们来想一想，根据我们以往的经验，如果要让任意两点（例如从顶点a点到顶点b）之间的路程变短，只能引入第三个点（顶点k），并通过这个顶点k中转即a->k->b，才可能缩短原来从顶点a点到顶点b的路程。那么这个中转的顶点k是1~n中的哪个点呢？甚至有时候不只通过一个点，而是经过两个点或者更多点中转会更短，即a->k1->k2b->或者a->k1->k2…->k->i…->b。比如上图中从4号城市到3号城市（4->3）的路程e[4][3]原本是12。如果只通过1号城市中转（4->1->3），路程将缩短为11（e[4][1]+e[1][3]=5+6=11）。其实1号城市到3号城市也可以通过2号城市中转，使得1号到3号城市的路程缩短为5（e[1][2]+e[2][3]=2+3=5）。所以如果同时经过1号和2号两个城市中转的话，从4号城市到3号城市的路程会进一步缩短为10。通过这个的例子，我们发现每个顶点都有可能使得另外两个顶点之间的路程变短。好，下面我们将这个问题一般化。
当任意两点之间不允许经过第三个点时，这些城市之间最短路程就是初始路程，如下图9所示。
假如现在只允许经过1号顶点，求任意两点之间的最短路程，应该如何求呢？只需判断e[i][1]+e[1][j]是否比e[i][j]要小即可。e[i][j]表示的是从i号顶点到j号顶点之间的路程。e[i][1]+e[1][j]表示的是从i号顶点先到1号顶点，再从1号顶点到j号顶点的路程之和。其中i是1n循环，j也是1n循环，代码实现如下。
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
if (e[i][j] > e[i][1] + e[1][j])
e[i][j] = e[i][1] + e[1][j];
}
}在只允许经过1号顶点的情况下，任意两点之间的最短路程更新为：
通过上图我们发现：在只通过1号顶点中转的情况下，3号顶点到2号顶点（e[3][2]）、4号顶点到2号顶点（e[4][2]）以及4号顶点到3号顶点（e[4][3]）的路程都变短了。
接下来继续求在只允许经过1和2号两个顶点的情况下任意两点之间的最短路程。如何做呢？我们需要在只允许经过1号顶点时任意两点的最短路程的结果下，再判断如果经过2号顶点是否可以使得i号顶点到j号顶点之间的路程变得更短。即判断e[i][2]+e[2][j]是否比e[i][j]要小，代码实现为如下。
//经过1号顶点
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if (e[i][j] > e[i][1]+e[1][j])
e[i][j]=e[i][1]+e[1][j];
//经过2号顶点
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if (e[i][j] > e[i][2]+e[2][j])
e[i][j]=e[i][2]+e[2][j];在只允许经过1和2号顶点的情况下，任意两点之间的最短路程更新为：
通过上图得知，在相比只允许通过1号顶点进行中转的情况下，这里允许通过1和2号顶点进行中转，使得e[1][3]和e[4][3]的路程变得更短了。
同理，继续在只允许经过1、2和3号顶点进行中转的情况下，求任意两点之间的最短路程。任意两点之间的最短路程更新为：
最后允许通过所有顶点作为中转，任意两点之间最终的最短路程为：
代码实现(C++)
#include<iostream>
#define inf 999999 //表示两个点之间不连通
#define max 105
using namespace std;
int m,n,edge[max][max];
int main()
{
int i,j;
cin>>n>>m;
//先对邻接矩阵进行初始化
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
edge[i][j]=inf;
edge[i][i]=0;
}
//建图
while(m--)
{
cin>>i>>j;
cin>>edge[i][j];
edge[j][i]=edge[i][j];
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
//若结点对跟中转点不连通，则跳过
if(edge[i][k]!=inf && edge[k][j]!=inf && edge[i][j]>(edge[i][k]+edge[k][j]))
//更新最短路径
edge[i][j]=edge[i][k]+edge[k][j];
cout<<edge[1][n]<<endl;
return 0;
}参考
[1]https://www.cnblogs.com/wangyuliang/p/9216365.html
[2]https://blog.csdn.net/Q_M_X_D_D_/article/details/84866501
[3]https://www.jianshu.com/p/ff6db00ad866
