基于DP的最短路算法---Floyd

简介：

Floydclass="superseo">算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。

特点：

1.可以求任意两个结点之间的最短路的

2.复杂度比较高 ，但是常数小，容易实现(三重循环)

3.适用于任何图，包括有向图，无向图，边权正负均可（不存在负环）

核心思想：

我们枚举三个点 i , j , k;

对于两个点(i , j) , d[i , j] 表示 i 到 j 的最短距离，k为 i , j 之间的转折点；

如果在 i 到 j 中存在 这样一个 k 使得 d[i,k] + d[k,j]" src="https://latex.codecogs.com/gif.latex?d%5Bi%2Cj%5D%20%3E%20d%5Bi%2Ck%5D%20+%20d%5Bk%2Cj%5D" />我们则进行一次松弛 *** 作;

；

核心代码：

void 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]);
	        }
	    }
	}
}

 练习：

原题链接：采购特价商品 - 洛谷

有了Floyd算法之后，我们来看一个题；

这个题，我们直接看数据范围，n = 100，确定Floyd是可以过；

我们从题干中，抽象出的模型就是，我们要计算两个点之间的最短路径；

只不过这个最短路径中的点不是按照常规给出的，而是按照坐标给出；

每个坐标，对应两个值，所以我们使用pair数组存储，又因为需要遍历每个点，所以我们用一个hash表来存，存储结构我们搞定了；

因为我们要求的距离是欧拉距离，所以我们要考虑计算欧拉距离；

然后，然后就是 coding 啦；

#include
#include
#include
#include
#include
#define x first
#define y second 
#define _for(i,s,t) for(int i = (s);i <=t ; i++)
#define FAST ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);

using namespace std;

typedef unsigned long long ULL;
typedef long long LL;
typedef pair PII;

const int N = 110,INF = 0x3f3f3f3f;

int n,m,st,ed;;
double d[N][N];
unordered_map hah;

void 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]);
	        }
	    }
	}
}

double solve(int x1,int y1,int x2,int y2)
{
	return sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1));
}

int main()
{
	
	scanf("%d",&n);
	
	for(int i =1 ;i<= n ;i ++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		hah[i] = {a,b};
	}
	scanf("%d",&m);
	
	for(int i = 1;i <= n;i ++)
		for(int j = 1;j <= n;j ++)
			if(i == j) d[i][j] = 0;
			else d[i][j] = INF;
			
	for(int i =1 ;i<= m ;i ++)
	{
		int a,b;
		int x1,x2,y1,y2;
		scanf("%d%d",&a,&b);
		x1 = hah[a].x , y1 = hah[a].y;
		x2 = hah[b].x , y2 = hah[b].y;
		d[a][b] = d[b][a] = solve(x1,y1,x2,y2);
	}
	
	scanf("%d%d",&st,&ed);
	
	floyd();
	
	printf("%.2lf ",d[st][ed]);
	
	return 0;
} 

原题链接：传送门 - 洛谷

 熟悉了floyd的简单应用之后，我们在来看一个有亿点点难度的；

根据题干我们抽象出一个模型，就是我们需要给现有路径上加入一个传送门，使得两点上的路径为零，可以直接过去，然后计算路径和，使得它最小；

我们先考虑最朴素的做法，就是我们先跑一遍floyd，我们枚举每两个点，然后再跑一遍floyd，显然时间复杂度是;对于这个时间复杂度我们是无法接受的；

那我们考虑一下优化；

我们每次枚举两个点，进行修改，也就是说对于其他不经过该条边上的路径的值是不受影响的，那我们考虑只修改经过该条边的路径就可以了；

接下来我们考虑一下如何计算；

我们知道floyd算法的第二层循环，是枚举一个转折点，然后进行松弛 *** 作；

那么如果某条路径经过当前枚举的边，那一定会以当前边的两个端点最为转折点；

也就是说，我们更新以当前边的两个端点作为转折点的路径即可；

最后，因为我们只需要记录一次x -> y 的值，我们枚举上三角矩阵，记录最小值；

可以看到，我们枚举两个点是，进行更新也是，时间复杂度是刚好可以过;

#include
#include
#include
#include
#include
#define x first
#define y second 
#define _for(i,s,t) for(int i = (s);i <=t ; i++)
#define FAST ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);

using namespace std;

typedef unsigned long long ULL;
typedef long long LL;
typedef pair PII;

const int N = 110,INF = 0x3f3f3f3f;

int n,m,res; 
int d[N][N],g[N][N];

void 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]);
	        }
	    }
	}
}

int solve(int u,int v)
{
	int sum = 0;
	memcpy(g,d,sizeof d);
	
	g[u][v] = g[v][u] = 0;
	
	for(int i =1 ;i<=n ;i++)   
    	for(int j = 1 ;j<=n ;j ++)
   	 		g[i][j] = min(g[i][j], g[i][u] + g[u][j]);
    
	for(int i =1 ;i<=n ;i++)
	    for(int j = 1 ;j<=n ;j ++)
	        g[i][j] = min(g[i][j], g[i][v] + g[v][j]);
	      
	for(int i =1 ;i <= n;i ++)
	for(int j =i + 1;j <= n;j ++)
	{
		sum += g[i][j];
	}
	return sum;
}

int main()
{
	scanf("%d%d",&n,&m);
	
	memset(d,0x3f,sizeof d);
	for(int i =1 ;i<=n;i ++)d[i][i] = 0;
	
	for(int i =1 ;i<=m ;i ++)
	{
		int x,y,w;
		scanf("%d%d%d",&x,&y,&w);
		d[x][y] = d[y][x] = w;
	}
	floyd();
	
	res = INF;
	for(int i =1 ;i <= n ;i ++)
	{
		for(int j = i + 1;j <= n; j ++)
		{
			int ant = solve(i,j);
			res = min(res,ant);
		}
	}
	
	printf("%d",res);
	
	return 0;
}