如何求无向图的最小环

POJ1734
题意：给定一个N个点的无向图，求一个最小环(各边权值和最小的环)并输出路径。


样例:
Sample Input

5 7   （图有五个点,七条边)
1 4 1  (顶点1与4之间有一条边,权值为1,以下同)
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20

Sample Output

1 3 5 2



思路：朴素的求法是：枚举每一条边（假设为e(i,j)），删除它，再求(i,j)之间的最短距离(用Dijkstra算法），该环就是dis(i,j) + e(i,j)。这样就需要依次枚举每条边，然后求一次最短路，时间复杂度为：O(N*N*M), 在N和M的数据规模较大时就会超时。

有一种改进的算法， 就是在求两点之间的最短路的时候，顺便求出最小环，即Floyd求最小环法。代码为：

void Floyd(){  
    for(int k=1;k<=N;k++){//环中的最大结点编号   
        for(int i=1;i<k;i++){//依次枚举k两端的结点 i , j   
            for(int j=i+1;j<k;j++){  
                ans = MIN(ans, dis[i][j] + G[i][k] + G[k][j]);//最大节点为k的环的最短路径
            }  
        }  
        for(int i=1;i<=N;i++){  
            for(int j=1;j<=N;j++){  
                dis[i][j] = MIN(dis[i][j] , dis[i][k] + dis[k][j]);  
            }  
        }  
    }  
 }  

该算法的证明：

   一个环中的最大结点为K（编号最大），与其相连的两个点为i,j ，这个环的最短长度为： G[i][k] + G[k][j ] + i到j的路径中所有结点编号都不大于k的最短路径长度，根据floyd的原理，在最外层循环做一个k-1次之后， dis[i][j] 则代表了i到j的路径中所有结点的编号都不大于k的最短路径。

本题的代码：
import java.util.Scanner;
public class Main{
 static final int INF = 0x3f3f3f3f ;  
 private int n;  //顶点数
 private int[][] maze;  //邻接矩阵
 private int[][] dis;  //dis[][]保存可以达到的最短距离，会变化； 
 private int[][] fa;  //标记(i,j)最短路径上，距离j最近的那个结点   
 private int[] res;//保存最小环的路径
 private int temp;

  public Main(int n,int[][] fa,int[][] maze){
     this.n=n;
     this.fa=fa;
     this.maze=maze;
     dis=new int[n+1][n+1];
     res=new int[n+1];
     
  }
  

 private void solve(int i, int j ,int k){//记录最小环的路径    
    temp = 0 ;  
    while(j != i){  
        res[temp++] = j  ;  
        j = fa[i][j] ;  
    }  
    res[temp++] = i ;  
    res[temp++] = k ;  
}  

 private void Floyd(){  //Floyd求任意两点i,j之间的最短距离dis[i][j]
    for(int i=1;i<=n;i++){  
        for(int j=1;j<=n;j++){  
            dis[i][j] = maze[i][j] ;  
        }  
    }  
    int ans = INF ;  
    for(int k=1;k<=n;k++){  
        for(int i=1;i<k;i++){  
            for(int j=i+1;j<k;j++){  
                if(dis[i][j]<INF && maze[i][k]<INF && maze[k][j]<INF && ans>dis[i][j] + maze[i][k] + maze[k][j]){  
                    ans = dis[i][j] + maze[i][k] + maze[k][j] ; //最大节点为k的环的最短路径
                    solve(i,j,k); //记录环的各顶点 
                }  
            }  
        }  
        for(int i=1;i<=n;i++){  
            for(int j=1;j<=n;j++){  
                if(dis[i][k]<INF && dis[k][j]<INF && dis[i][j]>dis[i][k] + dis[k][j]){  
                    dis[i][j] = dis[i][k] + dis[k][j] ;  
                    fa[i][j] = fa[k][j] ;  
                    fa[j][i] = fa[k][i] ;  
                }  
            }  
        }     
    }  
    if(ans == INF){  
        System.out.printf("No solution.\n");  
    }  
    else{  
        for(int i=0;i<temp;i++){  
            System.out.printf("%d%c",res[i],i==temp-1?'\n':' ');  
        }  
    }  
} 
 public static void  main(String args[]){  
    Scanner in=new Scanner(System.in);
    int a ,b ,c ;  
    while(in.hasNext()){  
       int n=in.nextInt();//顶点数
       int m=in.nextInt();//边数
       int maze[][]=new int[n+1][m+1];
       int fa[][]=new int[n+1][n+1];
        for(int i=1;i<=n;i++){  //初始化图
            for(int j=1;j<=m;j++){  
                if(i == j)  maze[i][j] = 0;   
                else        maze[i][j] = INF ;  
            }  
        }  
        for(int i=1;i<=m;i++){  
           a=in.nextInt();//边的一端
           b=in.nextInt();//边的另一端
           c=in.nextInt();//边的权
           if(maze[a][b] > c){  //重边取权小的
                maze[a][b] = maze[b][a] = c ;  
                fa[a][b] = a ; //标记(i,j)最短路径上，距离j最近的那个结点    
                fa[b][a] = b ;    
            }     
        }  
       Main ma=new Main(n,fa,maze);
        ma.Floyd() ;  
    }     
 }
}  

源码: