Floyd 的 改进写法可以解决最小环问题，时间复杂度依然是 O(n^3)，储存结构也是邻接矩阵
 
int mincircle = infinity;
Dist = Graph;

for(int k=0;k<nVertex;++k){
    //新增部分:
    for(int i=0;i<k;++i)
        for(int j=0;j<i;++j)
            mincircle = min(mincircle,Dist[i][j]+Graph[j][k]+Graph[k][i]);
    //通常的 floyd 部分:
    for(int i=0;i<nVertex;++i)
        for(int j=0;j<i;++j){
            int temp = Dist[i][k] + Disk[k][j];
            if(temp < Dist[i][j])
                Dist[i][j] = Dist[j][i] = temp;
        }
}

 
上面是对无向图的情况。
Floyd 算法保证了最外层循环到 k 时所有顶点间已求得以 0…k-1 为中间点的最短路径。一个环至少有3个顶点，设某环编号最大的顶点为 L ，在环中直接与之相连的两个顶点编号分别为 M 和 N (M,N < L)，则最大编号为 L 的最小环长度即为 Graph(M,L) + Graph(N,L) + Dist(M,N) ，其中 Dist(M,N) 表示以 0…L-1 号顶点为中间点时的最短路径，刚好符合 Floyd 算法最外层循环到 k=L 时的情况，则此时对 M 和 N 循环所有编号小于 L 的顶点组合即可找到最大编号为 L 的最小环。再经过最外层 k 的循环，即可找到整个图的最小环。
 
若是有向图，只需稍作改动。注意考虑有向图中2顶点即可组成环的情况。