无向图带权最小简单环 弗洛伊德算法

首先前提是原图不能有负权边,  否然会爆。

有向图使用floyd算法寻找最小权简单环可以直接暴力一波自己到自己的距离, 但是无向图就不可以, 因为可能会经过重边。

对于无向图求最小简单环可以这么搞:

先枚举k, 那么可以保证现在的路径不包含k, 然后枚举ij和k连成环, 由于边是正权的所以如果重复经过一条边那么答案一定不优, 点也不会重复经过。

口胡非常混乱…看代码吧

代码

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]+g[i][k]+g[k][j]<ans)//由于此处会存在三个INF相加，所以INF设小一点
 	                  ans=dis[i][j]+g[i][k]+g[k][j];  
  
        for(int i=1;i<=n;++i)//更新最短路  
            for(int j=1;j<=n;++j)  
                if(dis[i][j]>dis[i][k]+dis[k][j])  
                    dis[i][j]=dis[i][k]+dis[k][j];  
    }