无向图弗洛伊德算法求最短路径 输出路径
弗洛伊德算法求最短路径 输出路径
弗洛伊德算法其实比较好理解
这里我用邻接矩阵的储存方法来写
一.算法思想
1.1
如果我们要用邻接矩阵来写代码的话，就要储存他的权值信息
这里我们用map[][]这个二维数组来储存
其次要输出他的最短路径
就用path[][]来储存
int map[100][100];
int path[100][100];
1.2
初始化这个储存权值邻接矩阵
由于是无环图，自己到自己是 0
剩下的边的权值我们赋值为MAX
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
if(i==j)
map[i][j]=0;
else
map[i][j]=max;
1.3
读入边的信息
如果两个结点i，j之间有权值，就把他赋值给map[i][j]
并且这个时候将j赋值给path[i][j]
cout<<"输入点1到点2的距离"<<endl;
for(int i=1; i<=m; i++)
{
cin>>t1>>t2>>t3;
map[t1][t2]=t3;
map[t2][t1]=t3;
path[t1][t2]=t2;
}
这个路径的赋值如果在后面有更优解
将会更新这个值，如果没有，那说明i直接到j就是最短的
1.4 核心算法
这个核心算法使用一个三重循环来一个一个找最优解
第一重循环控制中转结点k
第二重控制起始结点i
第三重控制终止结点j
如果我们发现i->k->j的路径小于i->j的
那我们就更新路径，将path[i][j]=path[i][k]
同时权值邻接矩阵更新`map[i][j]=map[i][k]+map[k][j]
for(int k=1; k<=n; k++)
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
if(map[i][k]+map[k][j]<map[i][j])
{
map[i][j]=map[i][k]+map[k][j];
path[i][j]=path[i][k];
}
1.5
输出最短路径的值
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
cout<<map[i][j]<<" ";
cout<<endl;
}
1.6
输出最短路径
这里我们要输入两个结点v1 v2
最后输出的就是v1到v2的最短路径
仔细想想我们的path[v1][v2]储存的是v1 v2的第一个中转节点z的信息
输出z后，path[z][v2]储存的是z到v2的第一个中转结点
一个一个输出这些中转结点
以此类推，直到z为v2的时候，这就是v1到v2的最短路径
int v1,v2,z;
cout<<"输入两个点，输出之间路径"<<endl;
cin>>v1>>v2;
z=path[v1][v2];
cout<<v1;
while(z!=v2)
{
cout<<"->"<<z;
z=path[z][v2];
}
cout<<"->"<<v2;
二.测试数据
这里的最短距离我直接的输出距离矩阵了
如果要输出更方便阅读的形式
也可以在输出那块把代码改一下，可以cout<<"v1到v2的距离为：<<map[v1][v2]<<endl
我就不多写了
##测试数据
1 2 2
1 3 1
2 3 5
2 4 4
3 4 5
4 5 6
三.源代码
#include<iostream>
using namespace std;
#define max 99999
void fuluoyide(int n,int m)
{
int map[100][100],t1,t2,t3;
int path[100][100];
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
if(i==j)
map[i][j]=0;
else
map[i][j]=max;
//读入边
cout<<"输入点1到点2的距离"<<endl;
for(int i=1; i<=m; i++)
{
cin>>t1>>t2>>t3;
map[t1][t2]=t3;
map[t2][t1]=t3;
path[t1][t2]=t2;
}
//弗洛伊德(Floyd)核心语句
for(int k=1; k<=n; k++)
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
if(map[i][k]+map[k][j]<map[i][j])
{
map[i][j]=map[i][k]+map[k][j];
path[i][j]=path[i][k];
}
cout<<endl<<"最短距离矩阵为："<<endl;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
cout<<map[i][j]<<" ";
cout<<endl;
}
int v1,v2,z;
cout<<"输入两个点，输出之间路径"<<endl;
cin>>v1>>v2;
z=path[v1][v2];
cout<<v1;
while(z!=v2)
{
cout<<"->"<<z;
z=path[z][v2];
}
cout<<"->"<<v2;
}
int main()
{
cout<<"输入顶点数，边数"<<endl;
int n,m;
cin>>n>>m;//n表示顶点个数，m表示边的条数
cout<<endl;
fuluoyide(n,m);
}
总体来说 弗洛伊德算法的思想不是很难懂，有一点点暴力求值的感觉，就硬算
我还写了一篇 dijkstra 求最短路径的算法，也可以看看
