在最短路问题中，如果我们面对的是稠密图（十分稠密的那种，比如说全连接图），计算多源最短路的时候，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

如果单纯忽略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
     
       2 #include
      
        3 #include
       
         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
       
      
     

请注意，请注意，请注意

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

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

否则凉凉