精华内容
下载资源
问答
  • 要求得任意两点之间的最短路,可以采用松弛操作,对在i和j之间的所有其他点进行一次松弛,即访问从i到j的所有可能路径,把i到经过若干个编号不超过k的点再到j的多种路径做对比,更短的路径保留。 这本质上是一种动态...


    一、问题

    • 用Floyd算法求解下图各个顶点的最短距离,给出距离矩阵(顶点之间的最短距离矩阵)
      在这里插入图片描述

    二、解析

    要求得任意两点之间的最短路,可以采用松弛操作,对在i和j之间的所有其他点进行一次松弛,即访问从i到j的所有可能路径,把i到经过若干个编号不超过k的点再到j的多种路径做对比,更短的路径保留。

    这本质上是一种动态规划,把从i到j的最短路问题分成:i经过编号不超过k-1的节点到j,以及i先到k再到j,两个子问题。这样k不断加大,就可以不断的通过子问题找到经过更多点问题的答案。

    若D[k, i, j] 表示i点经过若干个编号不超过k的节点而到达j时的最短距离,则状态转移方程可以写为:D[k, i, j] = min( D[k-1, i, j] , D[k-1, i, k] + D[k-1,k,j] )

    而k是阶段, 讨论i,j间最短距离时必须要先确定最多可以经过多少个点(即k),所以要放在外层,外层循环到k时,内层有状态转移:D[i, j] = min( D[i, j] , D[i, k] + D[k,j] )

    三、设计

    由于k确定了之后,内部状态转移明确,所以k这一维的状态转移可以省略;

    可以初始化让D[0, i, j]=A[i, j],即i到j之间不经过点时的最短距离就是i直接到j

    然后就是k确定,遍历所有的i和j,把状态记录到d[k, i, j]。

    四、分析

    由于是k一层经过不超过n个点节点的外层循环,加上i到j的排列情况两层循环,故时间复杂度O(n³)

    由于k层面的状态记录可以省略,所以实际需要保持d[i][j]的数组,故空间复杂度O(n²)

    五、代码

    #include<stdio.h>
    #include<stdlib.h>
    #include<memory.h>
    #include<string.h>
    #include<algorithm>
    
    using namespace std;
    
    const int INF = 0x3f3f3f3f;
    const int N = 1005;
    
    int d[N][N], n, m;
    int main(void) {
    	scanf("%d%d", &n, &m);
    	//把d初始化为邻接矩阵
    	memset(d, INF, sizeof(d));
    	for (int i = 1; i <= n; i++)
    		d[i][i] = 0;
    	for (int i = 1; i <= m; i++) {
    		int x, y, z;
    		scanf("%d%d%d", &x, &y, &z);
    		d[x][y] = min(d[x][y], z);//保留从x直接到y中最短的路径
    	}
    	//floyd
    	for (int k = 1; k <= n; k++)
    		for (int i = 1; i <= n; i++)
    			for (int j = 1; j <= n; j++)
    				d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
    
    	printf("\n");
    	for (int i = 1; i <= n; i++) {
    		for (int j = 1; j <= n; j++)
    			printf("%d ", d[i][j]);
    		printf("\n");
    	}	
    }
    /*测试例子
    4 8
    1 2 2
    1 3 6
    1 4 4
    2 3 3
    3 1 7
    3 4 1
    4 1 5
    4 3 12
    */
    
    展开全文
  • 而在这篇博客里我们需要讲解的是求任意两点最短路的一个很简单的算法:Floyd算法。 二、算法概念介绍 Floyd算法其实是用到了动态规划的方法去解决图论问题,对于确定的起点与终点,我们可以通过状态的转移由之前求得...

    一、前言

    对于最短路问题,我们已经介绍了很多的算法来求解。其中每一种算法都有其不可替代性,分别适用于不同的情况。而在这篇博客里我们需要讲解的是求任意两点最短路的一个很简单的算法:Floyd算法。

    二、算法概念介绍

    Floyd算法其实是用到了动态规划的方法去解决图论问题,对于确定的起点与终点,我们可以通过状态的转移由之前求得的已知最短路来求得未知的最短路。如果要搞懂Floyd算法,你需要对于动态规划的知识点有所了解,否则可能会对其核心思想----状态转移无法理解。由于动态规划算法的特殊性,由代码来理解会更加轻松一些,因此笔者会在代码中写下详细的注释来帮助大家理解Floyd算法。

    三、算法的代码实现

    例题链接:Acwing Floyd求最短路

    给定一个 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≤200,
    1≤k≤n2
    1≤m≤20000,
    图中涉及边长绝对值均不超过 10000。
    
    输入样例:
    3 3 2
    1 2 1
    2 3 2
    1 3 1
    2 1
    1 3
    输出样例:
    impossible
    1
    

    这一道题就是一道Floyd算法的板子题,搞懂了这道题就可以说理解了Floyd算法。

    #include<iostream>
    #include<iomanip>
    #include<cstdio>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<queue>
    #include<vector>
    #include<map>
    #include<stack>
    #include<set>
    #include<bitset>
    #include<ctime>
    #include<cstring>
    #include<list>
    #define ll long long
    #define ull unsigned long long
    #define INF 0x3f3f3f3f
    #define mem(a,b) memset(a,b,sizeof(a))
    using namespace std;
    typedef  pair<int, int> PII;
    const int N = 1e3 + 7;
    int n, m, k;
    int dp[N][N];   //动态规划数组,dp[i][j]代表从i到j的最短距离
    
    void floyd()    //Floyd算法实现函数
    {
    	for (int k = 1; k <= n; k++)   //枚举中间的点,即一定经过k点
    		for (int i = 1; i <= n; i++)    //枚举起点
    			for (int j = 1; j <= n; j++)   //枚举终点
    				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);   //动态规划状态转移方程
    }
    
    void solve()
    {
    	cin >> n >> m >> k;
    	for(int i=1;i<=n;i++)    //初始化操作
    		for (int j = 1; j <= n; j++)
    		{
    			if (i == j)dp[i][j] = 0;   //自己到自己的距离为0
    			else dp[i][j] = INF;  //把每两个不同点的距离初始化为无限大
    		} 
    	for (int i = 0; i < m; i++)   //输入边的操作
    	{
    		int x, y, z;
    		cin >> x >> y >> z;
    		dp[x][y] = min(dp[x][y], z);   //如果两点不止一条边,保留最短的边
    	}
    	
    	floyd();   //实现算法
    	
    	while (k--)
    	{
    		int x, y;
    		cin >> x >> y;
    		if (dp[x][y] > INF / 2)    //这里在下面解释
    			cout << "impossible" << endl;
    		else
    			cout << dp[x][y] << endl;
    	}
    }
    
    int main()
    {
    	//std::ios::sync_with_stdio(false);
    	//cin.tie(0), cout.tie(0);
    	solve();
    	return 0;
    }
    

    解释为什么不是">INF"而是“>INF/2”:由于题目中可能会有负数边存在,而在方程“dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]); ”中我们可以发现,如果边为负数居然会把INF更新为INF-x,但是这个值实际上并不是我们能到达的距离。根据题目中数据范围,我们可以发现,我们虽然不能写成”>INF",但是“>INF/2”是可以判断是否能到达终点的。

    作者:Avalon Demerzel,喜欢我的博客就点个赞吧,更多图论与数据结构知识点请见作者专栏《图论与数据结构》

    展开全文
  • int d[MAX_V][MAX_V]; ///d[u][v]表示边e=(u,v)的权值(不存在时为INF,d[i][i]=0) int V; ///顶点数 void floyd() {  for(int k=0; k  for(int i=0; i  for(int j=0; j ... d[i][j]=m
    int d[MAX_V][MAX_V];  ///d[u][v]表示边e=(u,v)的权值(不存在时为INF,d[i][i]=0)
    
    int V; ///顶点数


    void floyd()
    {
        for(int k=0; k<V; k++)
            for(int i=0; i<V; i++)
                for(int j=0; j<V; j++)
                    d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
    }
    展开全文
  • 矩阵D存储任意两点间的最短路径,刚开始矩阵D和邻接矩阵一样,利用弗洛伊德算法实现时,依次枚举N个中转点(N为所有顶点数),判断如果从第i个点出发到第j个点,如果: 起点i到中转点k的距离+k到终点j的距离比它两的...

    弗洛伊德算法思想:

    矩阵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;
    } 
    
    展开全文
  • 最近复习了下最短路,...依次用1到n号顶点做中转,松弛任意两点之间的距离。 因为这个算法比较简单,就直接上代码了; #include<iostream> using namespace std; const int N=2000; int main() { int ma
  • Floyd-算法--任意两点间的最短路问题

    千次阅读 2017-12-23 14:10:35
    Floyd算法-任意两点间的最短路问题  求解所有两点间的最短路的问题叫做任意两点间的最短路问题。让我们试着用DP来求解任意两点间的最短路问题。只使用0~k的情况下,记i到j的最短路长度为d[k+1][i][j]。k=-1时,认为...
  • 我在前面的一篇博客中详细讲到了有权图中的最短路径问题--dijkstra算法,有兴趣的可以开下面插件温习一下dijkstra算法。但是,dijkstra算法无法解决边权为负的情况。因为dijkstra在对于路径长短的选择上采用了贪心...
  • // // Created by jal on 18-9-3. // #include &amp;lt;bits/stdc++.h&amp;gt; using namespace std; int n,m; const int MAXN = 50,MAX = 99999; int dis[MAXN][MAXN]; void init(){ ... i++){...
  • 任意两点间的最短路问题(Floyd-Warshall算法) 1 #define _CRT_SECURE_NO_WARNINGS 2 /* 3 7 10 4 0 1 5 5 0 2 2 6 1 2 4 7 1 3 2 8 2 3 6 9 2 4 10 10 3 5 1 11 4 5 3 12 4...
  • 算法作用求给定图中任意两点间的短距离时间复杂度O(v^3) V是顶点个数代码实现(3个for)g是用邻接矩阵传入的图, 如果两点之间没有路径, 设成inf, 否则设成边权, n是顶点个数, 顶点编号默认0~n-1, 最后i, j点的最短...
  • Floyd-Warshall算法是求解任意两点最短路的有力武器。其也适用于存在负边的情况。DP思路,假设只使用前K个点时i到j的短距离为d[k][i][j] 那么,使用前K+1个点就可以分成两种情况 ①i到j的最短路用到了第K+1个点...
  • floyd算法-求图中任意两点最短路

    千次阅读 2017-12-19 10:35:18
    floyd算法是一种可以在o(v^3)求出一个图中任意两点最短路的算法 输入:邻接矩阵d 输出:直接在d上面修改,每个元素d(i,j)代表点i到点j的最短路 这个算法的代码非常短,一眼看上去非常暴力 for(int k=1;k;k++) ...
  • Floyed算法任意两点间的最短路) 可以处理存在负边的情况,也可以判断是否存在负环。 对于最短路我们之前接触的都是单源最短路径,即起点固定,求该点开始到其他点的最短路径,但是如果我们想要求得任意两点间的...
  • Dijkstra算法任意两点间的最短路问题 路径还原 1 #define _CRT_SECURE_NO_WARNINGS 2 /* 3 7 10 4 0 1 5 5 0 2 2 6 1 2 4 7 1 3 2 8 2 3 6 9 2 4 10 10 3 5 1 11 4 5 3 ...
  • 本文要解决的问题和Dijkstra算法相似,在图上找两点间的最短路径,图上的边带有权重,权重不能为负数。在这里,增加一些约束条件,要求路径必须经过某些节点。要求路径不能成环,即不能两次经过相同的节点,否则问题...
  • 最短路算法总结(超详细~)

    千次阅读 多人点赞 2020-04-11 23:09:44
    多源最短路: 求任意两最短路 稠密图用邻接矩阵存,稀疏图用邻接表存储。 稠密图: m 和 n2 一个级别 稀疏图: m 和 n 一个级别 朴素Dijkstra算法 Dijkstra算法是通过 n 次循环来确定 n 个...
  • 算法实现的主要思路是声明一个路径矩阵和一个距离矩阵,利用动态规划的思想,依次将所有顶点作为中转顶点进行遍历,计算出当前路径距离与上一次的结果进行比较,如果当前路径的距离更小则更新个矩阵。...
  • Floyd算法用来解决每对顶点间的最短路劲问题,时间复杂度为n^3
  • 代码来源:《图论算法及其matlab实现》(北京航空航天出版社) P22 此代码返回第一个和最后一个之间最短路径,以及最短路径的长度。... 4 %u表示最短路的权和 5 n=length(W); 6 U=W; 7 ...
  • 本质是动态规划,O(n^3)算法思路设D[k,i,j]表示“经过若干个编号不超过k的节点”从i到j的最短路该问题可划分为个子问题:1.经过编号不超过k-1的节点从i到j 2.从i先到k再到jD[k,i,j]=min(D[k-1,i,j],D[k-1,i,k]+D...
  • 这个算法很简单,很容易理解 直接看代码 核心代码 void Floyd() { for(k = 0;k < n;k++) for(i = 0;i < n;i++) for(j = 0;j < n;j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } ...
  • 本文主要讲述计算两点之间所有的最短路,有一个误解需要澄清,即两点之间不只有一条最短路两点之间可能含有多条最短路! 1. 问题引入及介绍 /> 如上图所示,节点对之间的最短路径有两条,一条是:4 -> 3 -> 10...
  • public class Floyd { //Floyd最短路算法,求任意两点之前的短路 static void Floyd(float e[][]){ for(int k=0;k for(int i=0;i  for(int j=0;j  if(e[i][j]>e[i][k]+e[k][j])  e[i][j]=e[i][k]+e[k][j];
  • 任意两点间的最短路问题(Floyd-Warshall算法) */ import java.util.Scanner; public class Main { //图的顶点数,总边数 static int V, E; //存储所有的边,大小为顶点数 static int[][] Edges; ...
  • 刚开始的时候一直不明白插的顺序为什么不会对最后的结果有影响----一直不懂这个算法--- 今天看见他们都学会了-.-终于把我也带会了-- 对于原理的理解我还是通过输出每一步更新后的结果搞明白的 开始一直不...
  • 求解任意两点最短路问题也叫多源最短路径问题。 可解决途径 一种方法是把图中每个点当做源点重复算n次Dijkstra 算法(Dijkstra是求单源最短路径的算法),时间复杂度O(n^3),据说可以优化成O(n^2logn)。 另一...
  • 和 上算法的出发一样。每个顶点都有可能使得另外个顶点之间的路程变短。 d[i][j] = min(d[i][j], d[i][k] + d[k][j]; 不断用上式递推就可以实现 int d[MAX_V][MAX_V]; int V: void warshall-floyd() {...
  • 最最原始的问题——两点间的最短路 这类背景一般是类似:已知各城市之间距离,请给出从城市A到城市B的最短行车方案 or 各城市距离一致,给出需要最少中转方案。 也就是,固定起始点的情况下,求最短路。 这个问题...
  • 算法】算法6:只有五行的Floyd最短路算法 [复制链接]       电梯直达 楼主 发表于 2014-3-25 08:08:22|只看该作者|只看大图  暑假,小哼准备去一些城市旅游。有些...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 13,548
精华内容 5,419
关键字:

任意两点最短路算法是