首页 > 代码库 > Floyd判最小环算法模板

Floyd判最小环算法模板

2024-07-07 22:21:54   227人阅读

算法思想：如果存在最小环，会在编号最大的点u更新最短路径前找到这个环，发现的方法是，更新最短路径前，遍历i,j点对，一定会发现某对i到j的最短路径长度dis[i][j]+mp[j][u]+mp[u][i] != INF,这时i,j是图中挨着u的两个点，因为在之前最短路更新过程中，u没有参与更新，所以dis[i][j]所表示的路径中不会出现u，如果成立，则一定是一个环。用Floyd算法来实现。但是对于负环此算法失效，因为有负环时，dis[i][j]已经不能保证i到j的路径上不会经过同一个点多次了。

算法代码：

int Floyd_MinCircle()
{
    int Mincircle = Mod;
    int i,j,k;
    for(k=1;k<=n;k++)
    {
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(dis[i][j] != Mod && mp[j][k] != Mod && mp[k][i] != Mod && dis[i][j] + mp[j][k] + mp[k][i] < Mincircle)
                    Mincircle = dis[i][j] + mp[j][k] + mp[k][i];
            }
        }
        //正常Floyd
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(dis[i][k] != Mod && dis[k][j] != Mod && dis[i][k] + dis[k][j] < dis[i][j])
                {
                    dis[i][j] = dis[i][k] + dis[k][j];
                    pre[i][j] = pre[k][j];
                }
            }
        }
    }
    return Mincircle;
}
View Code

 


联系
我们