算法总结——Floyed

浏览数：34 / 时间：2015年06月08日

Floyed：

复杂度：O（n^3)

用途：求一条路走完所有的地方的的最小值，很简单，就三个for，一般写floyed不谢bellman_ford~~~

适用条件：遍历所有的点，适合于稠密图，floyed与bellman_ford算法之间的区别就是floyed计算了从每一点开始的值，最后只要选取就行，方便写，但是复杂度高了

原理：利用邻接矩阵判断，而bellman_ford是利用一个数组d进行判断（其实应该可以相互转换把- -||）

步骤：1.把所有的边赋值无穷大，能通过的赋值 2. 三个for循环，k,i,j, k表示从i->j可以走i->k->j，不断取小值 3.选取出发点和结束点，直接输出就是最短路

模板：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int  MAX = 300;
const int inf = 0x3f3f3f3f;
int d[MAX],map[MAX][MAX];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n ; i++)
        for(int j = 1; j <= n; j++)
          map[i][j] = inf;
    int x, y, t;
    for(int i = 1;i <=m;i++){
        scanf("%d%d%d",&x,&y,&t);
        map[x][y] = t;
    }
    for(int k = 1; k <= n ;k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n;j++){
                    if(i!=k&&i!=j)
                map[i][j] = min(map[i][j], map[i][k]+map[k][j]);
            }
        }
    }
    printf("%d",map[1][2]);
    return 0;
}