floyd算法

喜欢ヅ旅行 2021-06-22 15:37 405阅读 0赞

floyd算法是通过动态规划特别是记住公式，f[i, j, k]表示从i走到j的路径上除i和j点外只经过1到k的点的所有路径的最短距离。那么f[i, j, k] = min(f[i, j, k - 1), f[i, k, k - 1] + f[k, j, k - 1]。
    因此在计算第k层的f[i, j]的时候必须先将第k - 1层的所有状态计算出来，所以需要把k放在最外层。
    那为什么判断不连通的条件为大于0x3f3f3f3f/2呢？，因为可能存在不连通的点但是能把那个点更新了，比如i到j的距离是0x3f3f3f3f但是j到k的距离是-1，可以更新最短距离就不是0x3f3f3f3f了

#include <iostream>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    const int maxn=1e5+10;
    int n,m,k;

int g[210][210];
    void floyd(){ 
    	int k,i,j;
    	for(int k=1;k<=n;k++){ 
    		for(int i=1;i<=n;i++){ 
    			for(int j=1;j<=n;j++){ 
    				g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
    			}
    		}
    	}
    }

int main(){ 
    	cin>>n>>m>>k;
    	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]=0x3f3f3f3f;
    			 }
    		}
    	}
    	while(m--){ 
    		int a,b,c;
    		cin>>a>>b>>c;
    		g[a][b]=min(g[a][b],c);
    	}
    	floyd();
    	while(k--){ 
    		int a,b;
    		cin>>a>>b;
    		if(g[a][b]>0x3f3f3f3f/2){ 
    			cout<<"impossible"<<endl;
    		}
    		else{ 
    			cout<<g[a][b]<<endl;
    		}
    	}
    	
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，405人围观）

还没有评论，来说两句吧...

相关阅读

相关 Floyd-Warshal算法

![0_1315389826sAEs.gif][] 先来简单分析下,由于矩阵中对角线上的元素始终为0,因此以k为中间点时,从上一个矩阵到下一个矩阵变化时,矩阵的第k行,第k

港控/mmm°/ 2024年02月18日 22:54/ 0 赞/ 49 阅读

相关 Floyd算法

Floyd算法的理解 Floyd算法是用来求两点之间的最短路径的，它的一大特点就是三循环，时间复杂度是n^3。对于Floyd算法，相信初学者大多都会有一个疑问，就是

迷南。/ 2023年07月08日 09:18/ 0 赞/ 7 阅读

相关 Floyd算法实现(.)

最短路径算法 Floyd算法实现 const int INF = 65535; void GetShortestPath_Floyd(MGraph

缺乏、安全感/ 2022年12月27日 08:41/ 0 赞/ 125 阅读

相关 Floyd判圈算法

关于该算法，wiki上有详细说明。 https://en.wikipedia.org/wiki/Cycle\_detection\Tortoise\_and\_hare h

港控/mmm°/ 2022年12月13日 11:18/ 0 赞/ 127 阅读

相关【经典算法】：Dijskstra算法与Floyd算法

Dijkstra算法利用的是一个经典的东西，叫做保持好的最短路径，目的就是为了在寻找最短路径的时候的保持最短化的过程 Floyd算法利用的是一个经典的公式 D\

超、凢脫俗/ 2022年09月26日 02:58/ 0 赞/ 232 阅读

相关 1128 信使（floyd算法）

1. 问题描述：战争时期，前线有 n 个哨所，每个哨所可能会与其他若干个哨所之间有通信联系。信使负责在哨所之间传递信息，当然，这是要花费一定时间的（以天为单位）。指挥部设在

约定不等于承诺〃/ 2022年09月15日 15:52/ 0 赞/ 225 阅读

相关 PHP实现Floyd算法

Floyd算法相比于迪杰特斯拉算法又是在于方便理解，逻辑清晰但不方便记录路径 public function run() { @set

柔情只为你懂/ 2022年06月15日 04:28/ 0 赞/ 199 阅读

相关 Floyd-Warshall算法

　　Floyd也是采用动态规划的方案来解决在一个有向图G=（V，E）上每对顶点间的最短路径问题。运行时间为Θ（V3）。算法分析：　　用邻接矩阵map\[\]\[\]存储

以你之姓@/ 2021年12月17日 03:03/ 0 赞/ 306 阅读

相关图论 Floyd算法

Floyd算法　　　　时间复杂度O (n^3) 　　空间复杂度O (n^2) 用处　　可以求任意两个点之间的最短路径长度。　　得出的邻接矩阵存储 i 到 j 的

青旅半醒/ 2021年12月15日 05:01/ 0 赞/ 254 阅读

相关 floyd算法

floyd算法是通过动态规划特别是记住公式，f[i, j, k]表示从i走到j的路径上除i和j点外只经过1到k的点的所有路径的最短距离。那么f[i, j, k] = m

喜欢ヅ旅行/ 2021年06月22日 15:37/ 0 赞/ 406 阅读