floyd(权值非负)适用于有向图和无向图
1 floyd 的思想就是通过枚举n个点利用DP的思想来更新最短距离的，假设当前枚举到第k个点，那么就有任意的两个点i , j ，如果i k 相连 j k 相连 那么就可以知道这个时候dis[i][j] = min(dis[i][j] , dis[i][k] + dis[k][j]);，那么只要枚举完n个点，那么就说明已经完全更新完所有两点直间的最短路。
2 floyd算法是最简单的最短路径的算法，可以计算图中任意两点间的最短路径。floyd算法的时间复杂度为o(n^3)，如果是一个没有边权的图，把相连的两点间的距离设为dis[i][j]=1.不相连的两点设为无穷大，用floyd算法可以判断i j两点是否相连。 3 floyd 算法不允许所有的权值为负的回路。可以求出任意两点之间的最短距离。处理的是无向图 4 缺点是时间复杂度比较高，不适合计算大量数据
5 如果dis[i][i] != 0，说明此时存在环。
6 如果利用floyd求最小值的时候，初始化dis为INF ， 如果是求最大值的话初始化为-1.
7 模板：
[cpp] view plain copy print ? #define INF 0xFFFFFFF #define MAXN 1010 int dis[MAXN][MAXN]; /*如果是求最小值的话，初始化为INF即可*/ void init(){ for(int i = 1 ; i <= n ; i++){ for(int j = 1 ; j <= n ; j++) dis[i][j] = INF; dis[i][i] = 0; } } /*如果是求最大值的话，初始化为-1*/ void init(){ for(int i = 1 ; i <= n ; i++){ for(int j = 1 ; j <= n ; j++) dis[i][j] = -1； } } /*floyd算法*/ void folyd(){ for(int k = 1 ; k <= n ; k++){/*枚举n个点来更新dis*/ for(int i = 1 ; i <= n ; i++){ for(int j = 1 ; j <= n ; j++) if(dis[i][k] != -1 && dis[j][k] != -1)/*如果在求最大值的时候加上这一句*/ dis[i][j] = min(dis[i][k]+dis[k][j] , dis[i][j]); } } } [cpp] view plain copy print ? #define INF 0xFFFFFFF #define MAXN 1010 int dis[MAXN][MAXN]; /*如果是求最小值的话，初始化为INF即可*/ void init(){ for(int i = 1 ; i <= n ; i++){ for(int j = 1 ; j <= n ; j++) dis[i][j] = INF; dis[i][i] = 0; } } /*如果是求最大值的话，初始化为-1*/ void init(){ for(int i = 1 ; i <= n ; i++){ for(int j = 1 ; j <= n ; j++) dis[i][j] = -1； } } /*floyd算法*/ void folyd(){ for(int k = 1 ; k <= n ; k++){/*枚举n个点来更新dis*/ for(int i = 1 ; i <= n ; i++){ for(int j = 1 ; j <= n ; j++) if(dis[i][k] != -1 && dis[j][k] != -1)/*如果在求最大值的时候加上这一句*/ dis[i][j] = min(dis[i][k]+dis[k][j] , dis[i][j]); } } } #define INF 0xFFFFFFF #define MAXN 1010 int dis[MAXN][MAXN]; /*如果是求最小值的话，初始化为INF即可*/ void init(){ for(int i = 1 ; i <= n ; i++){ for(int j = 1 ; j <= n ; j++) dis[i][j] = INF; dis[i][i] = 0; } } /*如果是求最大值的话，初始化为-1*/ void init(){ for(int i = 1 ; i <= n ; i++){ for(int j = 1 ; j <= n ; j++) dis[i][j] = -1； } } /*floyd算法*/ void folyd(){ for(int k = 1 ; k <= n ; k++){/*枚举n个点来更新dis*/ for(int i = 1 ; i <= n ; i++){ for(int j = 1 ; j <= n ; j++) if(dis[i][k] != -1 && dis[j][k] != -1)/*如果在求最大值的时候加上这一句*/ dis[i][j] = min(dis[i][k]+dis[k][j] , dis[i][j]); } } } floyd扩展： 如何用floyd找出最短路径所行经的点： 1 这里要用到另一个矩阵P，它的定义是这样的：p(ij)的值如果为p，就表示i到j的最短行经为i->p…->j，也就是说p是i到j的最短行径中的j之前的第1个点。 2 P矩阵的初值为p(ij) = j。有了这个矩阵之后，要找最短路径就轻而易举了。对于i到j而言找出p(ij)，令为p，就知道了路径i->p….->j；再去找p(pj)，如果值为q，p到j的最短路径为p->q…->j；再去找p(qj)，如果值为r，i到q的最短路径为q>r…->q；所以一再反复，就会得到答案。 3 但是，如何动态的回填P矩阵的值呢？回想一下，当d(ij)>d(ik)+d(kj)时，就要让i到j的最短路径改为走i->…->k->…->j这一条路，但是d(ik)的值是已知的，换句话说，就是i->…->k这条路是已知的，所以i->…->k这条路上k的第一个城市(即p(ik))也是已知的，当然，因为要改走i->…->k->…->j这一条路，p(ij)的第一个城市正好是p(ik)。所以一旦发现d(ij)>d(ik)+d(kj)，就把p(ik)存入p(ij). 4 代码： [cpp] view plain copy print ? int dis[MAXN][MAXN]; int path[MAXN][MAXN]; void floyd(){ int i, j, k; /*先初始化化为j*/ for (i = 1; i <= n; i++){ for (j = 1; j <= n; j++) path[i][j] = j; } for (k = 1; k <= n; k++){/*枚举n个点*/ for (i = 1; i <= n; i++){ for (j = 1; j <= n; j++){ if (dis[i][j] > dis[i][k]+dis[k][j]){ path[i][j] = path[i][k];/*更新为path[i][k]*/ dis[i][j] = dis[i][k]+dis[k][j]; } } } } } [cpp] view plain copy print ? int dis[MAXN][MAXN]; int path[MAXN][MAXN]; void floyd(){ int i, j, k; /*先初始化化为j*/ for (i = 1; i <= n; i++){ for (j = 1; j <= n; j++) path[i][j] = j; } for (k = 1; k <= n; k++){/*枚举n个点*/ for (i = 1; i <= n; i++){ for (j = 1; j <= n; j++){ if (dis[i][j] > dis[i][k]+dis[k][j]){ path[i][j] = path[i][k];/*更新为path[i][k]*/ dis[i][j] = dis[i][k]+dis[k][j]; } } } } } int dis[MAXN][MAXN]; int path[MAXN][MAXN]; void floyd(){ int i, j, k; /*先初始化化为j*/ for (i = 1; i <= n; i++){ for (j = 1; j <= n; j++) path[i][j] = j; } for (k = 1; k <= n; k++){/*枚举n个点*/ for (i = 1; i <= n; i++){ for (j = 1; j <= n; j++){ if (dis[i][j] > dis[i][k]+dis[k][j]){ path[i][j] = path[i][k];/*更新为path[i][k]*/ dis[i][j] = dis[i][k]+dis[k][j]; } } } } } 2 floyd求解环中的最小环1 为什么要在更新最短路之前求最小环： 在第k层循环，我们要找的是最大结点为k的环，而此时Dist数组存放的是k-1层循环结束时的经过k-1结点的最短路径，也就是说以上求出的最短路是不经过k点的，这就刚好符合我们的要求。为什么呢？假设环中结点i,j是与k直接相连，如果先求出经过k的最短路，那么会有这样一种情况，即：i到j的最短路经过k。这样的话就形成不了环 。
2最小环改进算法的证明： 一个环中的最大结点为k(编号最大)，与他相连的两个点为i,j，这个环的最短长度为g[i][k]+g[k][j]+dis[i][j] (i到j的路径中,所有结点编号都小于k的最短路径长度)。根据floyd的原理，在最外层循环做了k-1次之后，dist[i][j]则代表了i到j的路径中，所有结点编号都小于k的最短路径, 综上所述，该算法一定能找到图中最小环。
3 为什么还要value数组： 因为dis数组时刻都在变动不能表示出原来两个点之间的距离。
4 形成环至少要有3点不同的点，两个点是不能算环的。 5 代码：
[cpp] view plain copy print ? int mincircle = INF; int dis[MAXN][MAXN]; int value[MAXN][MAXN]; void floyd(){ memcpy(value , dis , sizeof(value)); for(int k = 1 ; k <= n ; k++){ /*求最小环,不包含第k个点*/ for(int i = 1 ; i < k ; i++){/*到k-1即可*/ for(int j = i+1 ; j < k ; j++)/*到k-1即可*/ mincircle = min(mincircle , dis[i][j]+value[i][k]+value[k][j]);/*无向图*/ mincircle = min(mincircle , dis[i][j] +value[i][k]+value[k][j]);/*表示i->k ， k->j有边*/ } /*更新最短路*/ for(int i = 1 ; i <= n ; i++){ for(int j = 1 ; j <= n ; j++) dis[i][j] = min(dis[i][k]+dis[k][j] , dis[i][j]); } } } [cpp] view plain copy print ? int mincircle = INF; int dis[MAXN][MAXN]; int value[MAXN][MAXN]; void floyd(){ memcpy(value , dis , sizeof(value)); for(int k = 1 ; k <= n ; k++){ /*求最小环,不包含第k个点*/ for(int i = 1 ; i < k ; i++){/*到k-1即可*/ for(int j = i+1 ; j < k ; j++)/*到k-1即可*/ mincircle = min(mincircle , dis[i][j]+value[i][k]+value[k][j]);/*无向图*/ mincircle = min(mincircle , dis[i][j] +value[i][k]+value[k][j]);/*表示i->k ， k->j有边*/ } /*更新最短路*/ for(int i = 1 ; i <= n ; i++){ for(int j = 1 ; j <= n ; j++) dis[i][j] = min(dis[i][k]+dis[k][j] , dis[i][j]); } } } int mincircle = INF; int dis[MAXN][MAXN]; int value[MAXN][MAXN]; void floyd(){ memcpy(value , dis , sizeof(value)); for(int k = 1 ; k <= n ; k++){ /*求最小环,不包含第k个点*/ for(int i = 1 ; i < k ; i++){/*到k-1即可*/ for(int j = i+1 ; j < k ; j++)/*到k-1即可*/ mincircle = min(mincircle , dis[i][j]+value[i][k]+value[k][j]);/*无向图*/ mincircle = min(mincircle , dis[i][j] +value[i][k]+value[k][j]);/*表示i->k ， k->j有边*/ } /*更新最短路*/ for(int i = 1 ; i <= n ; i++){ for(int j = 1 ; j <= n ; j++) dis[i][j] = min(dis[i][k]+dis[k][j] , dis[i][j]); } } }Bellman_Ford(权值可正可负)，用来判断负环
1 Bellman_Frod可以计算边权为负值的最短路问题，适用于有向图和无向图.用来求解源点到达任意点的最短路。
2 在边权可正可负的图中，环有零环，正环，负环3种。如果包含零环和正环的话，去掉以后路径不会变成，如果包含负环则最短路是不存在的。那么既然不包含负环，所以最短路除了源点意外最多只经过n-1个点，这样就可以通过n-1次的松弛得到源点到每个点的最短路径。
3 时间复杂度o(n*m); 4 如果存在环的话就是经过n-1次松弛操作后还能更新dis数组。 5 模板：
[cpp] view plain copy print ? /* 适用条件： 1单源最短路径 2有向图和无向图 3边权可正可负 */ #define INF 0xFFFFFFF #define MAXN 1010*2 int dis[MAXN];/*dis[i]表示的是源点到点i的最短路*/ strucu Edge{ int x; int y; int value; }e[MAXN]; /*返回最小值*/ int min(int a , int b){ return a < b ? a : b; } /*处理成无向图*/ void input(){ for(int i = 0 ; i < m ; i++){ scanf(“%d%d%d” , e[i].x , &e[i].y , &e[i].value); e[i+m].x = e[i].y;/*注意地方*/ e[i+m].y = e[i].x;/*注意地方*/ e[i+m].value = e[i].value; } } /*假设现在有n个点，m条边*/ void Bellman_Ford(int s){ /*初始化dis数组*/ for(int i = 1 ; i <= s ; i++) dis[i] = INF; dis[s] = 0; for(int i = 1 ; i < n ; i++){/*做n-1次松弛*/ for(int j = 0 ; j < 2*m ; j++){/*每一次枚举2*m条边，因为是无向图*/ if(dis[e[j].y] > dis[e[j].x] + e[j].value) dis[e[j.].y] = dis[e[i].x]+e[j].value;/*更新dis[e[j].y]*/ } } } } [cpp] view plain copy print ? /* 适用条件： 1单源最短路径 2有向图和无向图 3边权可正可负 */ #define INF 0xFFFFFFF #define MAXN 1010*2 int dis[MAXN];/*dis[i]表示的是源点到点i的最短路*/ strucu Edge{ int x; int y; int value; }e[MAXN]; /*返回最小值*/ int min(int a , int b){ return a < b ? a : b; } /*处理成无向图*/ void input(){ for(int i = 0 ; i < m ; i++){ scanf(”%d%d%d” , e[i].x , &e[i].y , &e[i].value); e[i+m].x = e[i].y;/*注意地方*/ e[i+m].y = e[i].x;/*注意地方*/ e[i+m].value = e[i].value; } } /*假设现在有n个点，m条边*/ void Bellman_Ford(int s){ /*初始化dis数组*/ for(int i = 1 ; i <= s ; i++) dis[i] = INF; dis[s] = 0; for(int i = 1 ; i < n ; i++){/*做n-1次松弛*/ for(int j = 0 ; j < 2*m ; j++){/*每一次枚举2*m条边，因为是无向图*/ if(dis[e[j].y] > dis[e[j].x] + e[j].value) dis[e[j.].y] = dis[e[i].x]+e[j].value;/*更新dis[e[j].y]*/ } } } } /* 适用条件： 1单源最短路径 2有向图和无向图 3边权可正可负 */ #define INF 0xFFFFFFF #define MAXN 1010*2 int dis[MAXN];/*dis[i]表示的是源点到点i的最短路*/ strucu Edge{ int x; int y; int value; }e[MAXN]; /*返回最小值*/ int min(int a , int b){ return a < b ? a : b; } /*处理成无向图*/ void input(){ for(int i = 0 ; i < m ; i++){ scanf("%d%d%d" , e[i].x , &e[i].y , &e[i].value); e[i+m].x = e[i].y;/*注意地方*/ e[i+m].y = e[i].x;/*注意地方*/ e[i+m].value = e[i].value; } } /*假设现在有n个点，m条边*/ void Bellman_Ford(int s){ /*初始化dis数组*/ for(int i = 1 ; i <= s ; i++) dis[i] = INF; dis[s] = 0; for(int i = 1 ; i < n ; i++){/*做n-1次松弛*/ for(int j = 0 ; j < 2*m ; j++){/*每一次枚举2*m条边，因为是无向图*/ if(dis[e[j].y] > dis[e[j].x] + e[j].value) dis[e[j.].y] = dis[e[i].x]+e[j].value;/*更新dis[e[j].y]*/ } } } }SPFA(权值可正可负)，判断负环. 1用来求解单源最短路径，源点到任意点的最短路。 2 算法介绍：建立一个队列q，初始时队列里只有一个起始点，在建立一个数组dis记录起始点到所有点的最短路径，并且初始化这个数组。然后进行松弛操作，用 队列里面的点去刷新起始点到所有点的最短路，如果刷新成功且刷新点不再队列中则把该点加入到队列最后，重复执行直到队列为空。 3 时间复杂度：O(ke),k指的是所有顶点的进队的平均次数，可以证明k<=2，e为边数 4 可以用SPFA来存在是否存在环，如果是的话就是存在一条边的松弛操作大于等于n。 5 模板：
[cpp] view plain copy print ? /* 1 n个点 m条边 2 邻接表存储图: first[i]存储的是节点i的第一条边的编号，nest[i]存储的是编号为i的边的下一条边的编号。 3 star[i]表示编号为i的边的起点，end[i]表示编号为i的边的终点，value[i]表示编号为i的边的权值。 4 dis[i] 表示的源点到i的最短路 */ #define MAXN 1010 #define INF 0xFFFFFFF int n , m; int first[MAXN] , next[MAXN]; int star[MAXN] , end[MAXN] , value[MAXN]; int dis[MAXN]; queue<int>q; /*输入*/ void input(){ scanf(“%d%d” , &n , &m); /*初始化表头*/ for(int i = 1 ; i <= n ; i++){ first[i] = -1; next[i] = -1; } /*读入m条边*/ for(int i = 0 ; i < m ; i++){ scanf(“%d%d%d” , &star[i] , &end[i] , &value[i]); star[i+m] = end[i]; end[i+m] = star[i]; value[i+m] = value[i]; next[i] = first[star[i]];/*由于要插入表头，所以将原先表头后移*/ first[star[i]] = i;/*插入表头*/ next[i+m] = first[star[i+m]]; first[star[i+m]] = i+m; } } /*SPFA*/ void SPFA(int s){ while(!q.empty()) q.pop(); int vis[MAXN]; memset(vis , 0 , sizeof(vis)); /*初始化dis*/ for(int i = 1 ; i <= n ; i++) dis[i] = INF; dis[s] = 0; q.push(s);/*将源点加入队列*/ vis[s] = 1;/*源点标记为1*/ while(!q.empty()){ int x = q.front(); q.pop(); vis[x] = 0;/*注意这里要重新标记为0，说明已经出队*/ /*枚举和点x有关的所有边*/ for(int i = first[x] ; i != -1 ; i = next[i]){ if(dis[end[i]] > dis[x] + value[i]){/*松弛操作，利用三角不等式*/ dis[end[i]] = dis[x] + value[i]; if(!vis[end[i]]){/*如果该点不再队列里面*/ vis[end[i]] = 1; q.push(end[i]); } } } } [cpp] view plain copy print ? /* 1 n个点 m条边 2 邻接表存储图: first[i]存储的是节点i的第一条边的编号，nest[i]存储的是编号为i的边的下一条边的编号。 3 star[i]表示编号为i的边的起点，end[i]表示编号为i的边的终点，value[i]表示编号为i的边的权值。 4 dis[i] 表示的源点到i的最短路 */ #define MAXN 1010 #define INF 0xFFFFFFF int n , m; int first[MAXN] , next[MAXN]; int star[MAXN] , end[MAXN] , value[MAXN]; int dis[MAXN]; queue<int>q; /*输入*/ void input(){ scanf(”%d%d” , &n , &m); /*初始化表头*/ for(int i = 1 ; i <= n ; i++){ first[i] = -1; next[i] = -1; } /*读入m条边*/ for(int i = 0 ; i < m ; i++){ scanf(”%d%d%d” , &star[i] , &end[i] , &value[i]); star[i+m] = end[i]; end[i+m] = star[i]; value[i+m] = value[i]; next[i] = first[star[i]];/*由于要插入表头，所以将原先表头后移*/ first[star[i]] = i;/*插入表头*/ next[i+m] = first[star[i+m]]; first[star[i+m]] = i+m; } } /*SPFA*/ void SPFA(int s){ while(!q.empty()) q.pop(); int vis[MAXN]; memset(vis , 0 , sizeof(vis)); /*初始化dis*/ for(int i = 1 ; i <= n ; i++) dis[i] = INF; dis[s] = 0; q.push(s);/*将源点加入队列*/ vis[s] = 1;/*源点标记为1*/ while(!q.empty()){ int x = q.front(); q.pop(); vis[x] = 0;/*注意这里要重新标记为0，说明已经出队*/ /*枚举和点x有关的所有边*/ for(int i = first[x] ; i != -1 ; i = next[i]){ if(dis[end[i]] > dis[x] + value[i]){/*松弛操作，利用三角不等式*/ dis[end[i]] = dis[x] + value[i]; if(!vis[end[i]]){/*如果该点不再队列里面*/ vis[end[i]] = 1; q.push(end[i]); } } } } /* 1 n个点 m条边 2 邻接表存储图: first[i]存储的是节点i的第一条边的编号，nest[i]存储的是编号为i的边的下一条边的编号。 3 star[i]表示编号为i的边的起点，end[i]表示编号为i的边的终点，value[i]表示编号为i的边的权值。 4 dis[i] 表示的源点到i的最短路 */ #define MAXN 1010 #define INF 0xFFFFFFF int n , m; int first[MAXN] , next[MAXN]; int star[MAXN] , end[MAXN] , value[MAXN]; int dis[MAXN]; queue<int>q; /*输入*/ void input(){ scanf("%d%d" , &n , &m); /*初始化表头*/ for(int i = 1 ; i <= n ; i++){ first[i] = -1; next[i] = -1; } /*读入m条边*/ for(int i = 0 ; i < m ; i++){ scanf("%d%d%d" , &star[i] , &end[i] , &value[i]); star[i+m] = end[i]; end[i+m] = star[i]; value[i+m] = value[i]; next[i] = first[star[i]];/*由于要插入表头，所以将原先表头后移*/ first[star[i]] = i;/*插入表头*/ next[i+m] = first[star[i+m]]; first[star[i+m]] = i+m; } } /*SPFA*/ void SPFA(int s){ while(!q.empty()) q.pop(); int vis[MAXN]; memset(vis , 0 , sizeof(vis)); /*初始化dis*/ for(int i = 1 ; i <= n ; i++) dis[i] = INF; dis[s] = 0; q.push(s);/*将源点加入队列*/ vis[s] = 1;/*源点标记为1*/ while(!q.empty()){ int x = q.front(); q.pop(); vis[x] = 0;/*注意这里要重新标记为0，说明已经出队*/ /*枚举和点x有关的所有边*/ for(int i = first[x] ; i != -1 ; i = next[i]){ if(dis[end[i]] > dis[x] + value[i]){/*松弛操作，利用三角不等式*/ dis[end[i]] = dis[x] + value[i]; if(!vis[end[i]]){/*如果该点不再队列里面*/ vis[end[i]] = 1; q.push(end[i]); } } } }