首页 > 其他分享 >弗洛伊德

弗洛伊德

时间:2022-10-30 21:24:45浏览次数:50  
标签:弗洛伊德 arrays 矩阵 int Floyd 邻界

概念:

Floyd算法又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法
百度

只能实现非负数的距离

时间:

\(O(n^3)\)
感觉一般,但是简单,但是不建议用,还是优化的弗洛伊德时间少

代码实现

图
通过邻界矩阵实现

class Floyd{
    public:
    //邻界矩阵
    int N=;//数据
    int arrays[N][N];
    Floyd(int n){//邻接矩阵初始化
        for(int i =1;i<=n;i++){
            for(int j  = 1;j<=n;j++){
                arrays[i][j] = INT_MAX;//相当于没联通的路线为无穷远
            }
        }
    }
    //通过已知的路线,初始化相邻的节点的距离,假如有m个节点相邻
    for(int i  = 0;i<m;i++){
        arr[p1][p2] = (p1,p2的距离)//实现一种相邻点的距离
        arr[p2][p1] = (p1,p2的距离)
    }

    int floyd(int n ){
        int source,target;//源点和目标点
        for(int k = 1;k<=n;k++){
            for(int i = 1;i<=n;i++){
                for(int j = 1;j<=n;j++){
                    if(i!=j&&arrays[i][j]>arrays[i][k]+arrays[k][j]){//判断直接相连和间接的距离大小
                        arrays[i][j]=arrays[i][k]+arrays[k][j]
                    }
                }
            }
        }
        //得到的arrays[source][target],就是最短距离
    }
    

};

标签:弗洛伊德,arrays,矩阵,int,Floyd,邻界
From: https://www.cnblogs.com/tsqo/p/16842274.html

相关文章

  • 弗洛伊德算法
    简介和Dijkstra算法一样,弗洛伊德(Floyd)算法也是一种用于寻找给定的加权图中顶点间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系......
  • 弗洛伊德算法
    简介和Dijkstra算法一样,弗洛伊德(Floyd)算法也是一种用于寻找给定的加权图中顶点间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科......
  • 弗洛伊德(Floyd)算法
    1.弗洛伊德(Floyd)算法介绍1)和Dijkstra算法一样,弗洛伊德(Floyd)算法也是一种用于寻找给定的加权图中顶点间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者......
  • Floyd(弗洛伊德)
     Floyd(弗洛伊德)时间复杂度O(n^3)#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#defineendl"\n"#definefifirst#definesesecond#defi......