Floyd算法（最短路）

如题，这是最短路算法Floyd。

Floyd，是只有五行的代码。

简单，易懂。O(N的三方)的时间也可以。

遇到简单的就这么用。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<queue>

#define s(q) scanf("%d",&q)

#define p(q) printf("%d",q)

#define pk(q) printf(" %d",q)

#define pp printf("\n")

#define lp(q) printf("%lld",q)

#define r(q) return q;

#define ffor(i,l,k) for(i=l;i<=k;i++)

using namespace std;

int n,i,j,k;

int a[][];

void Floyd(){

    ffor(i,,n)

        ffor(j,,n)

            ffor(k,,n)

                if(a[i][j]>a[k][j]+a[i][k] && a[k][j]+a[i][k]>)

                    a[i][j]=a[k][j]+a[i][k];

}

int main(){

    s(n);

    ffor(i,,n)

        ffor(j,,n)

            s(a[i][j]);

    Floyd();

    /*ffor(i,1,n){

        ffor(j,1,n){

            pk(a[i][j]);

        }pp;

    }*/

    r();

}

这一条是不是很简单？

Floyd的作用就是帮你寻找两个点的最短路，就是：

如果i点到j点的路线大于i点到k点，然后再转到j点的路线，那么你就可以将i点到j点的路线替换为i点到k点，然后再转到j点的路线。

如果说两条边不能通，设为正无穷也可以。

我的输入可以改成：

现将所有的点与点的边变为正无穷，然后在输入某一点到另一点的，更新数据，再Floyd。

注意：要找到不能找为止！

值得一提的是，Floyd并不能“负权回路”，因为这种东西没有最短路。

就像这样：1->2->3->1->2......1->2->3......每一次循环最短路就会减少1，永远找不到。

如果要快，可以用Dijkstra算法（空间复杂度O(M)，时间复杂度O(M+N)logN）以及Bellman-Ford及其优化（空间复杂度O(M)，时间复杂度O(NM)或最坏O(NM)）

额，Floyd空间复杂度是O(N的2方)，时间复杂度是O(N的3方)。

如果你看不清楚上面的Floyd就看下面这个没有#define的。

void Floyd(){

    for(i=;i<=n;i++)

        for(j=;j<=n;j++)

            for(k=;k<=n;k++)

                if(a[i][j]>a[k][j]+a[i][k] && a[k][j]+a[i][k]>)

                    a[i][j]=a[k][j]+a[i][k];

}

应该没有人不知道a[i][j]干什么吧？

a是用来贮存最短路的。

巴特西

Floyd算法（最短路）

最新文章

热门文章