wiki - 算法小站

wiki 主题

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

算法基础搜索数据结构字符串数学图论动态规划计算几何杂项

图论

图的连通性

有向图的强连通分量

无向图的割点割边和双连通分量

流和匹配

最大流

最大流的一些应用

最小割

费用流

图论杂项

最大团搜索算法

树上问题

kruskal重构树

kruskal重构树的一些问题

最短路

[[ item.c ]]

最短路算法

## Floyd-Warshall 算法
用来求解**任意两点之间**的最短路径，算法是基于**动态规划**的

令$$dp(k, i, j)$$表示从节点`i`到节点`j`，只允许使用编号从$$1 \sim k$$的节点作为**中间节点**时的最短路径长度
状态转移方程，根据**最短路经不经过`k`**来划分
要么$$i \to j$$只用`[1...k-1]`构成最短路（不经过`k`），要么经过`k`
而经过`k`的最短路，划分成两段，$$i \to k$$，只用`[1...k-1]`作为中间节点，$$k \to j$$，只用`[1...k-1]`作为中间节点
```math
\displaystyle
dp(k, i, j) = \min(dp(k-1, i, j), dp(k-1, i, k) + dp(k-1, k, j))
```
使用滚动数组来优化的话
```bash
for k = 1 to n:
	for i = 1 to n:
		for j = 1 to n:
			d(i, j) = min(d(i, j), d(i, k) + d(k, j))
```

实际上，迭代`k`轮，在`kth`轮循环开始时候，`d(i, j)`维护只允许使用`[1...k-1]`作为中间节点的最短路
循环结束后，`d(i, j)`维护只允许使用`[1...k]`作为中间节点的最短路

当枚举了所有中间节点之后，`d(i, j)`就是$$i \to j$$的**全源最短路**

### ABC416E Development
**[ABC416E Development](https://www.luogu.com.cn/problem/AT_abc416_e)**
给定`n`个城市，`m`条道路，`k`个机场
其中第`i`条道路用$$(a_i, b_i, c_i)$$描述，双向道路，表示$$a_i, b_i$$两座城市之间，通行时间是$$c_i$$
另外有$$K$$个机场，位于城市$$d_1, d_2, \cdots, d_k$$，有机场的城市可以通过时间$$T$$互相到达
下面给定`Q`个询问，有三种类型
```bash
1 x y t，在 x, y 城市之间建一个双向道路，通行时间是 t
2 x, 在 x 城市新建一个机场
3，设 f(x, y) 是从城市 x 到城市 y 通过道路和机场可达的最短时间，不可达输出 0
```
对于操作`3`，可达时输出
```math
\displaystyle
\sum_{x = 1}^{n} \sum_{y = 1}^{n} f(x, y)
```

> 首先，机场怎么描述？

可以维护一个超级源点`air`，在城市`u`建机场，相当于连边`(u -> air, 0), (air -> u, T)`

> 其次，这个问题中的动态加点连边，怎么处理？

传统的`dijkstra`等算法，是没有办法处理动态加边这个过程的，但是`Floyd-Warshall`却可以
1）先预处理所有节点对的最短路`d(i, j)`，构成一个**矩阵**
2）假设说添加了道路$$(x, y, z)$$，那么`d`矩阵**会怎么变化**呢？`upd(x, y, z)`

可以$$O(n^2)$$枚举每一个节点对$$(i, j)$$，更新$$d(i, j) \xleftarrow{\min} d(i, x) + z + d(y, j)$$
3）由于是双向道路，再同样执行一遍`upd(y, x, z)`即可

### 算法实现
**Floyd-Warshall**
```bash
template<typename T>
vector<vector<T> > FloydWarshall(const vector<vector<T> > &mat, int n) {
    // vertex: [1...n]
    auto ret = mat;
    for (int u = 1; u <= n; u++) ret[u][u] = 0;

for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (ret[i][k] < inf<T> and ret[k][j] < inf<T>) {
                    ret[i][j] = min(ret[i][j], ret[i][k] + ret[k][j]);
                }
            }
        }
    }

return ret;
}

template<typename T>
vector<vector<T> > FloydWarshall(const Graph<T> &G) {
    int n = G._n;
    vector<vector<T> > ret(n+5, vector<T>(n+5, inf<T>));

// vertex, 1-indexed
    for (int u = 1; u <= n; u++) {
        ret[u][u] = 0;
        for (auto id : G.g[u]) {
            auto [from, to, cap] = G.e[id];
            chmin(ret[u][to], cap);
        }
    }

return FloydWarshall(ret, n);
}
```
**修改部分**
```bash
auto modify = [&](int x, int y, i64 z) -> void {
    for (int i = 1; i <= g._n; i++) {
        for (int j = 1; j <= g._n; j++) {
            if (mat[i][x] < inf<i64> and mat[y][j] < inf<i64>) {
                chmin(mat[i][j], mat[i][x] + z + mat[y][j]);
            }
        }
    }
};

void solve() {
	if (op == 1) {
		modify(x, y, w);
		modify(y, x, w);
	}
}
```

看完文章有啥想法

算法小站

wiki 主题

图论

最短路算法

目录