精华内容
下载资源
问答
  • 弗洛伊德算法思想: 矩阵D存储任意两点间的最短路径,刚开始矩阵D和邻接矩阵一样,利用弗洛伊德算法实现时,依次枚举N个中转点(N为所有顶点数),判断如果从第i个点出发到第j个点,如果: 起点i到中转点k的距离+k到...

    弗洛伊德算法思想:

    矩阵D存储任意两点间的最短路径,刚开始矩阵D和邻接矩阵一样,利用弗洛伊德算法实现时,依次枚举N个中转点(N为所有顶点数),判断如果从第i个点出发到第j个点,如果:
    起点i到中转点k的距离+k到终点j的距离比它两的直接距离还小,那么就更新矩阵D中它两对应的值。

    #include <bits/stdc++.h>
    using namespace std;
    #define inf 0x3f3f3f
    int D[100][100],N,M,G[100][100]; //D为任意两点最短路径矩阵   G为邻接矩阵 
    void flyod()
    {
    	int i,j,k;
    	for(k=1;k<=N;k++) //枚举中转点 
    	 for(i=1;i<=N;i++)
    	  for(j=1;j<=N;j++)
    	    { if(D[i][k]+D[k][j]<D[i][j]) //当任意两点经过中转点比两点间直接距离短时,松弛这两点最短路的值 
    	       D[i][j]=D[i][k]+D[k][j];
    	    }
    	for(i=1;i<=N;i++) //输出任意两点最短路径矩阵 
    	{ for(j=1;j<=N;j++)
    	   cout<<D[i][j]<<" ";
    	   cout<<endl;
    	}
    }
    int main()
    {
        cin>>N>>M;
        int i,j,start,end,w;
        for(i=1;i<=N;i++)  //初始化任意两点间距离为无穷大 
         for(j=1;j<=N;j++)
          {G[i][j]=inf;
           D[i][j]=inf;
          }
        for(i=1;i<=M;i++)//构建邻接矩阵 
        { cin>>start>>end>>w;
          G[start][end]=G[end][start]=w;
          D[start][end]=D[end][start]=w;
        }
       flyod();
    	return 0;
    } 
    
    展开全文
  • 最短路之——弗洛伊德算法(floyd)

    万次阅读 多人点赞 2018-06-12 19:46:38
    我们要做的是出从某一点到达任意一点的最短距离,我们先用邻接矩阵来建图,map[i][j]表示从i点到j点的距离,把自己到自己设为0,把自己到不了的边初始化为无穷大,代码为:[cpp] view plain copy//初始化 for...

    来源: https://blog.csdn.net/riba2534/article/details/54562440


    我们要做的是求出从某一点到达任意一点的最短距离,我们先用邻接矩阵来建图,map[i][j]表示从i点到j点的距离,把自己到自己设为0,把自己到不了的边初始化为无穷大,代码为:

    [cpp]  view plain  copy
    1. //初始化  
    2.     for(int i=1; i<=n; i++)  
    3.         for(int j=1; j<=n; j++)  
    4.             if(i==j)  
    5.                 map[i][j]=0;  
    6.             else  
    7.                 map[i][j]=inf;  
    8.     //读入边  
    9.     for(int i=1; i<=m; i++)  
    10.     {  
    11.         scanf("%d%d%d",&t1,&t2,&t3);  
    12.         map[t1][t2]=t3;  
    13.     }  
    最后,建好的图可以用表格来表示:

    现在,我们来思考,假设我们来找一个中转的点,看他们的路程会不会改变,我们先以1号顶点作为中转点最为例子,制图:


    我们发现,图有了变化,我们怎么判断以1号顶点作为中转点图的路程是不是更短呢,我们只需要判断map[i][1]+map[1][j]的路程是不是比map[i][j]的路程更短,就可以判断,

    代码为:

    [cpp]  view plain  copy
    1. for(int i=1; i<=n; i++)  
    2.     for(int j=1; j<=n; j++)  
    3.         if(map[i][1]+map[1][j]<map[i][j])  
    4.             map[i][j]=map[i][1]+map[1][j];  
    现在该怎么办呢,我们接着以2号顶点作为中转点,很简单代码修改一句就就可以:

    [cpp]  view plain  copy
    1. for(int i=1; i<=n; i++)  
    2.     for(int j=1; j<=n; j++)  
    3.         if(map[i][2]+map[2][j]<map[i][j])  
    4.             map[i][j]=map[i][2]+map[2][j];  
    现在我们是不是发现了一个规律,只要不断的遍历每一个点,并且以每一个点作为中转点看看它的值会不会改变,就可以得到从一个点到任意一个点的最短路径,也就是多源最短路,这就是弗洛伊德算法,代码为:

    [cpp]  view plain  copy
    1. for(int k=1; k<=n; k++)  
    2.     for(int i=1; i<=n; i++)  
    3.         for(int j=1; j<=n; j++)  
    4.             if(map[i][k]+map[k][j]<map[i][j])  
    5.                 map[i][j]=map[i][k]+map[k][j];  
    这样就可以遍历每个顶点,找出所有的最短路,算法的复杂度为O(n^3).

    对于我一开始提出的问题,完整的代码为:

    [cpp]  view plain  copy
    1. #include <stdio.h>  
    2. #include <string.h>  
    3. #include <string>  
    4. #include <iostream>  
    5. #include <stack>  
    6. #include <queue>  
    7. #include <vector>  
    8. #include <algorithm>  
    9. #define mem(a,b) memset(a,b,sizeof(a))  
    10. using namespace std;  
    11. const int inf=1<<29;  
    12. int main()  
    13. {  
    14.     int map[10][10],n,m,t1,t2,t3;  
    15.     scanf("%d%d",&n,&m);//n表示顶点个数,m表示边的条数  
    16.     //初始化  
    17.     for(int i=1; i<=n; i++)  
    18.         for(int j=1; j<=n; j++)  
    19.             if(i==j)  
    20.                 map[i][j]=0;  
    21.             else  
    22.                 map[i][j]=inf;  
    23.     //读入边  
    24.     for(int i=1; i<=m; i++)  
    25.     {  
    26.         scanf("%d%d%d",&t1,&t2,&t3);  
    27.         map[t1][t2]=t3;  
    28.     }  
    29.     //弗洛伊德(Floyd)核心语句  
    30.     for(int k=1; k<=n; k++)  
    31.         for(int i=1; i<=n; i++)  
    32.             for(int j=1; j<=n; j++)  
    33.                 if(map[i][k]+map[k][j]<map[i][j])  
    34.                     map[i][j]=map[i][k]+map[k][j];  
    35.     for(int i=1; i<=n; i++)  
    36.     {  
    37.         for(int j=1; j<=n; j++)  
    38.             printf("%10d",map[i][j]);  
    39.         printf("\n");  
    40.     }  
    41.     return 0;  
    42. }  
    展开全文
  • 弗洛伊德算法求最短路径

    千次阅读 2019-03-22 20:54:11
    弗洛伊德算法的是各个点之间的最小路径 这里的核心思想大致是这个样子,比如说你要从学校一教走到四教,中间经过的距离是10KM,这时如果你是先从一教走到风雨操场再到四教有可能只需要8KM,那么还有可能假如你是...

    在这里插入图片描述
    大意:

    弗洛伊德算法所求的是各个点之间的最小路径 这里的核心思想大致是这个样子,比如说你要从学校一教走到四教,中间经过的距离是10KM,这时如果你是先从一教走到风雨操场再到四教有可能只需要8KM,那么还有可能假如你是从一教到风雨再到数图再到四教发现距离只需要6KM。

    按我们图中的这个例子,假如现在我要从1→3 直接走是6步 这时我们发现如果经过2 即1→2→3这样的话只需要5步
    那么如何实现它呢只需要 min(e[i][j],e[i][2]+e[2][j])

    i→ j的意思是从点I到点j

    那么我们将它扩展开来 假如计算每两个点通过2以后会不会使距离变得太短

    //经过2号顶点
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if (e[i][j] > e[i][2]+e[2][j])  e[i][j]=e[i][2]+e[2][j];
    

    假如扩展开来我们让他通过所有点来使它不仅仅是直接得出两点的距离而是计算当有通过中间的点之后的最短距离,有可能中转一个点会变短,也有可能是几个当然也有可能不用中转

    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];
    
    

    完整程序

    `#include <stdio.h>
    int main()
    {
        int e[10][10],k,i,j,n,m,t1,t2,t3;
        int inf=99999999; 
        //读入n和m,n表示顶点个数,m表示边的条数
        scanf("%d %d",&n,&m);    
        //初始化
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(i==j) e[i][j]=0;  
                  else e[i][j]=inf;
       //读入边
        for(i=1;i<=m;i++)
        {
            scanf("%d %d %d",&t1,&t2,&t3);
            e[t1][t2]=t3;
        }
        //Floyd-Warshall算法核心语句
        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];  
        //输出最终的结果
        for(i=1;i<=n;i++)
        {
         for(j=1;j<=n;j++)
            {
                printf("%10d",e[i][j]);
            }
            printf("\n");
        }
        
        return 0;
    }
    
    展开全文
  • 给定一个n个点m条边的有向图,图中可能存在重边和自环,边权可能为负数。 再给定k个询问,每个询问包含两个整数x和y,表示查询从点x到点y的最短距离,如果路径不存在,则输出“impossible”。 ...

    给定一个n个点m条边的有向图,图中可能存在重边和自环,边权可能为负数。

    再给定k个询问,每个询问包含两个整数x和y,表示查询从点x到点y的最短距离,如果路径不存在,则输出“impossible”。

    数据保证图中不存在负权回路。

    输入格式

    第一行包含三个整数n,m,k

    接下来m行,每行包含三个整数x,y,z,表示存在一条从点x到点y的有向边,边长为z。

    接下来k行,每行包含两个整数x,y,表示询问点x到点y的最短距离。

    输出格式

    共k行,每行输出一个整数,表示询问的结果,若询问两点间不存在路径,则输出“impossible”。

    数据范围

    1≤n≤2001≤n≤200,
    1≤k≤n21≤k≤n2
    1≤m≤200001≤m≤20000,
    图中涉及边长绝对值均不超过10000。

    输入样例:

    3 3 2
    1 2 1
    2 3 2
    1 3 1
    2 1
    1 3
    

    输出样例:

    impossible
    1

     

    
    import java.io.*;
    import java.lang.*;
    import java.util.*;
    
    class Main{
        
        static int n = 0, m = 0, kc = 0;
        static int N = 210;
        static int INF = 0x3f3f3f3f;
        static int[][] g = new int[N][N];
        
        static void Flord(){
            
            for(int k = 1; k <= n; ++k)
                for(int i = 1; i <= n; ++i)
                    for(int j = 1; j <= n; ++j)
                        g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
           
        }
        
        public static void main(String[] args)throws Exception{
            BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
            String[] params = buf.readLine().split(" ");
            n = Integer.valueOf(params[0]);
            m = Integer.valueOf(params[1]);
            kc = Integer.valueOf(params[2]);
            for(int i = 1; i<= n; ++i){
                for(int j = 1; j <= n; ++j)
                    if(i == j)g[i][j] = 0;
                    else g[i][j] = INF;
            }
            for(int i = 1; i<= m; ++i){
                String[] info = buf.readLine().split(" ");
                int a = Integer.valueOf(info[0]);
                int b = Integer.valueOf(info[1]);
                int w = Integer.valueOf(info[2]);
                if(a == b)
                    g[a][b] = 0;
                else
                    g[a][b] = Math.min(g[a][b], w);
            }
            Flord();
            for(int i = 1; i <= kc; ++i){
                String[] info = buf.readLine().split(" ");
                int a = Integer.valueOf(info[0]);
                int b = Integer.valueOf(info[1]);
                if(g[a][b] > INF / 2)System.out.println("impossible");
                else System.out.println(g[a][b]);
            }
        }
    }

     

    展开全文
  • 原理:动态规划 设中转点是ki,那么i->j的最短路是min(dis[i][j],dis[i][ki]+dis[ki][j]),就是他的最短路要么是...多源最短路 判断负环 任意两点的最短距离,如果有负环可以判断出来 核心 bool floyd() ..
  • 弗洛伊德算法 最短路径

    千次阅读 2020-10-29 19:45:07
    我们现在需要任意两个城市之间的最短路程,也就是任意两个点之间的最短路径。这个问题这也被称为“多源最短路径”问题。 现在需要一个数据结构来存储图的信息,我们仍然可以用一个4*4的矩阵(二维数组e)来...
  • 最短路Floyd算法

    2014-04-04 13:32:51
    在计算有环有方向的最短路时,可以用Floyd算法计算出任意两点之间的最短路
  • NULL 博文链接:https://128kj.iteye.com/blog/1689015
  • 弗洛伊德算法 int dist[N]; // dist[i]表示起始点到i的距离 int w[iN][N]; // w[i][j]表示i到j的边的权值,如果不相邻,则为无穷大 for(int i = 0;i < n;i++) { for(int j = 0;j < n;j++) { dist[j] = min...
  • 弗洛伊德最短路算法

    千次阅读 2017-12-04 00:18:07
    暑假,小哼准备去一些城市旅游。有些城市之间有公路,有些城市...我们现在需要任意两个城市之间的最短路程,也就是任意两个点之间的最短路径。这个问题这也被称为“多源最短路径”问题。 现在需要一个数据结构
  • // 4.4 弗洛伊德算法求赋权图的两点间的最短路径 #include <stdio.h> #include <stdlib.h> #include <malloc.h> #define max 10000 typedef struct MGraph { int matrix[max][max]; int vernum...
  • 最短路 1.多源最短路 定义:现有n个地点,任意两点间的最短距离 ...那么我们要实现弗洛伊德算法的存储的话,一般都是用邻接矩阵实际上就是二维数组来实现的。 以上图为例子>我们把它转换成表格,
  • 思路:典型的最短路做法,用弗洛伊德和迪杰斯特拉算法各敲了一遍,当作复习。 ps:在稠密图中(m相对较大的图)dijkstra是最好的选择,写起来快,速度也快。对于floyd来说,当n>300的时候就不要用了,很可能跑1m...
  • 弗洛伊德算法-----最短路径算法(一)

    万次阅读 多人点赞 2017-12-28 16:37:58
    学习此算法的原因:昨天下午遛弯的时候,碰到闺蜜正在看算法,突然问我会不会弗洛伊德算法?我就顺道答应,然后用了半个小时的时间,学习了此算法,并用5分钟讲解给她听,在此也分享给各位需要的朋友,让你们在最短...
  • Floyd(罗伯特·弗洛伊德)于1962年发表在“Communications of the ACM”上。同年Stephen Warshall(史蒂芬·沃舍尔)也独立发表了这个算法。Robert W.Floyd这个牛人是朵奇葩,他原本在芝加哥大学读的文学,但是...
  • 弗洛伊德算法通过邻接矩阵存储图(有向图或者无向图)的信息,两点的距离,通过动态转移方程 a[i][j] = min(a[i][j], a[i][p] + a[p][j]); 来更新最短路径,出各个点之间的最短路径
  • 弗洛伊德算法介绍 弗洛伊德(Floyd)算法也是一种用于寻找给定的加权图中顶点间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。 Floyd优缺点分析 ...
  • Floyd(佛洛依德,和著名心理心理学家同名)算法用来解决全源最短路问题,即给定图G(V,E),任意两顶点的最短路径长度,时间复杂度O(n^3)。Floyd非常适合使用邻接矩阵来实现,但总的顶点数n限制在200以内。 Floyd...
  • 弗洛伊德(Floyd)算法介绍 1)和Dijkstra算法一样,弗洛伊德(Floyd)算法也...4)弗洛伊德算法 VS 迪杰斯特拉算法:迪杰斯特拉算法通过选定的被访问顶点,出从出发访问顶点到其他顶点的最短路径;弗洛伊德算法中每一个.
  • 算法描述:Floyd算法又称为弗洛伊德算法,插点法,是一种用于寻找给定的加权图中顶点间最短路径的算法。从图的带权邻接矩阵A=[a(i,j)]n×n开始,递归地进行n次更新,即由矩阵D(0)=A,按一个公式,构造出矩阵D(1);又...
  • 最短路弗洛伊德

    2018-12-03 17:35:18
    利用弗洛伊德算法实现无向图的短路径问题,弗洛伊德算法是可以任意两点间的最短距离,主要就是依次以图中每个节点为中间节点然后计算起始节点到中间节点加上中间节点到终节点的距离是否小于起始节点直接到终节点...
  • Floyd(弗洛伊德算法最短路径 有向图

    万次阅读 多人点赞 2018-12-30 21:37:52
     另外需要注意的是:Floyd-Warshall算法不能解决带有“负权回路”(或者叫“负权环”)的图,因为带有“负权回路”的图没有最短路。例如下面这个图就不存在1号顶点到3号顶点的最短路径。因为1->2->3->1->2->3->…->...
  • 弗洛伊德算法

    2021-07-27 14:05:28
    弗洛伊德算法任意点到所有点的最短距离 任意节点i到j的最短路径两种可能: 直接从i到j; 从i经过若干个节点k到j。 假如现在只允许经过1号顶点,任意两点之间的最短路程,应该如何呢?只需判断e[i][1]+e...
  • 参数都一样,这个改了一下能算出两点之间所有的最短路,算复杂网络的时候用到的,改了半天,算出的路由矩阵是cell,path给出一个每列记录一条路径,列数等于最短路数的矩阵,如果一个如果一条最短路经过的点较少,就...
  • 一、迪杰斯特拉(Dijkstra)算法 1、定义描述 Dijkstra(迪杰斯特拉)算法是典型的单源最短...例如下图中的1号顶点到2、3、4、5、6号顶点的最短路径: 2、算法思想 设G=(V,E)是一个带权有向图,把图中顶点集合...
  • java使用弗洛伊德(floyd)算法获取最短路,并打印对应路径 作业是使用动态规划获取最短路径,自然想到了牛逼的floyd算法 有向图: public class Main{ public static void main(String[] args){ //创建顶点名称,...
  • 最近考研复习到图的一些算法,但书上对这些算法解释只是一笔带过,更多的是如何做,如何使用。对于我这种又笨又固执的人来说,无疑非常难受,甚至一开始想不明白这个地方,但又说不出来,所以昨天很长时间都在思考这...
  • 博客内容有误欢迎指出!欢迎评论交流!...最短路径步骤 1、使用一个n*n的邻接矩阵map存储图,令其对角线元素为0,若存在弧&amp;amp;lt;Vi,Vj&amp;amp;gt;,则对应元素为权值;否则为无穷大,m...
  • 题目  N M//接下来N行,每行X,Y,V。表示序号X到序号Y要V费。  X Y V  ....  X Y//最后一行表示要从序号X到Y;   #include&lt;iostream&gt; #include&lt;cstdio&...al...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,002
精华内容 800
关键字:

弗洛伊德算法求最短路