目录
弗洛伊德算法是什么
弗洛伊德算法用于求多源最短路径，也就是求两个点的最短路径，其思想是基于动态规划。
弗洛伊德算法的组成和步骤
邻接矩阵dis：
若有n个点，则构建n*n的邻接矩阵 如果路径带权值，则构建int数组：存储的数值代表两点间的最短距离，如果为INF，则两点不连接。如果路径不带权值，则构建bool数组：1代表两点有路径，0代表没有。
code：
int dis[n+1][n+1]
bool dis[n+1][n+1]构建n*n的 最少要n+1 因为数组下标从0开始
初始化：
对于一个点自己来说，自己到自己没有距离，初始化为0。其他值全部初始化为INF，默认任意两点之间没有距离。
code:
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
if(i==j){
dis[i][j]=0;
}else{
dis[i][j]=INF;
}
}
}遍历邻接关系：
code1:
无边权
//不带权值的情况
int x,y;//用于输入一条边的两个点
while(m--){
cin>>x>>y;
dis[x][y]=1;
dis[y][x]=1;
}code2:
有边权
//带权值的情况
int x,y;//用于输入一条边的两个点
int val;//用于输入权值
while(m--){
cin>>x>>y>>val;
dis[x][y]=val;
dis[y][x]=val;
}FLOYD核心：
是通过一个三层循环，利用动态规划的思想，先确定中转点k，再枚举每一对点i j 。看i通过k到j会不会比本来的dis[i][j]更近，如果更近就更新。所以最外层循环为枚举中转点K，内两层循环为枚举每一对点。
所以状态转移方程就是:
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
code:
//floyd 计算最短路径
for(int k=1;k<=n;++k){//中转点
for(int i=1;i<=n;++i){//每一对邻接点
for(int j=1;j<=n;++j){
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
}最短路径的存储：
上述代码只完成了最短距离的计算，无法输出最短的路径。
我们只需要构建一个path[n][n]数组，在FLOYD算法的最内层。如果有更新dis[i][j]，则同步更新记录 i到j的最短路径的中转点即可。
初始化path：
默认path[i][j]=j 就是两个点的最短路径都默认初始化为要经过右边的终点。
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j) {
path[i][j]=j;
} 带记录路径的FLOYD算法
//floyd 计算最短路径
for(int k=1;k<=n;++k){//中转点
for(int i=1;i<=n;++i){//每一对邻接点
for(int j=1;j<=n;++j){
if(dis[i][j]>dis[i][k]+dis[k][j]){
dis[i][j]=dis[i][k]+dis[k][j];
path[i][j]=k;//更新最短路径的中转点
}
}
}
}输出最短路径:
比如要求3 到 5的最短路径 ：先输出起点3。由于我们初始化path数组时 默认path[i][j]=j，所以每次记录path[i][j]=k，用一个while循环判断 只要k!=j 就先输出k 代表会途径这个点 再记录path[k][j]，重新循环判断，直到k==j。 最后再输出终点
int s,e;//代表起点和终点
cin>>s>>e;
cout<<s;//先输出起点
//先记录中转点
int k=path[s][e];
while(k!=e){//如果中转点不是终点
cout<<"->"<<k;//输出中转点
k=path[k][e];//记录新的中转点 重新循环
}
cout<<"->"<<e;//输出终点完整代码：
#include<iostream>
#include<cstdio>
using namespace std;
#define INF 0x3f3f3f3f
const int n=5;//10个点
int m=5;//十条边
int main(){
int dis[n+1][n+1];
int path[n+1][n+1];
for(int i=1;i<=n;++i){//初始化dis 和path
for(int j=1;j<=n;++j){
path[i][j]=j;
if(i==j){
dis[i][j]=0;
}else{
dis[i][j]=INF;
}
}
}
//比如有m对邻接关系 或者说m条边
//带权值的情况
int x,y;//用于输入一条边的两个点
int val;//用于输入权值
while(m--){
cin>>x>>y>>val;
dis[x][y]=val;
dis[y][x]=val;
}
//floyd 计算最短路径
for(int k=1;k<=n;++k){//中转点
for(int i=1;i<=n;++i){//每一对邻接点
for(int j=1;j<=n;++j){
if(dis[i][j]>dis[i][k]+dis[k][j]){
dis[i][j]=dis[i][k]+dis[k][j];
path[i][j]=k;//更新最短路径的中转点
}
}
}
}
int s,e;//代表起点和终点
while(cin>>s>>e){
//先判断两点之间是否有最短路径
if(dis[s][e]==INF){//两点到不了
cout<<s<<"和"<<e<<"无最短路径";
}else{
cout<<s<<"和"<<e<<"最短距离为："<<dis[s][e]<<endl;//先输出最短距离
cout<<s;//先输出起点
//先记录中转点
int k=path[s][e];
while(k!=e){//如果中转点不是终点
cout<<"->"<<k;//输出中转点
k=path[k][e];//记录新的中转点 重新循环
}
cout<<"->"<<e<<endl;//输出终点
}
}
return 0;
}
测试：
