floyd算法 订阅
Floyd算法又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法,与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。 [1] 展开全文
Floyd算法又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法,与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。 [1]
信息
空间复杂度
O(n^2)
作    用
求多源最短路径,求传递闭包
别    名
Roy-Warshall算法
中文名
弗洛伊德算法
时间复杂度
O(n^3)
外文名
Floyd(Floyd-Warshall)
Floyd算法简介
在计算机科学中,Floyd-Warshall算法是一种在具有正或负边缘权重(但没有负周期)的加权图中找到最短路径的算法。算法的单个执行将找到所有顶点对之间的最短路径的长度(加权)。 虽然它不返回路径本身的细节,但是可以通过对算法的简单修改来重建路径。 该算法的版本也可用于查找关系R的传递闭包,或(与Schulze投票系统相关)在加权图中所有顶点对之间的最宽路径。Floyd-Warshall算法是动态规划的一个例子,并在1962年由Robert Floyd以其当前公认的形式出版。然而,它基本上与Bernard Roy在1959年先前发表的算法和1962年的Stephen Warshall中找到图形的传递闭包基本相同,并且与Kleene的算法密切相关 在1956年)用于将确定性有限自动机转换为正则表达式。算法作为三个嵌套for循环的现代公式首先由Peter Ingerman在1962年描述。该算法也称为Floyd算法,Roy-Warshall算法,Roy-Floyd算法或WFI算法。 [2] 
收起全文
精华内容
下载资源
问答
  • 主要介绍了Python基于Floyd算法求解最短路径距离问题,结合完整实例形式详细分析了Python使用Floyd算法求解最短路径距离问题的相关操作技巧与注意事项,需要的朋友可以参考下
  • Floyd算法思想

    2018-11-28 19:16:48
    Floyd算法思想,准确详细的描述了算法的思想和方法,适合新手,并附有代码
  • Floyd算法-java实现

    2019-04-23 14:52:17
    解决任意两点间的最短路径的一种算法,可以正确处理有向图或负权的最短...Floyd-Warshall算法的时间复杂度为O(N3),空间复杂度为O(N2)。 java代码实现。算法详解,参考技术文档 https://www.jianshu.com/p/db0df9197073
  • 正如我们所知道的,Floyd算法用于求最短路径。Floyd算法可以说是Warshall算法的扩展,三个for循环就可以解决问题,所以它的时间复杂度为O(n^3)。 Floyd算法的基本思想如下:从任意节点A到任意节点B的最短路径不外乎2...
  • 本节内容 最短路径 Floyd算法 王道考研/ Robert WFloyd Floyd算法Floyd-Warshall算法 堆排序算法 罗伯特弗洛伊德 1936 2001Robert WFloyd 1978年图灵奖得主 王道考研/ Floyd算法 Floyd算法求出每对顶点之间的最短...
  • 主要为大家详细介绍了C语言实现图的最短路径Floyd算法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • Floyd算法求任意两点之间的路径(matlab程序)
  • 教科书上的Floyd算法只能输出path,无法给出具体的路径描述,本代码可以输出具体的路径选择
  • 算法与数据结构的结课课程的报告。参考文章加自己提炼。求解几个点之间的最短距离的算法。c++源码在vs2019可以实现,也比较好容易理解。希望有所帮助。没有要积分,因为我也是参考别人的。
  • PAGE PAGE 1 欢迎下载 数学建模 基于Floyd算法的公园道路 优化设计问题 小组编号 02 小组成员队员1 张 聪-建模 队员2 汪 涛-建模 队员3 胡 娜-建模 队员4 薛向龙-建模 队员5 蔡诗聂-编程 队员6 杨志诚-编程 2012年 7...
  • 主要为大家详细介绍了Java实现Floyd算法求最短路径,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 沈阳理工大学课程设计专用纸 PAGE PAGE II 摘 要 现实生活中许多实际问题的解决依赖于最短路径的应用其中比较常用的是floyd算法通过floyd算法使最短路径问题变得简单化采用图的邻接矩阵或邻接表实现最短路径问题中图...
  • python实现Floyd算法

    2020-09-20 22:29:43
    主要为大家详细介绍了python实现Floyd算法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • Floyd算法

    2021-06-20 11:30:03
    只要图中不包含长度为负的回路,可用Floyd算法来生成距离矩阵。 该算法既可应用于无向加权图,也可用于有向加权图。 对于一个带权有向图: 其对应的权重矩阵为: 而距离矩阵为: 而我们的要求便是通过权重矩阵求...

    给定一个带权连通图(有向或无向),要求找出从每个顶点到其他所有顶点之间的距离(最短路径的长度),这就是完全最短路径问题

    只要图中不包含长度为负的回路,可用Floyd算法来生成距离矩阵。

    该算法既可应用于无向加权图,也可用于有向加权图

    对于一个带权有向图:

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-sqTQSOYQ-1624159776958)(C:\Users\llj\AppData\Roaming\Typora\typora-user-images\image-20210620104500226.png)]

    其对应的权重矩阵为:

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rSQGXO5x-1624159776963)(C:\Users\llj\AppData\Roaming\Typora\typora-user-images\image-20210620104524204.png)]

    而距离矩阵为:

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ZvA3v7Q8-1624159776967)(C:\Users\llj\AppData\Roaming\Typora\typora-user-images\image-20210620104548550.png)]

    而我们的要求便是通过权重矩阵求出其对应的距离矩阵。

    算法思想

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mgbTXrsM-1624159776972)(C:\Users\llj\AppData\Roaming\Typora\typora-user-images\image-20210620110026048.png)]

    其中,D(0)即为权重矩阵,D(n)即为距离矩阵。

    状态转移方程

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-OLfphsDu-1624159776976)(C:\Users\llj\AppData\Roaming\Typora\typora-user-images\image-20210620110403324.png)]

    由上图可知,第k次迭代中[ i , j ]之间的距离是由d[ i , j ]和d[ i , k ]+d[ k , j ]确定的,哪个距离最短就是哪个,因此我们可以得到如下的状态转移方程:

    (C:\Users\llj\AppData\Roaming\Typora\typora-user-images\image-20210620110653280.png)]

    如:求出下图的距离矩阵:

    [(C:\Users\llj\AppData\Roaming\Typora\typora-user-images\image-20210620110747648.png)]

    则用Floyd算法的过程为:

    对于D(0),很显然为该图的权重矩阵。

    对于D(1),在D(0)的基础上添加了第一行第一列,注意到,由于[b,a]+[a,c]=2+3=5<[b,c],因此就将[b,c]更新成5,以此类推。

    对于D(2),在D(1)的基础上添加了第二行第二列,由于[c,b]+[b,a]=7+2=9<[c,a],因此将[c,a]更新成9,以此类推。

    ……

    最终迭代到D(4),算法终止。

    伪代码

    由上述思想,我们可以得到如下伪代码:

    algorithm Floyd(W[1..n, 1..n])
    //使用Floyd算法求距离矩阵
    //输入:有向图的权重矩阵
    //输出:对应的距离矩阵
    D <- W
    for k <- 1 to n do
    	for i <- 1 to n do
    		for j <- 1 to n do
    			D[i, j] <- min{D[i, j], D[i, k]+D[k, j]}
    return D
    

    代码实现

    这里我使用的是C++(以前面的例子为例):

    首先是权重矩阵:

    int W[4][4] = {
    	{0, 99, 3, 99},
    	{2, 0, 99, 99},
    	{99, 7, 0, 1},
    	{6, 99, 99, 0}
    };
    

    然后是Floyd算法的实现:

    void Floyd(int W[][4], int D[][4]) {
    	for (int i = 0; i < 4; i++) {
    		for (int j = 0; j < 4; j++) {
    			D[i][j] = W[i][j];
    		}
    	}
    	for (int k = 0; k < 4; k++) {
    		for (int i = 0; i < 4; i++) {
    			for (int j = 0; j < 4; j++) {
    				int temp = D[i][k] + D[k][j];
    				D[i][j] = (D[i][j] < temp) ? D[i][j] : temp;
    			}
    		}
    	}
    }
    

    再在main()函数中启动:

    int main() {
    	int D[4][4];
    
    	Floyd(W, D);
    	for (int i = 0; i < 4; i++) {
    		for (int j = 0; j < 4; j++) {
    			cout << D[i][j] << " ";
    		}cout << endl;
    	}
    
    	return 0;
    }
    

    运行结果如下:

    在这里插入图片描述

    可以看到,输出了我们想要的最终结果。

    完整代码

    #include<iostream>
    using namespace std;
    
    int W[4][4] = {
    	{0, 99, 3, 99},
    	{2, 0, 99, 99},
    	{99, 7, 0, 1},
    	{6, 99, 99, 0}
    };
    
    void Floyd(int W[][4], int D[][4]) {
    	for (int i = 0; i < 4; i++) {
    		for (int j = 0; j < 4; j++) {
    			D[i][j] = W[i][j];
    		}
    	}
    	for (int k = 0; k < 4; k++) {
    		for (int i = 0; i < 4; i++) {
    			for (int j = 0; j < 4; j++) {
    				int temp = D[i][k] + D[k][j];
    				D[i][j] = (D[i][j] < temp) ? D[i][j] : temp;
    			}
    		}
    	}
    }
    
    int main() {
    	int D[4][4];
    
    	Floyd(W, D);
    	for (int i = 0; i < 4; i++) {
    		for (int j = 0; j < 4; j++) {
    			cout << D[i][j] << " ";
    		}cout << endl;
    	}
    
    	return 0;
    }
    
    展开全文
  • 图:FLoyd算法

    2014-08-04 13:36:34
    使用Floyd算法,求解点对之间的最短距离。图结构使用邻接矩阵存储。
  • java实现Floyd算法

    2020-08-28 09:09:29
    主要为大家详细介绍了java实现Floyd算法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 针对中小城镇环境线网特点,用Floyd算法,以站点间的客流O-D分布为基本依据,在"逐条布线、优化成网"的方法基础上进行优化。通过在起终站点间插入重要节点,调整线路走向,从而改变线网运输的客流总量。避免了严格按照...
  • 摘 要 现实生活中许多实际问题的解决依赖于最短路径的应用其中比较常用的是floyd算法通过floyd算法使最短路径问题变得简单化采用图的邻接矩阵或邻接表实现最短路径问题中图的存储采用Visual C++6.0的控制台工程和...
  • floyd算法

    千次阅读 2018-11-02 13:08:33
    floyd算法解决的问题是在图中找到从i号结点到j号结点最短路径值(边的权值)的问题,核心代码就下面四行 for(int k = 0;k &lt; n;k++) for(int i = 0;i &lt; n;i++) for(int j = 0;j &lt; n;j++) dp...

    floyd

    floyd算法解决的问题是在图中找到从i号结点到j号结点最短路径值(边的权值)的问题,核心代码就下面四行

    for(int k = 0;k < n;k++)
        for(int i = 0;i < n;i++)
            for(int j = 0;j < n;j++)
                dp[i][j] = Math.min(dp[i][j],dp[i][k] + dp[k][j]);
    

    很容易理解,假设i和j中间有一个点k,那么i到j的最短路径值肯定是i到j,或者i先到k然后k到j两者中最小的

    题目链接:Codeforces522A


    题目大意是说,有一条消息,B从A那里转发,C从B那里转发,…,问最长的转发链长度是多少,你可以理解为dfs问题,也可以认为是floyd问题,如果用floyd解法来做就是算出每一个从i到j的最短路径值,然后再在其中找最大,注意人名统一大小写即可

    import java.util.Scanner;
    import java.util.TreeMap;
    public class Main {
    
    	public static void main(String[] args) {
    		Scanner cin = new Scanner(System.in);
    		int n = cin.nextInt();
    		int num = 0;
    		TreeMap<String,Integer> map = new TreeMap<>();
    		int[][] dp = new int[250][250];
    		
    		for(int i = 0;i < 250;i++)
    			for(int j = 0;j < 250;j++)
    				dp[i][j] = 0x3f3f3f3f;
    		
    		for(int i = 0;i < n;i++) {
    			String name1 = cin.next();
    			name1 = name1.toLowerCase();
    			cin.next();
    			String name2 = cin.next();
    			name2 = name2.toLowerCase();
    			if(!map.containsKey(name1))
    				map.put(name1,++num);
    			if(!map.containsKey(name2))
    				map.put(name2,++num);
    			dp[map.get(name1)][map.get(name2)] = 1;
    		}
    		for(int k = 1;k <= num;k++) 
    			for(int i = 1;i <= num;i++) 
    				for(int j = 1;j <= num;j++) 
    					dp[i][j] = Math.min(dp[i][j],dp[i][k] + dp[k][j]);
    		
    		int res = -0x3f3f3f3f;
    		for(int i = 1;i <= num;i++) 
    			for(int j = 1;j <= num;j++) 
    				res = (dp[i][j] < 0x3f3f3f3f) ? Math.max(res,dp[i][j]) : res;
    		System.out.println(res + 1);
    	}
    }
    

    题目链接:CodeForces505B


    这道题大意是说给一个n个点,m条边的无向图,首先设置点a到b之间的边的颜色c,然后有q次询问,问u到v有几种方法。假设1和3是不相连的,但是2分别连接1和3,要想从1通过2走到3,必须满足1,2之间边的颜色和2,3之间边的颜色相同

    水题,类floyd算法,三维数组dp[c][i][j]的值为1表示i到j有颜色为c的边,如果dp[c][i][j]的值为0,表示i到j没有颜色为c的边

    import java.util.Scanner;
    public class Main {
    
    	public static void main(String[] args) {
    		Scanner cin = new Scanner(System.in);
    		int n = cin.nextInt();
    		int m = cin.nextInt();
    		int maxc = -1;
    		int[][][] dp = new int[101][101][101];
    		for(int i = 0;i < m;i++) {
    			int a,b,c;
    			a = cin.nextInt();
    			b = cin.nextInt();
    			c = cin.nextInt();
    			maxc = Math.max(c,maxc);
    			dp[c][a][b] = dp[c][b][a] = 1;
    		}
    		
    		//floyd
    		for(int c = 1;c <= maxc;c++) //颜色
    			for(int k = 1;k <= n;k++) //中间点
    				for(int i = 1;i <= n;i++) //起始点
    					for(int j = 1;j <= n;j++) //终止点
    						//i和j之间没有颜色为c的连线 && i到k之间有颜色为c的连线 && k到j之间有颜色为c的连线
    						if(dp[c][i][j] == 0 && dp[c][i][k] != 0 && dp[c][k][j] != 0)
    							//则i到j之间就有颜色为c的连线
    							dp[c][i][j] = dp[c][i][j] = 1;
    		
    		int q = cin.nextInt();
    		while((q--) != 0) {
    			int u = cin.nextInt();
    			int v = cin.nextInt();
    			int ans = 0;
    			for(int i = 1;i <= maxc;i++)
    				ans += dp[i][u][v];
    			System.out.println(ans);
    		}
    	}
    }
    

    题目连接:CodeForces601A


    题目大意是说,有n个城镇,两两之间必有路相连,不是铁路就是公路(只能有一种路),现在汽车和火车同时从1出发,问最晚达到n的用时是多长。很简单,如果铁路直接将1和n相连,就去对公路进行floyd,反之就对铁路进行floyd

    import java.util.Scanner;
    public class Main {
    	public static int floyd(int[][] tmp,int n) {
    		for(int k = 1;k <= n;k++) {
    			for(int i = 1;i <= n;i++) {
    				for(int j = 1;j <= n;j++) {
    					//中间点和起点或者终点都不可连 
    	                if(tmp[i][k] == 0 || tmp[k][j] == 0) 
    	                	continue;
    	                //如果起点和终点不可连,那么一定更新 
    	                if(tmp[i][j] == 0) 
    	                	tmp[i][j] = tmp[i][k] + tmp[k][j];
    	                tmp[i][j] = Math.min(tmp[i][j],tmp[i][k] + tmp[k][j]); 
    				}
    			}
    		}
    		return tmp[1][n];
    	}
    	
    	public static void main(String[] args) {
    		Scanner cin = new Scanner(System.in);
    		int n = cin.nextInt();
    		int m = cin.nextInt();
    		int res;
    		int[][] huo = new int[n + 1][n + 1];
    		int[][] qi = new int[n + 1][n + 1];
    		for(int i = 0;i < m;i++) {
    			int a = cin.nextInt();
    			int b = cin.nextInt();
    			huo[a][b] = huo[b][a] = 1;
    		}
    		
    		if(huo[1][n] == 1) {//火车从1直达n
    			for(int i = 1;i <= n;i++) 
    				for(int j = 1;j <= n;j++)
    						qi[i][j] = 1 - huo[i][j];
    			//汽车floyd
    			res = floyd(qi,n);
    		} else //汽车1直达n
    			//火车floyd
    			res = floyd(huo,n);
    		
    		if(res == 0)
    			System.out.println(-1);
    		else
    			System.out.println(res);
    	}
    }
    
    展开全文
  • 这是图论中用来求解有向赋权图最短路径的Floyd算法的Matlab文件,已经封装成了函数,函数接口在代码中有说明。
  • C语言实现Floyd算法

    2020-08-28 08:59:45
    主要为大家详细介绍了C语言实现Floyd算法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • Floyd算法.rar

    2019-06-27 16:47:20
    Floyd算法又称为弗洛伊德算法,插点法,是一种用于寻找给定的加权图中顶点间最短路径的算法。
  • 任意两点间的最短路问题 Floyd算法 使用范围: 求每对顶点的最短路径; 有向图无向图和混合图; 算法思想: 直接在图的带权邻接矩阵中用插入顶点的方法依次递推地构造出n个矩阵D(1, D(2, , D(v, D(v)是图的距离矩阵, ...
  • Floyd算法模板

    2018-07-24 00:49:22
    求解多源最短路径的Floyd算法模板,数学建模竞赛必备。
  • 基于MATLAB的Floyd算法

    2014-05-14 20:37:20
    基于MATLAB的Floyd算法,计算网络中任意结点间的最小距离!
  • Floyd算法实现源码

    2020-03-08 12:59:33
    Floyd是数据结构中解决求解图中多源点最短路径问题的经典算法,文件中包括算法实现和详细分析,下载可直接运行调试,可供数据结构与算法课程的学习
  • floyd算法代码

    2019-02-13 12:48:18
    无向图的最短路径floyd算法实现,代码清晰。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 28,747
精华内容 11,498
关键字:

floyd算法