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] 
收起全文
精华内容
下载资源
问答
  • Floyd算法

    2019-01-12 13:52:20
    Floyd算法
                   

     弗洛伊德(Floyd)算法过程:
    1、用D[v][w]记录每一对顶点的最短距离。
    2、依次扫描每一个点,并以其为基点再遍历所有每一对顶点D[][]的值,看看是否可用过该基点让这对顶点间的距离更小。


    算法理解:
    最短距离有三种情况:
    1、两点的直达距离最短。(如下图<v,x>)
    2、两点间只通过一个中间点而距离最短。(图<v,u>)
    3、两点间用通过两各以上的顶点而距离最短。(图<v,w>)

    对于第一种情况:在初始化的时候就已经找出来了且以后也不会更改到。
    对于第二种情况:弗洛伊德算法的基本操作就是对于每一对顶点,遍历所有其它顶点,看看可否通过这一个顶点让这对顶点距离更短,也就是遍历了图中所有的三角形(算法中对同一个三角形扫描了九次,原则上只用扫描三次即可,但要加入判断,效率更低)。
    对于第三种情况:如下图的五边形,可先找一点(比如x,使<v,u>=2),就变成了四边形问题,再找一点(比如y,使<u,w>=2),可变成三角形问题了(v,u,w),也就变成第二种情况了,由此对于n边形也可以一步步转化成四边形三角形问题。(这里面不用担心哪个点要先找哪个点要后找,因为找了任一个点都可以使其变成(n-1)边形的问题)。

     

    刺猬加注:

    floyd的核心代码:

     

    for (k=0;k<g.vexnum;k++)
    ...{
        
    for (i=0;i<g.vexnum;i++)
        
    ...{
            
    for (j=0;j<g.vexnum;j++)
            
    ...{
                
    if (distance[i][j]>distance[i][k]+distance[k][j])
                
    ...{
                    distance[i][j]
    =distance[i][k]+distance[k][j];
                }

            }

        }

    }


    结合代码 并参照上图所示 我们来模拟执行下 这样才能加深理解:
    第一关键步骤:当k执行到x,i=v,j=u时,计算出v到u的最短路径要通过x,此时v、u联通了。
    第二关键步骤:当k执行到u,i=v,j=y,此时计算出v到y的最短路径的最短路径为v到u,再到y(此时v到u的最短路径上一步我们已经计算过来,直接利用上步结果)。
    第三关键步骤:当k执行到y时,i=v,j=w,此时计算出最短路径为v到y(此时v到y的最短路径长在第二步我们已经计算出来了),再从y到w。

    依次扫描每一点(k),并以该点作为中介点,计算出通过k点的其他任意两点(i,j)的最短距离,这就是floyd算法的精髓!同时也解释了为什么k点这个中介点要放在最外层循环的原因.

               

    再分享一下我老师大神的人工智能教程吧。零基础!通俗易懂!风趣幽默!还带黄段子!希望你也加入到我们人工智能的队伍中来!https://blog.csdn.net/jiangjunshow

    展开全文
  • 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);
    	}
    }
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,812
精华内容 3,924
关键字:

floyd算法