钦北区网站建设,网站中英文切换前端,从化网站开发,腾讯云服务器使用教程佛洛伊德最短路径算法 讲解 以及 C实现 算法的特点#xff1a; 弗洛伊德算法(Floyd)是解决任意两点间的最短路径的一种算法#xff0c;可以正确处理有向图或有向图或负权#xff08;但不可存在负权回路)的最短路径问题#xff0c;同时也被用于计算有向图的传递闭包。 算法…佛洛伊德最短路径算法 讲解 以及 C实现 算法的特点 弗洛伊德算法(Floyd)是解决任意两点间的最短路径的一种算法可以正确处理有向图或有向图或负权但不可存在负权回路)的最短路径问题同时也被用于计算有向图的传递闭包。 算法的思路
通过Floyd计算图G(V,E)中各个顶点的最短路径时需要引入两个矩阵矩阵S中的元素a[i][j]表示顶点i(第i个顶点)到顶点j(第j个顶点)的距离。矩阵P中的元素b[i][j]表示顶点i到顶点j经过了b[i][j]记录的值所表示的顶点。
假设图G中顶点个数为N则需要对矩阵D和矩阵P进行N次更新。初始时矩阵D中顶点a[i][j]的距离为顶点i到顶点j的权值如果i和j不相邻则a[i][j]∞矩阵P的值为顶点b[i][j]的j的值。 接下来开始对矩阵D进行N次更新。第1次更新时如果”a[i][j]的距离” “a[i][0]a[0][j]”(a[i][0]a[0][j]表示”i与j之间经过第1个顶点的距离”)则更新a[i][j]为”a[i][0]a[0][j]”,更新b[i][j]b[i][0]。 同理第k次更新时如果”a[i][j]的距离” “a[i][k-1]a[k-1][j]”则更新a[i][j]为”a[i][k-1]a[k-1][j]”,b[i][j]b[i][k-1]。
涉及到了两个矩阵
距离矩阵 比较好理解存储的是任意两点之间的最小距离 路径矩阵 路径矩阵的第i行j列代表的时顶点i与顶点j之间最短距离的中间节点。例如i,j两个点 最短的边为i-j则路径矩阵的path[i][j]i最短的边为i-k-j则path[i][j]k,path[i][k]i;最短的边为i-k-h-j则path[i][j]h,path[i][h]k,path[i][k]i; 在实现对应的路径输出时进行寻路输出
3、Floyd算法的实例过程 第一步我们先初始化两个矩阵得到下图两个矩阵
、
第二步以v1为中阶更新两个矩阵 发现a[1][0]a[0][6] a[1][6] 和a[6][0]a[0][1] a[6][1]所以我们只需要矩阵D和矩阵P结果如下 通过矩阵P我发现v2–v7的最短路径是v2–v1–v7
第三步以v2作为中介来更新我们的两个矩阵使用同样的原理扫描整个矩阵得到如下图的结果 总结 FLoyd算法其实就是每次选择一个中介点更新根据这个中节点可以连接起来的两个点的距离信息在path中记录对应的路径 代码 代码设计了一个FloydWay类实现了有向图和无向图的两种版本 写代码的时候偷了懒路径的输出是倒着的 #includebits/stdc.h
using namespace std;
const int INF1e6;
//
class FloydWay{public:int vertex_num;void out_matrix(vectorvectorintmatrix)const{for(int i0;imatrix.size();i){for(int u0;umatrix[i].size();u){if(matrix[i][u]INF||matrix[i][u]-1){coutleftsetw(5)/;}else{coutleftsetw(5)matrix[i][u];}}coutendl;}}void out_path_single(int i,int u){int ku;coutk-;while(k!i){kpath_matrix[i][k];coutk;if(k!i){cout-;continue;}else{cout | min dist: min_dist_matirx[i][u];coutendl;}}}void out_all_path(){for(int i0;ivertex_num;i){for(int ui1;uvertex_num;u){couti-u: ;out_path_single(i,u);}}}vectorvectorintgraph_matrix;//图矩阵vectorvectorintmin_dist_matirx;//最短距离矩阵vectorvectorintpath_matrix;//路径矩阵FloydWay(vectorvectorintgraph_matri):graph_matrix(graph_matri),vertex_num(graph_matri.size()){//初始化最短距离矩阵,路径矩阵min_dist_matirxvectorvectorint(vertex_num,vectorint(vertex_num,INF));path_matrixvectorvectorint(vertex_num,vectorint(vertex_num,-1));for(int i0;ivertex_num;i){for(int j0;jvertex_num;j){min_dist_matirx[i][j]graph_matrix[i][j];path_matrix[i][j]i;}}cout初始的距离矩阵endl;out_matrix(min_dist_matirx);cout初始的路径矩阵endl;out_matrix(path_matrix);}void floyd_undirected(){//在无向图中的算法cout###无向图###endl;for(int i0;ivertex_num;i){//第一层循环选择中间点for(int u0;uvertex_num;u){//第二、三曾循环遍历顶点for(int k0;kvertex_num;k){if(min_dist_matirx[u][k]min_dist_matirx[i][u]min_dist_matirx[i][k]){min_dist_matirx[u][k]min_dist_matirx[i][u]min_dist_matirx[i][k];min_dist_matirx[k][u]min_dist_matirx[i][u]min_dist_matirx[i][k];path_matrix[u][k]i;path_matrix[k][u]i;coutu到k(双向)以i为中间节点可以取得更小值endl;cout更新后的距离矩阵endl;out_matrix(min_dist_matirx);cout更新后的路径矩阵endl;out_matrix(path_matrix);}}}}cout最终的距离矩阵endl;out_matrix(min_dist_matirx);cout最终的路径矩阵endl;out_matrix(path_matrix);out_all_path();}void floyd_directed(){//在有向图中的算法cout###有向图###endl;for(int i0;ivertex_num;i){//第一层循环选择中间点for(int u0;uvertex_num;u){//第二、三曾循环遍历顶点for(int k0;kvertex_num;k){if(min_dist_matirx[u][k]min_dist_matirx[u][i]min_dist_matirx[i][k]){min_dist_matirx[u][k]min_dist_matirx[u][i]min_dist_matirx[i][k];path_matrix[u][k]i;coutu到k(单向)以i为中间节点可以取得更小值endl;cout更新后的距离矩阵endl;out_matrix(min_dist_matirx);cout更新后的路径矩阵endl;out_matrix(path_matrix);}}}}cout最终的距离矩阵endl;out_matrix(min_dist_matirx);cout最终的路径矩阵endl;out_matrix(path_matrix);out_all_path();}
};
int main(){vectorvectorintgraph_undirected{{0, 1, 4, INF},{1, 0, INF, 1},{4, INF, 0, 1},{INF, 1, 1, 0}};vectorvectorintgraph_directed{{0, 1, 4, INF},{INF, 0, INF, 1},{INF, INF, 0, INF},{INF, INF, 1, 0}};FloydWay(graph_undirected).floyd_undirected();FloydWay(graph_directed).floyd_directed();
}运行结果
