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] 
收起全文
精华内容
下载资源
问答
  • 2021-06-20 11:30:03

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

    只要图中不包含长度为负的回路,可用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算法直接使用二维数组求出所有顶点到所有顶点的最短路径。 D代表顶点到顶点的最短路径权值和的矩阵。 P代表对应顶点的最小路径的前驱矩阵。 以下程序在DEV C++中调试运行通过。 #include <stdio> #define ...
  • C语言实现Floyd算法

    2020-08-28 08:59:45
    主要为大家详细介绍了C语言实现Floyd算法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 本文实例讲述了Python基于Floyd算法求解最短路径距离问题。分享给大家供大家参考,具体如下: Floyd算法和Dijkstra算法,相信大家都不陌生,在最短路径距离的求解中应该算得上是最为基础和经典的两个算法了,今天就...
  • python实现Floyd算法

    2020-09-20 22:29:43
    主要为大家详细介绍了python实现Floyd算法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 主要使用了Dijkstra算法,Floyd算法。 主要功能有六项:1、烟台大学的平面图。2、景点的介绍。3、从一个景点到其他地方的所有最短路径。4、两景点间的最短路径。5、计算从一个地方到另一个地方所要花费的时间。6、...
  • 正如我们所知道的,Floyd算法用于求最短路径。Floyd算法可以说是Warshall算法的扩展,三个for循环就可以解决问题,所以它的时间复杂度为O(n^3)。 Floyd算法的基本思想如下:从任意节点A到任意节点B的最短路径不外乎2...
  • MATLAB中计算已知有向图、邻接矩阵情况下的最短路径
  • 算法与数据结构的结课课程的报告。参考文章加自己提炼。求解几个点之间的最短距离的算法。c++源码在vs2019可以实现,也比较好容易理解。希望有所帮助。没有要积分,因为我也是参考别人的。
  • 教科书上的Floyd算法只能输出path,无法给出具体的路径描述,本代码可以输出具体的路径选择
  • 使用了Floyd算法,求出了任意两点的距离矩阵和两点之间最短节点的矩阵,并用遗传算法创造四个父辈,对父辈遗传,且保持基因量相等,以最短空跑距离为适应度,筛选出最优秀的父辈子辈的其中有所有基因的四个。...
  • Floyd算法的应用研究

    2019-12-30 00:36:37
    Floyd算法的应用研究,周柳阳,,我国地域辽阔,气候多变,各种自然灾害频频发生,特别是每年在长江、淮河、嫩江等流域经常爆发不同程度的洪涝灾害。提前做好某种
  • 最短路问题的Floyd算法与MATLAB程序实现.pdf
  • Floyd算法又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法,与Dijkstra算法类似,对于有向的NP问题提供求解的方法。
  • 基于Floyd算法的社区服务中心的选址问题,梅索,毛洪振,本论文响应了刚刚结束的十七大的号召,讨论如何选择小区建立社区服务中心更好的方便小区居民。为了解决此问题,我们首先利用Lingo9
  • 算法-最短路径-Floyd算法
  • java实现Floyd算法

    2020-08-28 09:09:29
    主要为大家详细介绍了java实现Floyd算法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 最短路径的Dijkstra算法及Floyd算法
  • 针对中小城镇环境线网特点,用Floyd算法,以站点间的客流O-D分布为基本依据,在"逐条布线、优化成网"的方法基础上进行优化。通过在起终站点间插入重要节点,调整线路走向,从而改变线网运输的客流总量。避免了严格按照...
  • 实验四Floyd 算法 一实验 目的 利用MAT LAB 实现Floyd 算法可对输入的邻接距离矩阵计算图中任 意两点间的最短距离矩阵和路由矩阵且能查询任意两点间的最短距离 和路由 二实验原理 Floyd 算法适用于求解网络中的任意...
  • 图:FLoyd算法

    2014-08-04 13:36:34
    使用Floyd算法,求解点对之间的最短距离。图结构使用邻接矩阵存储。
  • Floyd-Warshall算法,又叫Floyd算法,用于求每对顶点之间最短路径
  • Floyd 算法 详细教程

    2014-10-27 18:15:48
    Floyd算法 详细介绍了Floyd算法的应用
  • 主要为大家详细介绍了Java实现Floyd算法求最短路径,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • Floyd算法.rar

    2019-06-27 16:47:20
    Floyd算法又称为弗洛伊德算法,插点法,是一种用于寻找给定的加权图中顶点间最短路径的算法。
  • floyd算法代码

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

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

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 31,745
精华内容 12,698
关键字:

floyd算法