精华内容
参与话题
问答
  • Floyd算法 Floyd算法

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

    2013-04-20 14:01:56
    使用c语言,基于win32的工程,实现从文件读取弧段到图,然后实现Dijskra算法和floyd算法,并将结果写入txt文件
  • 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算法 matlab 实例 动态规划
  • DiskStra算法: 求单源最短路径,即求一个顶点到任意顶点的最短路径,其时间复杂度为O(V*V) 如图所示:求顶点0到各顶点之间的最短路径 代码实现: #include<stdio.h> #include&l...

    最短路径:

    在一个带权图中,顶点V0到图中任意一个顶点Vi的一条路径所经过边上的权值之和,定义为该路径的带权路径长度,把带权路径最短的那条路径称为最短路径。

    DiskStra算法:

    求单源最短路径,即求一个顶点到任意顶点的最短路径,其时间复杂度为O(V*V)

    如图所示:求顶点0到各顶点之间的最短路径

    代码实现:

    #include<stdio.h>
    #include<stdlib.h>
    #define MaxVexNum 50
    #define MaxInt 32767
    #define MaxEdgeNum 50
    //邻接矩阵
    typedef int VertexType;
    typedef int EdgeType;
    typedef struct AMGraph{
    	VertexType vexs[MaxVexNum];//顶点表 
    	EdgeType arcs[MaxVexNum][MaxVexNum];//邻接矩阵表 
    	int vexnum,edgenum;//顶点数,边数 
    }AMGraph; 
    
    void createGraph(AMGraph &g){//创建无向图 
    	printf("请输入顶点数:");
    	scanf("%d",&g.vexnum);
    	printf("\n请输入边数:");
    	scanf("%d",&g.edgenum);
    	
    	//初始化顶点表 
    	for(int i=0;i<g.vexnum;i++){
    		g.vexs[i]=i; 
    	} 
    	for(int i=0;i<g.vexnum;i++){
    		for(int j=0;j<g.vexnum;j++){
    			g.arcs[i][j]=MaxInt;
    			if(i==j) g.arcs[i][j]=0;
    		}
    	} 
    	printf("请输入边的信息以及边的权值(顶点是0~n-1)\n");
    	for(int i=0;i<g.edgenum;i++){
    		int x,y,w;
    		scanf("%d%d%d",&x,&y,&w);
    		g.arcs[x][y]=w;
    		//g.arcs[y][x]=w;
    	}
    }
    void PrintGraph(AMGraph g){
    	printf("邻接矩阵为:\n");
    	for(int i=0;i<g.vexnum;i++) {
    		printf("  %d",g.vexs[i]);
    	}
    	printf("\n");
    	for(int i=0;i<g.vexnum;i++){
    		printf("%d ",g.vexs[i]);
    		for(int j=0;j<g.vexnum;j++){
    			if(g.arcs[i][j]==32767){
    				printf("∞ "); 
    			}else{
    				printf("%d  ",g.arcs[i][j]);
    			}	
    		}
    		printf("\n");
    	} 
    }
    //Dijkstra算法,求单源最短路径
    void Dijkstra(AMGraph g,int dist[],int path[],int v0){
    	int n=g.vexnum,v;
    	int set[n];//set数组用于记录该顶点是否归并 
    	//第一步:初始化 
    	for(int i=0;i<n;i++){
    		set[i]=0;
    		dist[i]=g.arcs[v0][i];
    		if(dist[i]<MaxInt){//若距离小于MaxInt说明两点之间有路可通 
    			path[i]=v0;//则更新路径i的前驱为v 
    		}else{
    			path[i]=-1; //表示这两点之间没有边
    		 } 
    	}
    	set[v0]=1;//将初始顶点并入 
    	path[v0]=-1;//初始顶点没有前驱
    	
    	//第二步 
    	for(int i=1;i<n;i++){//共n-1个顶点 
    		int min=MaxInt;
    		//第二步:从i=1开始依次选一个距离顶点的最近顶点 
    		for(int j=0;j<n;j++){
    			if(set[j]==0&&dist[j]<min){
    				v=j;
    				min=dist[j];
    		}
    	}
    	//将顶点并入 
    	set[v]=1;	
    	//第三步:在将新结点并入后,其初始顶点v0到各顶点的距离将会发生变化,所以需要更新dist[]数组
    	for(int j=0;j<n;j++){
    		if(set[j]==0&&dist[v]+g.arcs[v][j]<dist[j]){
    			dist[j]=dist[v]+g.arcs[v][j];
    			path[j]=v;
    		}
    	} 	
     } 
     //输出 
     printf("       ");
     for(int i=0;i<n;i++) printf("%d  ",i);
      
     printf("\ndist[]:");
     for(int i=0;i<n;i++) printf("%d  ",dist[i]);
     
     printf("\npath[]:");
     for(int i=0;i<n;i++) printf("%d  ",path[i]);
    
    }
    
    int main(){
    	AMGraph g;
    	createGraph(g);
    	int dist[g.vexnum];
    	int path[g.vexnum];
    	Dijkstra(g,dist,path,0);
    } 

    Floyd算法:

    求各顶点之间的最短路径,其时间复杂度为O(V*V*V)

    如图所示,求<1,0>之间的最短路径:

    代码实现:

    #include<stdio.h>
    #include<stdlib.h>
    #define MaxVexNum 50
    #define MaxInt 32767
    #define MaxEdgeNum 50
    //邻接矩阵
    typedef int VertexType;
    typedef int EdgeType;
    typedef struct AMGraph{
    	VertexType vexs[MaxVexNum];//顶点表 
    	EdgeType arcs[MaxVexNum][MaxVexNum];//邻接矩阵表 
    	int vexnum,edgenum;//顶点数,边数 
    }AMGraph; 
    
    void createGraph(AMGraph &g){//创建无向图 
    	printf("请输入顶点数:");
    	scanf("%d",&g.vexnum);
    	printf("\n请输入边数:");
    	scanf("%d",&g.edgenum);
    	
    	//初始化顶点表 
    	for(int i=0;i<g.vexnum;i++){
    		g.vexs[i]=i; 
    	} 
    	for(int i=0;i<g.vexnum;i++){
    		for(int j=0;j<g.vexnum;j++){
    			g.arcs[i][j]=MaxInt;
    			if(i==j) g.arcs[i][j]=0;
    		}
    	} 
    	printf("请输入边的信息以及边的权值(顶点是0~n-1)\n");
    	for(int i=0;i<g.edgenum;i++){
    		int x,y,w;
    		scanf("%d%d%d",&x,&y,&w);
    		g.arcs[x][y]=w;
    		//g.arcs[y][x]=w;
    	}
    }
    void PrintGraph(AMGraph g){
    	printf("邻接矩阵为:\n");
    	for(int i=0;i<g.vexnum;i++) {
    		printf("  %d",g.vexs[i]);
    	}
    	printf("\n");
    	for(int i=0;i<g.vexnum;i++){
    		printf("%d ",g.vexs[i]);
    		for(int j=0;j<g.vexnum;j++){
    			if(g.arcs[i][j]==32767){
    				printf("∞ "); 
    			}else{
    				printf("%d  ",g.arcs[i][j]);
    			}	
    		}
    		printf("\n");
    	} 
    }
    
    //Floyd算法
    
    //递归输出两个顶点直接最短路径 
    void printPath(int u,int v,int path[][MaxVexNum]){
    	if(path[u][v]==-1){
    		printf("[%d %d] ",u,v);
    	}else{
    		int mid=path[u][v];
    		printPath(u,mid,path);
    		printPath(mid,v,path);
    	}
    }
    void Floyd(AMGraph g,int path[][MaxVexNum]){
    	int n=g.vexnum;
    	int A[n][n];
    	//第一步:初始化path[][]和A[][]数组 
    	for(int i=0;i<n;i++){
    		for(int j=0;j<n;j++){
    			A[i][j]=g.arcs[i][j];
    			path[i][j]=-1; 
    		}
    	}
    	//第二步:三重循环,寻找最短路径 
    	for(int v=0;v<n;v++){//第一层是代表中间结点 
    		for(int i=0;i<n;i++){
    			for(int j=0;j<n;j++){
    				if(A[i][j]>A[i][v]+A[v][j]){
    					A[i][j]=A[i][v]+A[v][j];
    					path[i][j]=v;
    				}
    			}
    		} 
    	} 
    } 
     
    int main(){
    	AMGraph g;
    	createGraph(g);
    	PrintGraph(g);
    	int path[MaxVexNum][MaxVexNum];
    	Floyd(g,path);
    
    	printPath(1,0,path);
    } 

    代码运行截图:

    展开全文
  • Floyd.cpp Floyd算法

    2020-10-13 15:52:19
    最短路Floyd算法Floyd算法(Floyd-Warshallalgorithm)又称为弗洛伊德算法、插点法,是解决给定的加权图中顶点间的最短路径的一种算法,可以正确处理有向图或负权的最短路径问题,同时也被用于计算有向图的传递闭包。
  • Dijkstra算法与Floyd算法

    2017-11-19 22:14:56
    最短路径—Dijkstra算法和Floyd算法 注意:以下代码 只是描述思路,没有测试过!!   Dijkstra算法 1.定义概览 Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短...

    最短路径—Dijkstra算法和Floyd算法

     

    注意:以下代码 只是描述思路,没有测试过!!

     

    Dijkstra算法

    1.定义概览

    Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。注意该算法要求图中不存在负权边。

    问题描述:在无向图 G=(V,E) 中,假设每条边 E[i] 的长度为 w[i],找到由顶点 V0 到其余各点的最短路径。(单源最短路径)

     

    2.算法描述

    1)算法思想:设G=(V,E)是一个带权有向图,把图中顶点集合V分成两组,第一组为已求出最短路径的顶点集合(用S表示,初始时S中只有一个源点,以后每求得一条最短路径 , 就将加入到集合S中,直到全部顶点都加入到S中,算法就结束了),第二组为其余未确定最短路径的顶点集合(用U表示),按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中,总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外,每个顶点对应一个距离,S中的顶点的距离就是从v到此顶点的最短路径长度,U中的顶点的距离,是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

    2)算法步骤:

    a.初始时,S只包含源点,即S={v},v的距离为0。U包含除v外的其他顶点,即:U={其余顶点},若v与U中顶点u有边,则<u,v>正常有权值,若u不是v的出边邻接点,则<u,v>权值为∞。

    b.从U中选取一个距离v最小的顶点k,把k,加入S中(该选定的距离就是v到k的最短路径长度)。

    c.以k为新考虑的中间点,修改U中各顶点的距离;若从源点v到顶点u的距离(经过顶点k)比原来距离(不经过顶点k)短,则修改顶点u的距离值,修改后的距离值的顶点k的距离加上边上的权。

    d.重复步骤b和c直到所有顶点都包含在S中。

     

    执行动画过程如下图

     

    3.算法代码实现:

     

    复制代码
    const int  MAXINT = 32767;
    const int MAXNUM = 10;
    int dist[MAXNUM];
    int prev[MAXNUM];
    
    int A[MAXUNM][MAXNUM];
    
    void Dijkstra(int v0)
    {
        bool S[MAXNUM];                                  // 判断是否已存入该点到S集合中
          int n=MAXNUM;
        for(int i=1; i<=n; ++i)
        {
            dist[i] = A[v0][i];
            S[i] = false;                                // 初始都未用过该点
            if(dist[i] == MAXINT)    
                  prev[i] = -1;
            else 
                  prev[i] = v0;
         }
         dist[v0] = 0;
         S[v0] = true;   
        for(int i=2; i<=n; i++)
        {
             int mindist = MAXINT;
             int u = v0;                               // 找出当前未使用的点j的dist[j]最小值
             for(int j=1; j<=n; ++j)
                if((!S[j]) && dist[j]<mindist)
                {
                      u = j;                             // u保存当前邻接点中距离最小的点的号码 
                      mindist = dist[j];
                }
             S[u] = true; 
             for(int j=1; j<=n; j++)
                 if((!S[j]) && A[u][j]<MAXINT)
                 {
                     if(dist[u] + A[u][j] < dist[j])     //在通过新加入的u点路径找到离v0点更短的路径  
                     {
                         dist[j] = dist[u] + A[u][j];    //更新dist 
                         prev[j] = u;                    //记录前驱顶点 
                      }
                  }
         }
    }
    复制代码

     

    4.算法实例

    先给出一个无向图

    用Dijkstra算法找出以A为起点的单源最短路径步骤如下

     

    Floyd算法

    1.定义概览

    Floyd-Warshall算法(Floyd-Warshall algorithm)是解决任意两点间的最短路径的一种算法,可以正确处理有向图或负权的最短路径问题,同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为O(N3),空间复杂度为O(N2)。

     

    2.算法描述

    1)算法思想原理:

         Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话,首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题,我们需要为这个目标重新做一个诠释(这个诠释正是动态规划最富创造力的精华所在)

          从任意节点i到任意节点j的最短路径不外乎2种可能,1是直接从i到j,2是从i经过若干个节点k到j。所以,我们假设Dis(i,j)为节点u到节点v的最短路径的距离,对于每一个节点k,我们检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立,如果成立,证明从i到k再到j的路径比i直接到j的路径短,我们便设置Dis(i,j) = Dis(i,k) + Dis(k,j),这样一来,当我们遍历完所有节点k,Dis(i,j)中记录的便是i到j的最短路径的距离。

    2).算法描述:

    a.从任意一条单边路径开始。所有两点之间的距离是边的权,如果两点之间没有边相连,则权为无穷大。   

    b.对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。

    3).Floyd算法过程矩阵的计算—-十字交叉法

    方法:两条线,从左上角开始计算一直到右下角 如下所示

    给出矩阵,其中矩阵A是邻接矩阵,而矩阵Path记录u,v两点之间最短路径所必须经过的点

    相应计算方法如下:

    最后A3即为所求结果

     

    3.算法代码实现

    复制代码
    typedef struct          
    {        
        char vertex[VertexNum];                                //顶点表         
        int edges[VertexNum][VertexNum];                       //邻接矩阵,可看做边表         
        int n,e;                                               //图中当前的顶点数和边数         
    }MGraph; 
    
    void Floyd(MGraph g) {   int A[MAXV][MAXV];   int path[MAXV][MAXV];   int i,j,k,n=g.n;   for(i=0;i<n;i++)   for(j=0;j<n;j++)   {    A[i][j]=g.edges[i][j];    path[i][j]=-1;   }   for(k=0;k<n;k++)   {   for(i=0;i<n;i++)   for(j=0;j<n;j++)   if(A[i][j]>(A[i][k]+A[k][j]))   {
      A[i][j]
    =A[i][k]+A[k][j];   path[i][j]=k;   }  }
    }
    复制代码

    算法时间复杂度:O(n3)

    66
    1

    « 上一篇:最小生成树-Prim算法和Kruskal算法
    » 下一篇:贪心算法
        </div>
        <p class="postfoot">
            posted on <span id="post-date">2012-07-31 12:37</span> <a href="http://www.cnblogs.com/biyeymyhjob/">as_</a> 阅读(<span id="post_view_count">401900</span>) 评论(<span id="post_comment_count">41</span>)  <a href="https://i.cnblogs.com/EditPosts.aspx?postid=2615833" rel="nofollow">编辑</a> <a href="#" onclick="AddToWz(2615833);return false;">收藏</a>
        </p>
    </div>
    <script type="text/javascript">var allowComments=true,cb_blogId=122253,cb_entryId=2615833,cb_blogApp=currentBlogApp,cb_blogUserGuid='c874d6d3-41cb-e111-aa3f-842b2b196315',cb_entryCreatedDate='2012/7/31 12:37:00';loadViewCount(cb_entryId);var cb_postType=1;</script>
    
    </div><a name="!comments"></a><div id="blog-comments-placeholder"><div id="comments_pager_top"></div>
    

    评论

    #1楼   

    good
    http://pic.cnblogs.com/face/508792/20130325095912.png
    2014-03-04 17:45 | ☆y急速の灵感 ★  

    #2楼   

    楼主讲的很精辟,好文章
    http://pic.cnblogs.com/face/u264690.bmp
    2014-04-01 15:19 | 晓O(∩_∩)O~  

    #3楼   

    如此的详细
    http://pic.cnblogs.com/face/584151/20131120141849.png
    2014-08-04 20:27 | 阿鲁巴  

    #4楼   

    给赞!
    2014-08-12 14:44 | silent_coder  

    #5楼   

    强大,赞
    http://pic.cnblogs.com/face/608121/20140227211824.png
    2014-10-23 15:01 | 千叶树  

    #6楼   

    能否转载?写的好详细!!
    以前学的忘了,现在看看觉得好有道理!
    http://pic.cnblogs.com/face/632767/20141029231741.png
    2014-11-05 19:07 | Godfray  

    #7楼[楼主]   

    @ Godfray
    哈哈 记得标明出处吧
    http://pic.cnblogs.com/face/u426620.jpg?id=11183206
    2014-11-17 14:25 | as_  

    #8楼   

    结合代码总算看懂了Dijkstra算法~
    2014-11-29 16:14 | qinggeouye  

    #9楼   

    竟然可以讲的如此明白
    2014-12-02 16:12 | pppanda  

    #10楼   

    算法原理那里,2(是从i经过若干个节点k到j)好像不等价于Dis(i,k) + Dis(k,j) < Dis(i,j)吧?
    2015-04-03 20:33 | yeshen  

    #11楼   

    @ 月下凉
    这句话只是在判断这个点有没有用过,并且,这个点还是可以走的。而且你说的那个例子,我完全没看懂,能不能详细的说下,是为什么?是怎么个走法???还是菜菜,希望解释下,好学习学习!
    2015-08-03 15:16 | 梁小猪  

    #12楼   

    mark
    2015-08-04 16:52 | alex_cool  

    #13楼   

    写的很好很详细,不过Dijikstra的算法步骤第二步和第三步交换一下顺序应该更好,把除V0外的距离都初始化为MAXINT,第一步把V0加入S中,以V0为中间点计算修改U中各顶点的距离(原步骤3),然后从中选择距离最小的顶点为新的中间点,加入S中(原步骤2),重复步骤2和步骤3。这是一个递归的过程,这样感觉更顺,与动画也更贴切。另外,我水平比较低,不过,数组真的没越界吗???
    2015-09-16 21:28 | 营养不良的红  

    #14楼   

    话不多说,一个字,好!
    2015-11-18 13:08 | 屌丝改变世界  

    #15楼   

    不得不顶!
    2015-12-29 15:55 | 阿水  

    #16楼   

    很清晰
    http://pic.cnblogs.com/face/636799/20150907113508.png
    2015-12-31 22:07 | xiaoluo91  

    #17楼   

    请问可以转载吗?
    2016-01-04 03:22 | lamlamM  

    #18楼   

    http://pic.cnblogs.com/face/741325/20150407174308.png
    2016-03-04 12:55 | 鼬与轮回  

    #19楼   

    有一个疑问,Dijkstra其实就是贪心算法的思想吧???
    http://pic.cnblogs.com/face/919841/20160323111700.png
    2016-03-25 09:40 | Sampson-9  

    #20楼   

    代码你跑通了吗就发上来,不像个程序员
    2016-04-04 22:10 | gouxake  

    #21楼[楼主]   

    @ gouxake
    不好意思 这代码是在校期间写的
    另外代码根本没有跑过 我当时原本目的想写伪代码描述思路而已

    至于具体代码 作为个程序员 自己实现个也不困难吧
    http://pic.cnblogs.com/face/u426620.jpg?id=11183206
    2016-05-06 14:05 | as_  

    #22楼   

    博主写的这篇博客,真的是太他妈好了。
    2016-05-24 15:26 | keyeechen  

    #23楼   

    楼主,讲的简单直白!怒赞,想问一下楼主的动态图是用什么画的了?
    2016-06-23 11:17 | 愤怒的小菜鸟~.~  

    #24楼   

    很好,谢谢楼主,画的非常直观
    2016-07-13 15:21 | 编程萝卜  

    #25楼   

    讲的很好啊,思路清晰,而且事无巨细,搂住棒棒哒~
    2016-09-09 12:04 | 莲动似是故人来  

    #26楼   

    我只想说一句话,本来我没有注册博客园帐号。
    我注册的目的就是想给博主点个赞��
    2016-09-14 23:03 | EsLion  

    #27楼   

    楼主, 这个判断if((!S[j]) && dist[j]<mindist)可不可以改成if( !S[j] && map[u][j] < Max )?
    2016-09-15 15:31 | FriskyPuppy  

    #28楼   

    请问在Dijkstra算法示例中,将D、E 之间的权重改为5或者6以上的数字,会影响最短路径的结果么? 小弟在推算过程中感觉改变这个值对结果没有影响。如果是这样的话那就不是最短路径了。 有可能是我推算的有问题。 望大神解答
    2016-09-17 17:20 | forwardX  

    #29楼   

    @ yeshen
    这是个类似动态规划的过程,在O(n^3)的运算过程中一定可以把局部最优解处理为全局最优解。。。因为局部最优是全局最优的必要条件。。。
    http://pic.cnblogs.com/face/788097/20150925163550.png
    2016-11-15 22:37 | woodenhead  

    #30楼   

    感谢博主! 但Dijkstra算法的动画图好像有一个错误:在以3为中间点判断到4的最短路径时应该时22>9+11,动画里好像写反了;)
    http://pic.cnblogs.com/face/1072319/20161129230024.png
    2016-11-30 16:56 | 李秋豪  

    #31楼   

    感谢博主,辛苦了。
    2016-12-28 16:39 | Griezmann  

    #32楼   

    可以注册账号来感谢你的动态图,及其他,谢谢
    2017-05-04 16:59 | SuvanCheng  

    #33楼   

    http://pic.cnblogs.com/face/789826/20170208092208.png
    2017-05-22 16:21 | 刘毅(Limer)  

    #34楼   

    刚刚学习算法,不大懂啊,要不要先看看凸轮的知识。。。
    http://pic.cnblogs.com/face/1176586/20170905173945.png
    2017-07-19 15:40 | YJLAugus  

    #35楼   

    感谢分享
    2017-07-28 20:56 | 噗_嗤  

    #36楼   

    博主 我觉得你写Floyd算法的时候 上面文字说的清楚 但是下面的矩阵演示就不清楚了 没有说明每一步划线的含义 只是告诉我们怎么做是不够的
    2017-08-02 09:50 | 剩余的明天  

    #37楼   

    最看不起这种用了别人的东西却不注明出处的人!
    2017-08-04 09:04 | yogurtice22yogadance  

    #38楼   

    @ Sampson-9
    对,弗洛伊德的思想是动态规划
    http://pic.cnblogs.com/face/1215839/20171005220935.png
    2017-08-13 20:20 | Hammer_cwz_77  

    #39楼   

    @ yogurtice22yogadance
    你写的?你连博客都没有。
    http://pic.cnblogs.com/face/1215839/20171005220935.png
    2017-08-13 20:26 | Hammer_cwz_77  

    #40楼   

    dijkstra算法解释得异常清楚,伪代码也很清晰,但是写到Floyd-WarShall算法就不太认真了噢。谢谢楼主了。
    2017-09-18 22:30 | 不燥不怕  

    #41楼37902282017/9/19 23:02:22   

    非常感谢
    2017-09-19 23:02 | learningAgain  
    葡萄城1101
    阿里云1113
    fixPostBody(); setTimeout(function () { incrementViewCount(cb_entryId); }, 50); deliverAdT2(); deliverAdC1(); deliverAdC2(); loadNewsAndKb(); loadBlogSignature(); LoadPostInfoBlock(cb_blogId, cb_entryId, cb_blogApp, cb_blogUserGuid); GetPrevNextPost(cb_entryId, cb_blogId, cb_entryCreatedDate, cb_postType); loadOptUnderPost(); GetHistoryToday(cb_blogId, cb_blogApp, cb_entryCreatedDate);


    导航

    <2012年7月>
    24252627282930
    1234567
    891011121314
    15161718192021
    22232425262728
    2930311234

    公告

    昵称:as_
    园龄:5年4个月
    粉丝:481
    关注:0

    展开全文
  • 最短路径算法 Dijkstra算法 Floyd算法 简述

    万次阅读 多人点赞 2017-01-29 06:22:47
    Dijkstra算法 又称迪杰斯特拉算法,是一个经典的最短路径算法,主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止,使用了广度优先搜索解决赋权有向图的单源最短路径问题,算法最终得到一个最短路径树。...
  • Floyd算法思想

    千次阅读 2016-03-20 19:34:05
    Floyd-Warshall算法Floyd-Warshall algorithm)是解决任意两点间的最短路径的一种算法,可以正确处理有向图或负权的最短路径问题,同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为O(N3),...
  • 1、Floyd算法解决的是所有成对的最短路径问题 对于图中的每一个顶点,该算法都会找出从某个顶点到该顶点所能达到的任何其他顶点的最短路径 构建的一个初始的距离矩阵,其单元格中包含了连接每一个顶点及其邻居节点...
  • Floyd 算法

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

空空如也

1 2 3 4 5 ... 20
收藏数 17,720
精华内容 7,088
关键字:

floyd