分类目录网站程序,网上建立网站,佛山企业网站设计,什么最便宜网站建设多源最短路#xff1a;即图中每对顶点间的最短路径
floyd算法本质是动态规划#xff0c;⽤来求任意两个结点之间的最短路#xff0c;也称插点法。通过不断在两点之间加⼊新的点#xff0c;来更新最短路。 适⽤于任何图#xff0c;不管有向⽆向#xff0c;边权正负…多源最短路即图中每对顶点间的最短路径
floyd算法本质是动态规划⽤来求任意两个结点之间的最短路也称插点法。通过不断在两点之间加⼊新的点来更新最短路。 适⽤于任何图不管有向⽆向边权正负但是最短路必须存在也就是不存在负环。
状态表⽰ f[k][i][j] 表⽰仅仅经过 [1, k] 这些点结点 i ⾛到结点 j 的最短路径的⻓度。状态转移⽅程
第⼀种情况不选新来的点 f[k][i][j] f[k - 1][i][j] 第⼆种情况选择新来的点 f[k][i][j] f[k - 1][i][k] f[k - 1][k][j]
空间优化只会⽤到上⼀层的状态因此可以优化到第⼀维。初始化
f[i][i] 0 f[i][j] 为初始状态下 i 到 j 的距离如果没有边则为⽆穷。
填表顺序
⼀定要先枚举 k 再枚举 i 和 j 。因为我们填表的时候需要依赖的是 k - 1 层的状态因此 k 必须先枚举。
B3647 【模板】Floyd - 洛谷
#include bits/stdc.h
using namespace std;const int N 110;int n, m;
int f[N][N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin n m;memset(f, 0x3f, sizeof f);for (int i 1; i n; i) f[i][i] 0;for (int i 1; i m; i){int a, b, c; cin a b c;f[a][b] f[b][a] min(f[a][b], c);}//floydfor (int k 1; k n; k)for (int i 1; i n; i)for (int j 1; j n; j)f[i][j] min(f[i][j], f[i][k] f[k][j]);for (int i 1; i n; i){for (int j 1; j n; j)cout f[i][j] ;cout endl;}return 0;
}P2910 [USACO08OPEN] Clear And Present Danger S - 洛谷
#include bits/stdc.h
using namespace std;typedef long long LL;const int N 110, M 1e4 10;int n, m;
int a[M];
int f[N][N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin n m;for (int i 1; i m; i) cin a[i];for (int i 1; i n; i)for (int j 1; j n; j)cin f[i][j];for (int k 1; k n; k)for (int i 1; i n; i)for (int j 1; j n; j)f[i][j] min(f[i][j], f[i][k] f[k][j]);LL ret 0;for (int i 2; i m; i){int x a[i-1], y a[i];ret f[x][y];}cout ret endl;return 0;
}P1119 灾后重建 - 洛谷
在floyd算法中我们是⼀个点⼀个点加⼊到最短路的更新中那么这道题其实就是限制了我们加点的时机。当从前往后遍历每次询问的时候直到时间点在询问的时间t之前的点都可以加⼊到最短路的更新中。 那么就可以⼀边读取询问⼀边通过时间限制更新最短路
#include bits/stdc.h
using namespace std;const int N 210, INF 0x3f3f3f3f;int n, m;
int t[N];
int f[N][N];void floyd(int k)
{for (int i 0; i n; i)for (int j 0; j n; j)f[i][j] min(f[i][j], f[i][k] f[k][j]);
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin n m;for (int i 0; i n; i) cin t[i];memset(f, 0x3f, sizeof f);for (int i 0; i n; i) f[i][i] 0;for (int i 1; i m; i){int a, b, c; cin a b c;f[a][b] f[b][a] min(f[a][b], c);}int Q; cin Q;int pos 0;while (Q--){int a, b, c; cin a b c;while (pos n t[pos] c) floyd(pos);if (t[a] c || t[b] c || f[a][b] INF) cout -1 endl;else cout f[a][b] endl;}return 0;
}P6175 无向图的最小环问题 - 洛谷
floyd算法的性质
在计算第 k 层的时候 f[i][j] ⾥⾯存储着中转点为 [1, k - 1] 时的最短路。如果设环⾥的最⼤结点的编号为 k 与k相邻的点为 i, j 其中 i k j k i ! j 那么我们在floyd算法循环到 k 的时候这个环的最⼩⻓度为 f[i][j] e[i][k] e[j][k] 。环的最⼤编号是任意的因此在所有情况下取最⼩值即可
#include bits/stdc.h
using namespace std;const int N 110, INF 1e8;int n, m;
int e[N][N];
int f[N][N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin n m;//memset(e, 0x3f, sizeof e);//memset(f, 0x3f, sizeof f);for (int i 1; i n; i)for (int j 1; j n; j)f[i][j] e[i][j] INF;for (int i 1; i n; i) e[i][i] f[i][i] 0;for (int i 1; i m; i){int a, b, c; cin a b c;e[a][b] e[b][a] f[a][b] f[b][a] min(e[a][b], c);}int ret INF;for (int k 1; k n; k){//最小环for (int i 1; i k; i)for (int j i1; j k; j)ret min(ret, f[i][j] e[i][k] e[k][j]);//最短距离for (int i 1; i n; i)for (int j 1; j n; j)f[i][j] min(f[i][j], f[i][k] f[k][j]);}if (ret INF) cout No solution. endl;else cout ret endl;return 0;
}
