有没有专门做包装设计的网站,ssc网站建设交流群,做企业网站还有钱挣吗,做网站apache如何Floyd算法是一种对所有点对最短路径算法、多源最短路径算法#xff0c;以此计算能得到图中每一对节点之间的最短路径。Floyd不仅可以用来求多源最短路#xff0c;也可以用于解决传递闭包问题。 算法思想#xff1a;
Floyd求最短路径用的是“从小图到全图”的动态规划思想以此计算能得到图中每一对节点之间的最短路径。Floyd不仅可以用来求多源最短路也可以用于解决传递闭包问题。 算法思想
Floyd求最短路径用的是“从小图到全图”的动态规划思想定义状态dp[k][i][j]i、j、k都为节点编号范围为1~n。状态dp[k][i][j]表示在包含1~k点的子图上点对i、j的最短路径。当从子图1~k-1扩展成子图1~k时状态转移方程为
dp[k][i][j]min(dp[k-1][i][j], dp[k-1][i][k]dp[k-1][k][j]);
dp[k-1][i][j]是不考虑经过k点的旧的i到j的路径dp[k-1][i][k]dp[k-1][k][j]是考虑经过k点的新的i到j的路径较小者就是新的dp[k][i][j]。
当k从1逐步扩展到n时最后得到的dp[n][i][j]就是点对i、j之间的最短路径长度。若i、j是直连的初值dp[0][i][j]就是边长若不直连初值为无穷大。
在具体实现时我们利用滚动数组技巧将dp[][][]缩成dp[][]因为dp[k][][]只和dp[k-1][][]有关所以可以省略掉k这一维。由于k是动态规划子问题的“阶段”即k是从点1开始逐步扩大到n的所以k循环必须在i、j循环的外层。
关键代码
void floyd()
{for (int k 0; k n; k) // 不能将最外层的k循环放到内层这会导致结果出错{for (int i 0; i n; i){for (int j 0; j n; j){if(d[i][k] ! INF d[k][j] ! INF d[i][k] d[k][j] d[i][j]){d[i][j] d[i][k] d[k][j]; // 找到更短的路径}}}}
}
或者
void floyd()
{for (int k 0; k n; k) // 不能将最外层的k循环放到内层这会导致结果出错{for (int i 0; i n; i){for (int j 0; j n; j){d[i][j] min(d[i][j], d[i][k]d[k][j]);}}}
} 算法特征
1能一次性求得所有节点之间的最短距离。
2效率不高时间复杂度为O(n^3)n为节点数量。
3用邻接矩阵存储最合适因为Floyd算法求的是所有点对之间的最短距离本身就需要n*n的存储空间。
4可用于负权边可以判断负环。因为Floyd基于动态规划思想而非贪心思想所以即使图中存在负权边也可以保证从局部最优可以推导到全局最优。如果图中存在负环那么每在这个负环上绕一圈总长度就更小从而使得能与这个负环连通的点对的最短距离都将成为负无穷大。而Floyd算法很容易判断负环只要在算法运行过程中出现任意dp[i][i]0就说明有负环。因为dp[i][i]是从i出发经过其他中转点绕一圈回到自己的最短路径如果小于0即存在负环。 算法的常见应用场景以及例题
1图的规模n300。时间复杂度O(n^3)限制了图的规模。
2可能多次查询不同点对之间的最短路径。 例题hdu 1385 题意非常简单的模板题该题需要输出具体的路径点。 思路求最短路就是最简单的Floyd模板我们讨论打印具体路径的方法用path[][]记录路径path[i][j]u表示起点为i终点为j的最短路径从i出发下一个点是u。一个完整的路径是从s出发查询path[s][j]u找到下一个点为u然后从u出发查询path[u][j]v下一个点是v重复这个操作直到最后到达终点j。路径的具体计算见代码。 代码
#include iostream
#include cstdio
#include cstring
#include cstring
using namespace std;const int maxn5000;
const int INF100000000;int n;
int node[maxn];
int dist[maxn][maxn];
int path[maxn][maxn];void floyd()
{for(int i1;in;i)//初始化 有一种后驱的感觉for(int j1;jn;j)path[i][j]j;for(int k1;kn;k)for(int i1;in;i)for(int j1;jn;j){int tempdist[i][k]dist[k][j]node[k];if(dist[i][j]temp){dist[i][j]temp;path[i][j]path[i][k];}if(dist[i][j]temp){if(path[i][j]path[i][k])path[i][j]path[i][k];}}
}int main()
{int a,be,en;while(scanf(%d,n)n){for(int i1;in;i)for(int j1;jn;j){scanf(%d,a);if(a!-1) dist[i][j]a;else dist[i][j]INF;}for(int i1;in;i) scanf(%d,node[i]);floyd();int kcase0;while(1){if(kcase!0) printf(\n);kcase;scanf(%d%d,be,en);if(be-1en-1) break;printf(From %d to %d :\n,be,en);printf(Path: );printf(%d,be);int tempbe;while(temp!en){printf(--%d,path[temp][en]);temppath[temp][en];}printf(\n);printf(Total cost : %d\n,dist[be][en]);}}return 0;
} 3问题的解决和中转点有关。这是Floyd算法的核心思想算法用DP方法遍历中转点计算最短路径。 例题洛谷P1119 灾后重建 个人题解戳这
4路径在“兜圈子”一个点可能多次经过。这是Floyd算法的特点其他路径算法都不行。 例题洛谷P1613 跑路 个人题解戳这
5解决传递闭包问题。传递闭包是离散数学的概念给定一个集合以及若干对元素之间的传递关系传递闭包问题是求所有元素之间的传递连通关系。例如包括3个元素的集合{a,b,c}给定传递关系a-bb-c那么可以推导出a-c。在图论中可以把传递闭包问题转换为给定一个有向图其中有n个点和m条边求所有点对之间的连通性关系。传递闭包是“多源”路径问题。 例题1hdu1704 Rank 题意有m场比赛每场比赛由两人决胜负。已知一些比赛的成绩现在要查询任意两人之间的胜负情况要求输出有多少个查询的胜负是不能被确定的。在本题中我们认为胜负关系具有传递性即若A赢了BB赢了C那么得出A赢了C。n,m 500。 思路把参赛人员和胜负关系建模为一个有向图有向边A-B表示A赢了B。然后使用Floyd算法求解传递闭包矩阵矩阵中等于1代表能确定胜负为0代表不能确定。统计Floyd后矩阵中为0的数量即可。本题n500比较小简单优化即可通过。如果n1000则需要使用bitset优化减少一层循环。bitset是一种类似数组的数据结构它的每个元素用1b存储只能是0或者1。使用了bitset后Floyd算法在传递闭包的特殊情况下时间复杂度可以优化到接近O(n^2)。 代码
#include bits/stdc.h
using namespace std;
#define endl \n
typedef long long ll;
typedef unsigned long long ull;
const int maxn 1e3 10;
const int INF 0x3fffffff;
const int mod 1000000007;
int dis[maxn][maxn];
int n, m;void floyd() {for (int k 1; k n; k) {for (int i 1; i n; i) {if (!dis[i][k])continue;for (int j 1; j n; j) {if (!dis[k][j])continue;dis[i][j] 1;}}}
}void solve() {cin n m;for (int i 1; i n; i) { // 初始化for (int j 1; j n; j) {dis[i][j] (i j);}}for (int i 0; i m; i) {int u, v;cin u v;dis[u][v] 1;}floyd();int ans 0;for (int i 1; i n; i) {for (int j i 1; j n; j) {if (dis[i][j] 0 dis[j][i] 0) {ans;}}}cout ans endl;
}int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout fixed;cout.precision(18);int t;cin t;while (t--)solve();return 0;
} 下面也给出bitset优化的代码bitset的作用是省去了最后一层j的循环改用位运算或的方式对整个bitset数组的每一位一次性计算
#include bits/stdc.h
using namespace std;
#define endl \n
typedef long long ll;
typedef unsigned long long ull;
const int maxn 1e3 10;
const int INF 0x3fffffff;
const int mod 1000000007;
bitsetmaxn dis[maxn];
int n, m;void floyd() {for (int k 1; k n; k) {for (int i 1; i n; i) {if (!dis[i][k])continue;dis[i] | dis[k];}}
}void solve() {cin n m;for (int i 1; i n; i) { // 初始化for (int j 1; j n; j) {dis[i][j] (i j);}}for (int i 0; i m; i) {int u, v;cin u v;dis[u][v] 1;}floyd();int ans 0;for (int i 1; i n; i) {for (int j i 1; j n; j) {if (dis[i][j] 0 dis[j][i] 0) {ans;}}}cout ans endl;
}int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout fixed;cout.precision(18);int t;cin t;while (t--)solve();return 0;
} 例题2POJ1127 题意给出n条线段线段相交即连通判断任意两条线段是否连通 思路首先用计算几何的算法求出线段相交将线段之间的相交构建成二维矩阵就可以转换成传递闭包问题了用Floyd求出所有线段之间的连通性。 代码
#include cstdio
#include iostream
#include cmath
using namespace std;
const int maxn 20;
const int maxm 1e4 10;
double EPS 1e-10;// 考虑误差的加法运算
double add(double a, double b)
{if(abs(a b) EPS * (abs(a) abs(b)))return 0;return a b;
}// 二维向量结构体
struct P
{double x, y;P() {}P(double x, double y){this-x x;this-y y;}void input(){cin x y;}P operator (P p){return P(add(x, p.x), add(y, p.y));}P operator - (P p){return P(add(x, -p.x), add(y, -p.y));}P operator * (double d){return P(x * d, y * d);}double dot(P p) // 内积{return add(x * p.x, y * p.y);}double det(P p) // 外积{return add(x * p.y, -y * p.x);}
};// 判断两条直线是否平行
bool isParallel(P p1, P p2, P q1, P q2)
{return (p1 - p2).det(q1 - q2) 0;
}// 判断点q是否在线段p1p2上
bool on_seg(P p1, P p2, P q)
{return (p1 - q).det(p2 - q) 0 (p1 - q).dot(p2 - q) 0;
}// 计算直线p1p2与直线q1q2的交点
P intersection(P p1, P p2, P q1, P q2)
{// return p1 (p2 - p1) * ((q2 - q1).det(q1 - p1) / (q2 - q1).det(p2 - p1));double t ((q2 - q1).det(q1 - p1) / (q2 - q1).det(p2 - p1));P x ((p2 - p1) * t);return p1 x;
}int n, m;
P p[maxn], q[maxn]; // 一个线段的起点和终点
int A[maxm], B[maxm]; // 题目要询问哪些木棍的连接情况
bool G[maxn][maxn]; // 线段之间的相连关系void floyd()
{for (int k 1; k n; k){for (int i 1; i n; i){for (int j 1; j n; j){G[i][j] | (G[i][k] G[k][j]);}}}
}void solve()
{// 先判断所有的线段两两之间是否有直接的公共点for (int i 1; i n; i){G[i][i] true;for (int j 1; j i; j){if(i j) continue;// 判断线段i和线段j是否有公共点if(isParallel(p[i], q[i], p[j], q[j])){ // 平行时我们检查任一端点是否在另一条线段上来判断两条线段是否有公共点G[i][j] G[j][i] on_seg(p[i], q[i], p[j]) || on_seg(p[i], q[i], q[j]) || on_seg(p[j], q[j], p[i]) || on_seg(p[j], q[j], q[i]);}else{P cross intersection(p[i], q[i], p[j], q[j]);G[i][j] G[j][i] on_seg(p[i], q[i], cross) on_seg(p[j], q[j], cross);}}}// 通过floyd算法判断任意两条线段之间是否连通传递闭包问题floyd();// 输出结果for (int i 1; i m; i){G[A[i]][B[i]] ? cout CONNECTED\n : cout NOT CONNECTED\n;}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin n;while(n ! 0){for (int i 1; i n; i){p[i].input();q[i].input();// cout p[i].x p[i].y q[i].x q[i].y endl;}for (int i 1; ; i){int a, b;cin a b;if(a 0 b 0)break;m i;A[i] a;B[i] b;// cout A[i] B[i] endl;}solve();cin n;}return 0;
}
