首先前提是原图不能有负权边, 否然会爆。
有向图使用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]; }
Join the discussion