图论：Floyd-多源最短路、无向图最小环

在最短路问题中，如果我们面对的是稠密图（十分稠密的那种，比如说全连接图），计算多源最短路的时候，Floyd算法才能充分发挥它的优势，彻彻底底打败SPFA和Dijkstra

在别的最短路问题中都不推荐使用这个算法

我们以一道单源最短路题目介绍一下在输入数据为边表的情况下的Floyd使用情况，如果直接给了邻接矩阵的话，直接无脑求就可以了

在这里，我们把Floyd算法的功能补全，实现了一个打印最短路径的函数并加入了求无向图的最小环的功能（经过至少两个定点，权值和最小）

看定义：

int n,m,s,mina=INF;
int d[maxn][maxn],mp[maxn][maxn],p[maxn][maxn];

n个点m条边和源点s,最小环初始化为INF

然后d是最短路的答案数组，mp是初始地图数组，p是记录两个点之间的衔接点k,用来打印路径

然后是初始化：

void init()
{
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        d[i][j]=mp[i][j]=INF;
    for(int i=1;i<=n;i++) d[i][i]=mp[i][i]=0;
}

这里注意，如果给的是边表，必须要这么做，如果给的是矩阵，可以直接忽略这个函数了

然后是Floyd算法：

void floyd()
{
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<k;i++)  
        for(int j=i+1;j<k;j++)   
            mina=min(d[i][j]+mp[j][k]+mp[k][i],mina); 
             
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        if(d[i][k]<INF&&d[k][j]<INF)
            d[i][j]=min(d[i][j],d[i][k]+d[k][j]),p[i][j]=k;
    }
}

如果单纯忽略mina的求解过程，这就是一个裸的，Floyd

我们再看一下路径是怎么打印的，其实很显然：

void output(int i,int j)
{
    if(i==j) return;
    if(p[i][j]==0) printf("%d ",j);
    else{output(i,p[i][j]);output(p[i][j],j);}
}

递归的思路还是很明显的

我们给出完整的实现：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxn=1005;
 6 const int maxm=2005;
 7 const int INF=0x7fffffff;
 8 int n,m,s,mina=INF;
 9 int d[maxn][maxn],mp[maxn][maxn],p[maxn][maxn];
10 void init()
11 {
12     for(int i=1;i<=n;i++)
13     for(int j=1;j<=n;j++)
14         d[i][j]=mp[i][j]=INF;
15     for(int i=1;i<=n;i++) d[i][i]=mp[i][i]=0;
16 }
17 void floyd()
18 {
19     for(int k=1;k<=n;k++)
20     {
21         for(int i=1;i<k;i++)  
22         for(int j=i+1;j<k;j++)   
23             mina=min(d[i][j]+mp[j][k]+mp[k][i],mina); 
24              
25         for(int i=1;i<=n;i++)
26         for(int j=1;j<=n;j++)
27         if(d[i][k]<INF&&d[k][j]<INF)
28             d[i][j]=min(d[i][j],d[i][k]+d[k][j]),p[i][j]=k;
29     }
30 }
31 void output(int i,int j)
32 {
33     if(i==j) return;
34     if(p[i][j]==0) printf("%d ",j);
35     else{output(i,p[i][j]);output(p[i][j],j);}
36 }
37 int main()
38 {
39     scanf("%d%d%d",&n,&m,&s);
40     int x,y,z;
41     init();
42     for(int i=1;i<=m;i++) {scanf("%d%d%d",&x,&y,&z);mp[x][y]=d[x][y]=min(z,d[x][y]);}
43     floyd();
44     for(int i=1;i<=n;i++) printf("%d ",d[s][i]);
45     return 0;
46 }

请注意，请注意，请注意

在不保证没有重边的情况下，一定要有

mp[x][y]=d[x][y]=min(z,d[x][y]);

否则凉凉