共有回帖数 0 个
-
Floyd-Warshall 算法进阶应用
Floyd-Warshall 算法是有向图（当前也适用于无向图）中求最短路径长度的算法，可以得到各对点间的最短路径，并且允许存在负权值的边，时间复杂度 Θ(|V|^3)。
----------
动态规划本质
----------
图 G 的顶点集 V 为 {1,2,...,n}，A 为其邻接矩阵，d[k][j] 表示允许以 {1,2,...,k} 作为中间顶点，i 到 j 的最短路径，易知 d[n][j] 就是 i 到 j 的最短路径（因为允许任意点为中间顶点）。然后考察如何计算 d[k][j]。
显然，d[0][j] = A[j]。
假设我们已知 d[k-1][j]，设 d[k][j] 代表的最短路径为 p：
* 如果 k 不是路径 p 的中间顶点，那么 p 的所有中间顶点在集合 {1,2,...,k-1} 中，d[k][j] 代表的最短路径就是路径 p
* 如果 k 是路径 p 的中间顶点，那么说明 i 经由 k 到达 j，而 i 到达 k 所经过的中间顶点均在集合 {1,2,...,k-1} 中，k 到达 j 所经过的中间顶点也均在集合 {1,2,...,k-1} 中。所以 d[k][j] = d[k-1][k]+d[k-1][k][j]。
从而得到 d[k][j] 的递推式：
d[k][j] = A[j], if k = 0
min(d[k-1][j], d[k-1][k]+d[k-1][k][j], if k 0
易知 d 的第一维可以省略，从而得到经典代码：
for (int k = 1; k = n; ++k)
for (int i = 1; i = n; ++i)
for (int j = 1; j = n; ++j)
if (d[k]+d[k][j] d[j])
d[j] = d[k]+d[k][j];
-------
传递闭包
-------
把 d[j] = true 视为存在 i 到 j 的路径即可。
---------------
寻找有向图的最小圈
---------------
对于一个最小圈，它必然存在一个编号最大的顶点，比如为 k，那么在执行 Floyd-Warshall 算法的第 k 次外层迭代前，d[j] 存放的是中间顶点在集合 {1,2,...,k-1} 中，i 到 j 的最短路径。容易知道此时 d[k]+dist[k][j]+A[j] 就是最大编号为 k、包含 i、j、k（绕向为 j-i-k）的最小圈。做完 n 次迭代后，我们就可以知道最大编号为任意值的最小圈：最大编号为1的最小圈、最大编号为2的最小圈、……、最大编号为n的最小圈，这些值中取最小值即可。
int best = 0;
for (int k = 1; k = n; ++k)
{
for (int i = 1; i = k; ++i)
for (int j = 1; j = k; ++j)
if (d[k]+d[k][j]+A[j] best)
best = d[k]+d[k][j]+A[j];
for (int i = 1; i = n; ++i)
for (int j = 1; j = n; ++j)
if (d[k]+d[k][j] d[j])
d[j] = d[k]+d[k][j];
}
+++++++++++++++++++++++++++++++++++
例题 USACO Training 4.1 Fence Loops
+++++++++++++++++++++++++++++++++++
题目大意：给定一个无向图 G，求出 G 的最小圈。输入方式比较怪异，给出的是与某条边一端相连的边的序号。
分析：设 w 为边 i 的权值，A[j] = w+w[j]，以此为邻接矩阵。那么对于最小圈 e1 - e2 - ... - em - e1，我们求出的值是 A[1][2]+A[2][3]+...+A[m-1][m]+A[m][1]，也就是 2(w[1]+w[2]+...+w[m])。
++++++++++++++++++++++++++++++++++++++++++++++++++++++
例题 USACO Contest DEC09 Gold Problem 2 Cow Toll Paths
++++++++++++++++++++++++++++++++++++++++++++++++++++++
题目大意，给定点边均赋权的无向图，顶点数 N = 250，边数 M = 10000，有 K = 10000 个询问，询问 u 到 v 的最小花费。花费定义为一条路经上所有边的权值和，加上路径上顶点中的最大权值。
分析：w 为顶点 i 的权值。枚举顶点 p，只允许经过权值小于 w[p] 的顶点，用任一最短路径算法求出 u 到 v 的最短路径，加上 w[p] 即为总花费。取最小值即可。
其实可以利用 Floyd-Warshall 的性质，把顶点按权值从小到大排序，以此对顶点重编号。可知第 k(u,v = k) 次外层迭代后，d[v] + w[k] 就是以 k 为最大权值顶点的最小花费。
楼主 2016-04-21 09:21 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
