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算法

    千次阅读 2015-06-07 18:00:19
    Floyd算法
    #include<stdio.h>
    #include<stdlib.h>
    #define MAXVEX 100      //最大顶点数
    typedef char VertexType;     //顶点
    typedef int EdgeType;   //权值
    #define INFINITY 65535      /*用65535来代表∞*/
    
    //Dist的存储结构
    typedef struct
    {
        int length; //当前最短路径长度
        int pre;    //路径最后经过的顶点
    }Dist;
    
    typedef struct
    {
        int from;   //边的始点
        int to; //边的终点
        EdgeType weight;    //权重
    }Edge;  //边的结构
    
    
    //图的结构
    typedef struct
    {
        int numVertex;  //顶点个数
        int numEdge;    //边的个数
        VertexType vexs[MAXVEX];    /*顶点表*/
        int Indegree[MAXVEX];   //顶点入度
        EdgeType arc[MAXVEX][MAXVEX];   //边表
        Dist D[MAXVEX][MAXVEX];
    }Graph;
    
    
    //初始化图
    void InitGraph(Graph * G,int numVert,int numEd )    //传入顶点个数,边数
    {
        G->numVertex=numVert;
        G->numEdge=numEd;
        for(int i=0;i<numVert;i++)
        {
            G->Indegree[i]=0;
            for(int j=0;j<numVert;j++)
            {
                G->arc[i][j]=INFINITY;
                if(i==j)
                {
                    G->arc[i][j]=0;
                }
            }
        }
        return ;
    }
    
    
    //判断是否为边
    bool IsEdge(Edge oneEdge)
    {
        if(oneEdge.weight>0 && oneEdge.weight!=INFINITY && oneEdge.to>=0)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    
    
    
    
    //建立有向图的邻接矩阵
    void CreatGraph(Graph * G)
    {
        int i,j,k,w;
        printf("请输入%d个顶点元素:\n",G->numVertex);
        for(i=0;i<G->numVertex;i++)
        {
            scanf(" %c",&G->vexs[i]);
        }
        for(k=0;k<G->numEdge;k++)
        {
            printf("请输入边(Vi,Vj)的下标Vi,Vj,和权重w:\n");
            scanf("%d%d%d",&i,&j,&w);
            G->Indegree[j]++;
            G->arc[i][j]=w;
        }
    }
    
    
    
    //返回顶点个数
    int VerticesNum(Graph * G)
    {
        return G->numVertex;
    }
    
    
    
    //返回依附于顶点的第一条边
    Edge FirstEdge(Graph * G,int oneVertex)
    {
        Edge firstEdge;
        firstEdge.from=oneVertex;
        for(int i=0;i<G->numVertex;i++)
        {
            if(G->arc[oneVertex][i]!=0 && G->arc[oneVertex][i]!=INFINITY)
            {
                firstEdge.to=i;
                firstEdge.weight=G->arc[oneVertex][i];
                break;
            }
    
        }
        return firstEdge;
    }   
    
    
    
    //返回oneEdge的终点
    int ToVertex(Edge oneEdge)
    {
        return oneEdge.to;
    }
    
    
    
    //返回与preEdge有相同顶点的下一条边
    Edge NextEdge(Graph * G,Edge preEdge)
    {
        Edge myEdge;
        myEdge.from=preEdge.from;   //边的始点与preEdge的始点相同
        if(preEdge.to<G->numVertex) //如果preEdge.to+1>=G->numVertex;将不存在下一条边
            for(int i=preEdge.to+1;i<G->numVertex;i++)  //找下一个arc[oneVertex][i]
            {                                           //不为0的i
                if(G->arc[preEdge.from][i]!=0 && G->arc[preEdge.from][i]!=INFINITY)
                {
                    myEdge.to=i;
                    myEdge.weight=G->arc[preEdge.from][i];
                    break;
                }
            }
            return myEdge;
    }
    
    
    
    //初始化Dist数组
    void Init_Dist(Graph * G)   
    {
        int i,j;
        for(i=0;i<G->numVertex;i++)
        {
            for(j=0;j<G->numVertex;j++)
            {
                if(i==j)
                {
                    G->D[i][j].length=0;
                    G->D[i][j].pre=i;
                }
                else
                {
                    G->D[i][j].length=INFINITY;
                    G->D[i][j].pre=-1;
                }
            }
        }
    }
    
    
    
    
    void Floyd(Graph * G)
    {
        int v;
        Init_Dist(G);   //初始化Dist数组
        for(v=0;v<G->numVertex;v++) 
        {
            for(Edge e=FirstEdge(G,v);IsEdge(e);e=NextEdge(G,e))
            {
                G->D[v][ToVertex(e)].length=e.weight;
                G->D[v][ToVertex(e)].pre=v;
            }
        }   //更改Dist数组的数据
    
        //顶点i到顶点j的路径经过顶点v,如果变短就改变Dist数组里的数据
        for(v=0;v<G->numVertex;v++)
        {
            for(int i=0;i<G->numVertex;i++)
            {
                for(int j=0;j<G->numVertex;j++)
                {
                    if(G->D[i][j].length>(G->D[i][v].length+G->D[v][j].length))
                    {
                        G->D[i][j].length=G->D[i][v].length+G->D[v][j].length;
                        G->D[i][j].pre=G->D[v][j].pre;
                    }
                }
            }
        }
    }
    
    
    //输出Dist数组
    void Print_Dist(Graph * G)
    {
        for(int i=0;i<G->numVertex;i++)
        {
            for(int j=0;j<G->numVertex;j++)
            {
                printf("elem:%c   length:%d   pre:%d\n",G->vexs[i],G->D[i][j].length,G->D[i][j].pre);
            }
        }
        printf("\n");
    }
    
    
    
    int main()
    {
        Graph G;
        int numVert,numEd;
        printf("请输入顶点数和边数:\n");
        scanf("%d%d",&numVert,&numEd);
        InitGraph(&G,numVert,numEd);
        CreatGraph(&G);
        Floyd(&G);
        Print_Dist(&G);
        return 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算法 Floyd算法

    2010-10-28 19:34:49
    中国数学建模-数学工具-Floyd最短路算法的MATLAB程序 wh-ee 重登录 隐身 用户控制面板 搜索 风格 论坛状态 论坛展区 社区服务 社区休闲 网站首页 退出 >> Matlab,Mathematica,maple,几何画板,word,sas,spss......
  • Floyd 算法

    2013-04-28 23:49:24
    Floyd算法可以说是Warshall算法的扩展,三个for循环就可以解决问题,所以它的时间复杂度为O(n^3)。 Floyd算法的基本思想如下:从任意节点A到任意节点B的最短路径不外乎2种可能,1是直接从A到B,2是从A经过若干个...

    点击打开链接

    正如我们所知道的,Floyd算法用于求最短路径。Floyd算法可以说是Warshall算法的扩展,三个for循环就可以解决问题,所以它的时间复杂度为O(n^3)。

    Floyd算法的基本思想如下:从任意节点A到任意节点B的最短路径不外乎2种可能,1是直接从A到B,2是从A经过若干个节点X到B。所以,我们假设Dis(AB)为节点A到节点B的最短路径的距离,对于每一个节点X,我们检查Dis(AX) + Dis(XB) < Dis(AB)是否成立,如果成立,证明从A到X再到B的路径比A直接到B的路径短,我们便设置Dis(AB) = Dis(AX) + Dis(XB),这样一来,当我们遍历完所有节点X,Dis(AB)中记录的便是A到B的最短路径的距离。

    很简单吧,代码看起来可能像下面这样:

    for ( int i = 0; i < 节点个数; ++i )
    {
    for(int j = 0; j < 节点个数; ++j )
    {
    for(int k = 0; k < 节点个数; ++k )
    {
    if( Dis[i][k] + Dis[k][j] < Dis[i][j] )
    {
    // 找到更短路径
    Dis[i][j] = Dis[i][k] + Dis[k][j];
    }
    }
    }
    }

    但是这里我们要注意循环的嵌套顺序,如果把检查所有节点X放在最内层,那么结果将是不正确的,为什么呢?因为这样便过早的把i到j的最短路径确定下来了,而当后面存在更短的路径时,已经不再会更新了。

    让我们来看一个例子,看下图:

    图中红色的数字代表边的权重。如果我们在最内层检查所有节点X,那么对于A->B,我们只能发现一条路径,就是A->B,路径距离为9。而这显然是不正确的,真实的最短路径是A->D->C->B,路径距离为6。造成错误的原因就是我们把检查所有节点X放在最内层,造成过早的把A到B的最短路径确定下来了,当确定A->B的最短路径时Dis(AC)尚未被计算。所以,我们需要改写循环顺序,如下:

    for ( int k = 0; k < 节点个数; ++k )
    {
    for(int i = 0; i < 节点个数; ++i )
    {
    for(int j = 0; j < 节点个数; ++j )
    {
    if( Dis[i][k] + Dis[k][j] < Dis[i][j] )
    {
    // 找到更短路径
    Dis[i][j] = Dis[i][k] + Dis[k][j];
    }
    }
    }
    }

    这样一来,对于每一个节点X,我们都会把所有的i到j处理完毕后才继续检查下一个节点。

    那么接下来的问题就是,我们如何找出最短路径呢?这里需要借助一个辅助数组Path,它是这样使用的:Path(AB)的值如果为P,则表示A节点到B节点的最短路径是A->...->P->B。这样一来,假设我们要找A->B的最短路径,那么就依次查找,假设Path(AB)的值为P,那么接着查找Path(AP),假设Path(AP)的值为L,那么接着查找Path(AL),假设Path(AL)的值为A,则查找结束,最短路径为A->L->P->B。

    那么,如何填充Path的值呢?很简单,当我们发现Dis(AX) + Dis(XB) < Dis(AB)成立时,就要把最短路径改为A->...->X->...->B,而此时,Path(XB)的值是已知的,所以,Path(AB) = Path(XB)。

    好了,基本的介绍完成了,接下来就是实现的时候了,这里我们使用图以及邻接矩阵:

    #define INFINITE 1000 // 最大值
    #define MAX_VERTEX_COUNT 20   // 最大顶点个数
    //
    structGraph
    {
    intarrArcs[MAX_VERTEX_COUNT][MAX_VERTEX_COUNT];// 邻接矩阵
    intnVertexCount;   // 顶点数量
    intnArcCount;   // 边的数量
    };
    //

    首先,我们写一个方法,用于读入图的数据:

    void readGraphData( Graph *_pGraph )
    {
    std::cout <<"请输入顶点数量和边的数量: ";
    std::cin >> _pGraph->nVertexCount;
    std::cin >> _pGraph->nArcCount;
    std::cout <<"请输入邻接矩阵数据:"<< std::endl;
    for(int row = 0; row < _pGraph->nVertexCount; ++row )
    {
    for(int col = 0; col < _pGraph->nVertexCount; ++col )
    {
    std::cin >> _pGraph->arrArcs[row][col];
    }
    }
    }

    接着,就是核心的Floyd算法:

    void floyd( int _arrDis[][MAX_VERTEX_COUNT],int_arrPath[][MAX_VERTEX_COUNT],int_nVertexCount )
    {
    // 先初始化_arrPath
    for(int i = 0; i < _nVertexCount; ++i )
    {
    for(int j = 0; j < _nVertexCount; ++j )
    {
    _arrPath[i][j] = i;
    }
    }
    //
    for(int k = 0; k < _nVertexCount; ++k )
    {
    for(int i = 0; i < _nVertexCount; ++i )
    {
    for(int j = 0; j < _nVertexCount; ++j )
    {
    if( _arrDis[i][k] + _arrDis[k][j] < _arrDis[i][j] )
    {
    // 找到更短路径
    _arrDis[i][j] = _arrDis[i][k] + _arrDis[k][j];
    _arrPath[i][j] = _arrPath[k][j];
    }
    }
    }
    }
    }

    OK,最后是输出结果数据代码:

    void printResult( int _arrDis[][MAX_VERTEX_COUNT], int _arrPath[][MAX_VERTEX_COUNT], int _nVertexCount )
    {
    std::cout <<"Origin -> Dest Distance Path"<< std::endl;
    for(int i = 0; i < _nVertexCount; ++i )
    {
    for(int j = 0; j < _nVertexCount; ++j )
    {
    if( i != j )// 节点不是自身
    {
    std::cout << i+1 <<" -> "<< j+1 << "\t\t";
    if( INFINITE == _arrDis[i][j] )// i -> j 不存在路径
    {
    std::cout <<"INFINITE"<< "\t\t";
    }
    else
    {
    std::cout << _arrDis[i][j] <<"\t\t";
    // 由于我们查询最短路径是从后往前插,因此我们把查询得到的节点
    // 压入栈中,最后弹出以顺序输出结果。
    std::stack<int> stackVertices;
    intk = j;
    do
    {
    k = _arrPath[i][k];
    stackVertices.push( k );
    }while( k != i );
    //
    std::cout << stackVertices.top()+1;
    stackVertices.pop();
    unsignedintnLength = stackVertices.size();
    for( unsignedintnIndex = 0; nIndex < nLength; ++nIndex )
    {
    std::cout <<" -> "<< stackVertices.top()+1;
    stackVertices.pop();
    }
    std::cout <<" -> "<< j+1 << std::endl;
    }
    }
    }
    }
    }

    好了,是时候测试了,我们用的图如下:

    测试代码如下:

    int main( void )
    {
    Graph myGraph;
    readGraphData( &myGraph );
    //
    intarrDis[MAX_VERTEX_COUNT][MAX_VERTEX_COUNT];
    intarrPath[MAX_VERTEX_COUNT][MAX_VERTEX_COUNT];
    // 先初始化arrDis
    for(int i = 0; i < myGraph.nVertexCount; ++i )
    {
    for(int j = 0; j < myGraph.nVertexCount; ++j )
    {
    arrDis[i][j] = myGraph.arrArcs[i][j];
    }
    }
    floyd( arrDis, arrPath, myGraph.nVertexCount );
    //
    printResult( arrDis, arrPath, myGraph.nVertexCount );
    //
    system("pause");
    return0;
    }

    如图:

    展开全文
  • FLOYD算法

    2018-07-12 11:10:49
    #include&lt;iostream&gt; #include&lt;cstdio&gt; using namespace std;...const int INF = 0x3f3f3f3f;... int e[10][10] = { 0 }, dis[10], book[10], i, j, k, n, m, t1, t2, t3;...
    #include<iostream>
    #include<cstdio>
    using namespace std;
    const int INF = 0x3f3f3f3f;
    int main(void)
    {
    	int e[10][10] = { 0 }, dis[10], book[10], i, j, k, n, m, t1, t2, t3;
    	cout << "本程序演示Floyd算法" << endl;
    	cout << "请输入顶点数和边数:";
    	cin >> n >> m;
    	for (i = 1; i <= n; i++)
    		for (j = 1; j <= n; j++)
    			if (i != j)
    				e[i][j] = INF;
    	cout << "下面请输入权重数据";
    	for (i = 1; i <= m; i++)
    	{
    		cin >> t1 >> t2 >> t3;
    		e[t1][t2] = t3;
    	}
    	for (k = 1; k <= n; k++)
    		for (i = 1; i <= n; i++)
    			for (j = 1; j <= n; j++)
    				if (e[i][j]>e[i][k] + e[k][j])
    					e[i][j] = e[i][k] + e[k][j];
    	cout << "下面输出多源最短路径" << endl;
    	for (i = 1; i <= n; i++)
    	{
    		for (j = 1; j <= n; j++)
    		{
    			cout << e[i][j] << " ";
    		}
    		cout << endl;
    	}
    	return 0;
    }
    

    展开全文

空空如也

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

floyd算法