任意两点最短路径 最短路之floyd

本人水平有限，题解不到为处，请多多谅解

本蒟蒻谢谢大家观看

floyd算法：

设D[k,i,j]表示“经过若干个编号不超过k的节点” 从i到j的最短路径长度

D[k,i,j]=min(D[k-1,i,j]，D[k-1,i,k]+D[k-1,k,j])；

初始为D[0,i,j]=A[i,j]；A为邻接矩阵

设有向图G=(V,E),V为点集，E为边集，（x,y）表示一条从x到y的有向图，其边权(或称长度)为W(x,y)。设n=|V|，m=|E|，邻接矩阵A是一个n*n的矩阵。

A的定义如下：

A[i,j]={　　0　　　i=j

　　　　　w(i,j)　 (i,j)属于E

　　　　　+∞　  （i,j)不属于E

　　  }

所以k为阶段，所以必须置于最外层循环中

省略k这一维之后的DP

D[i,j]=min(D[i,k]+D[k,j])；

最终D[i,j]为i到j的最短路径长度

 模板如下：

code:

#include<bits/stdc++.h>
#pragma GCC optimize(3)

using namespace std;
int n,m;
int f[310][310];
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch==‘-‘)f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
inline void write(int x)
{
    if(x<0)x=-x,putchar(‘-‘);
    if(x>9)write(x/10);
    putchar(x%10+‘0‘);
}
int main()
{
    memset(f,0x3f,sizeof(f));//初始距离最大 
    for(int i=1;i<=n;i++)f[i][i]=0;//自己到自己的距离为0 
    n=read(),m=read();
    for(int i=1,x,y,z;i<=m;i++){
        x=read(),y=read(),z=read();
        f[x][y]=min(f[x][y],z);//建邻接矩阵 
    }
    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]);
            }
        }
    }
    return 0;
}

应用：

传递闭包

code:

#include<bits/stdc++.h>
#pragma GCC optimize(3)

using namespace std;
int n,m;
bool f[310][310];
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch==‘-‘)f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
inline void write(int x)
{
    if(x<0)x=-x,putchar(‘-‘);
    if(x>9)write(x/10);
    putchar(x%10+‘0‘);
}
int main()
{
    for(int i=1;i<=n;i++)f[i][i]=1; 
    n=read(),m=read();
    for(int i=1,x,y,z;i<=m;i++){
        x=read(),y=read(),z=read();
        f[x][y]=f[y][x]=1;
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                f[i][j]|=f[i][k]&f[k][j];
            }
        }
    }
    return 0;
}