Floyd 算法学习日记

算法用途：

Floyd 算法是用于解决两点间最短路径的一种算法，可以处理有向图或负权的最短路问题。

该算法时间复杂度为，空间复杂度为。

算法原理

Floyd 算法基于动态规划实现。

Floyd 算法一直在解决一个问题，寻找的最短路径 ~~（废话）~~。

但是，既然是动态规划，那么我们就要为问题做一个全新的定义 ~~（平生最烦动态规划就是因为这个）~~。

从任意节点到另一个节点，不外乎就两种可能。

$的最短路径直接从到从开始，经过个点，到达$

设任意一个中途经过的节点为，我们检查是否成立，如果成立即证明，则，遍历完所有节点后，记录的就是最短路径的长度。~~（咋感觉和背包有点像？？？）~~

算法思想

从任意一个边开始，将所有两点有直接连接的边的最短路径（）设为边权，如果两点之间没有边则初始化为。
对于每一对顶点，看是否有一个顶点使得，如果有就更新路径长度。

核心代码 & 代码分析

void floyd()
{
    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (i == j)
                {
                    f[i][j] = 0;
                    continue;
                }
                f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
            }
        }
    }

    // print 部分
    for (int i = 1; i <= n; i++)
    {
        for (int j = i + 1; j <= n; j++)
            cout << i << " " << j << "的最路径为：" << f[i][j] << "\n";
    }

    return ;
}

~~（真的真的太太太 DP 了）~~

核心代码只有三层循环，一行更新，十分简洁，可是这四行代码为什么就能求出任意两点的最短路径呢？

从动态规划考虑，我们设为经过前个点的最短路径，根据上述原理，我们有两种转移方法：

$不经过节点经过节点$

众所周知，DP 的两个满足条件为 最优子结构 和 无后效性。

这里有一个显而易见的定理：

最短路径的子路径仍然是最短路径，这个定理显而易见，比如一条的最短路那么一定是的最短路，反过来，如果说一条最短路必须要经过点，那么的最短路加上的最短路一定是经过的最短路。因此，最优子结构可以保证。

状态由，转移过来，很容易可以看出，的状态完全由转移过来。因此，只要我们把放最外层循环中，就能保证无后效性。

参考资料

图最短路径算法之弗洛伊德算法（Floyd）

—（华丽的分界线）—

例题

例题 1：爆搜与 Floyd 的融合

算法：Floyd, 爆搜, 组合数学（全排列）

点我查看题目

看见这个题目，我们先来处理最最最无脑的 Floyd 预处理部分。

纯板子，见上。

Floyd 板子部分

void floyd()
{
    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (i == j)
                {
                    f[i][j] = 0;
                    continue;
                }
                f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
            }
        }
    }
	return ;
}

我们现在思考进行问题转化。

对于 Floyd 算法，最适合求导的问题就是最短路问题 ~~（CNM，说了一堆废话）~~。

我们现在思考，求的最短路是简单的，那我们求中间必须经过个点的最短路，即为，这也非常简单，我们可以用分治来考虑。

$经过个点$

即为：

得到这个公式后，我们可以将问题转化。

既然要经过所有边，我们就转化为要经过所有指定边的点。

有两个问题：

怎么确定边的顺序？

- 全排列，next_permutation。

怎么确定点的顺序？

- dfs 爆搜

爆搜部分

注：每次全排列后，通过最短路到达目前执行边起点，在起点加上本边边权。

ll search(int now, int nowi, ll cnt)
{
	if (nowi == k + 1)
	{
		cnt += f[now][n];
		return cnt;
	}
	return min((search(a[need[nowi] - 1].v, nowi + 1, cnt + f[now][a[need[nowi] - 1].u] + a[need[nowi] - 1].w)), (search(a[need[nowi] - 1].u, nowi + 1, cnt + f[now][a[need[nowi] - 1].v] + a[need[nowi] - 1].w)));
}

完整代码：

#include <bits/stdc++.h>
using namespace std;

#define ll long long
int n, m;
struct road
{
	int id;
	int u, v;
	ll w;
};
vector<road> a;
ll f[505][505];
void floyd()
{
    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (i == j)
                {
                    f[i][j] = 0;
                    continue;
                }
                f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
            }
        }
    }
	return ;
}

int q;
int k, need[505];
ll search(int now, int nowi, ll cnt)
{
	if (nowi == k + 1)
	{
		cnt += f[now][n];
		return cnt;
	}
	return min((search(a[need[nowi] - 1].v, nowi + 1, cnt + f[now][a[need[nowi] - 1].u] + a[need[nowi] - 1].w)), (search(a[need[nowi] - 1].u, nowi + 1, cnt + f[now][a[need[nowi] - 1].v] + a[need[nowi] - 1].w)));
}
ll ans;

int main()
{
	cin >> n >> m;
	memset(f, 0x3f3f3f3f, sizeof(f));
	for (int i = 0; i < m; i++)
	{
		road now;
		now.id = i + 1;
		cin >> now.u >> now.v >> now.w;
		a.push_back(now);
		f[now.u][now.v] = min(f[now.u][now.v], now.w);
		f[now.v][now.u] = min(f[now.v][now.u], now.w);
	}
	floyd();
	
	cin >> q;
	while (q--)
	{
		cin >> k;
		for (int i = 1; i <= k; i++)
			cin >> need[i];
		ans = LONG_LONG_MAX;
        sort(need + 1, need + k + 1);
		do
		{
			ans = min(ans, search(1, 1, 0));
		}
		while (next_permutation(need + 1, need + k + 1));
		cout << ans << "\n";
	}
	return 0;
}

George222