【图论】FLOYD弗洛伊德算法-最短路径

弗洛伊德算法是什么

弗洛伊德算法用于求多源最短路径，也就是求两个点的最短路径，其思想是基于动态规划。

弗洛伊德算法的组成和步骤

邻接矩阵dis：

若有n个点，则构建nn的邻接矩阵 如果路径带权值，则构建int数组：存储的数值代表两点间的最短距离，如果为INF，则两点不连接。如果路径不带权值，则构建bool数组：1代表两点有路径，0代表没有。 code： int dis[n+1][n+1] bool dis[n+1][n+1] 构建nn的 最少要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<"<"< #include 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<"<"«e«endl;//输出终点 } } return 0; }

测试：