Floyd 算法

算法用途：

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

该算法时间复杂度为 \(O(N^3)\)，空间复杂度为 \(O(N^2)\) 。

算法原理

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

Floyd 算法一直在解决一个问题，寻找 \(i \rightarrow j\) 的最短路径 （废话）。

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

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

\( i \sim j 的最短路径 \begin{cases} 直接从 i 到 j \\ 从 i 开始，经过 x 个点，到达 j \\ \end{cases} \)

设任意一个中途经过的节点为 \(k\)，我们检查 \(f_{i, k} + f_{k, j} < f_{i, j}\) 是否成立，如果成立即证明 \(i \sim k \sim j < i \sim j\)，则 \(f_{i, j} = f_{i, k} + f_{k, j}\)，遍历完所有节点后，\(f_{i, j}\) 记录的就是最短路径的长度。（咋感觉和背包有点像？？？）

算法思想

1. 从任意一个边开始，将所有两点有直接连接的边的最短路径（\(f_{i, j}\)）设为边权，如果两点之间没有边则初始化为 \(\inf\)。

2. 对于每一对顶点 \([i, j]\)，看是否有一个顶点 \(k\) 使得 \(i \rightarrow k \rightarrow j < i \rightarrow j\)，如果有就更新路径长度。

核心代码 & 代码分析

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 了）

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

从动态规划考虑，我们设 \(f_{k, i, j}\) 为经过前 \(k\) 个点的 \(i \rightarrow j\) 最短路径，根据上述原理，我们有两种转移方法：

\( f_{k, i, j} = \begin{cases} f_{k - 1, i, j} & 不经过 k 节点 \\ f_{k - 1, i, k} + f_{k - 1, k, j} & 经过 k 节点 \\ \end{cases} \)

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

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

最短路径的子路径仍然是最短路径，这个定理显而易见，比如一条 \(a \rightarrow e\) 的最短路 \(a \rightarrow b \rightarrow c \rightarrow d \rightarrow e\) 那么 \(a \rightarrow b \rightarrow c\) 一定是 \(a \rightarrow c\) 的最短路，反过来，如果说一条最短路必须要经过点 \(k\)，那么 \(i \rightarrow k\) 的最短路加上 \(k \rightarrow j\) 的最短路一定是 \(i \rightarrow j\) 经过 \(k\) 的最短路。因此，最优子结构可以保证。

状态 \(f_{k, i, j}\) 由 \(f_{k - 1, i, j}\)，\(f_{k - 1, i, k} + f_{k - 1, k, j}\) 转移过来，很容易可以看出，\(f_{k, x, x}\) 的状态完全由 \(f_{k - 1, x, x}\) 转移过来。因此，只要我们把 \(k\) 放最外层循环中，就能保证无后效性。

参考资料

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

---（华丽的分界线）---

例题

注：本部分含有大量使用 Hexo-Theme-Redefine 渲染的内容，阅读感受不好请见谅。

或许更好的阅读体验

{% tabs Floyd Ques %}

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

点我查看题目

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

纯板子，见上。

{% folding white::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 ;
}

{% endfolding %}

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

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

我们现在思考，求 \(1 \rightarrow n\) 的最短路是简单的，那我们求 \(1 \rightarrow n\) 中间必须经过 \(x\) 个点的最短路，即为 \(1 \rightarrow x_1 \rightarrow x_2 \rightarrow \dots \rightarrow x_k \rightarrow n\)，这也非常简单，我们可以用分治来考虑。

\(1 \rightarrow 经过 n 个点 \rightarrow n = \begin{cases} 1 \rightarrow x_1 \\ x_1 \rightarrow x_2 \\ \dots \\ x_{k - 1} \rightarrow x_k \\ x_k \rightarrow n \end{cases}\)

即为：\(1 \rightarrow x_1 \rightarrow x_2 \rightarrow \dots \rightarrow x_k \rightarrow n = f_{1, x_1} + f_{x_1, x_2} + \dots + f_{x_{k - 1}, x_k} + f_{x_k, n}\)

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

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

有两个问题：

1. 怎么确定边的顺序？

• • 全排列，next_permutation。

2. 怎么确定点的顺序？

• • 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)));
}

{% endfolding %}

完整代码：

#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;
}

{% endtabs %}