本文共 1671 字，大约阅读时间需要 5 分钟。

最小环

顾名思义，最小环即为带权图中最短的环路

算法

主要是floyd和dij两种

Floyd

floyd三层循环中，最外层k循环代表用上第k个点的最短路，在刚开始时，所有节点最短路中都是仅包含前k-1个节点的，

我们在floyd跑带有k节点的循环前进行操作，枚举i，j。i-j-k-i为一个可能的环路。其中i-j我们用跑出的dis数组来表示，因为floyd性质确保了i-j的最短路中没有k节点存在，之后j-k和k-i我们用他们之间本来的边来表示，更新答案。

代码

#include
   
    #include
    
     #include
     
      #include
      
     
    
   

迪杰斯特拉

这个算法主要用于以下情况：

• 无向图最小环
• 求经过某一顶点的最小环

若求某一顶点s的最小环，就把s所连的点都加入队列，当然这些点的dis也就是边长（相当于手动处理队列取出s的情况），之后将dis[S]设为inf，当s取出时，即找到了最小环。

对于全图最小环，枚举一遍取min即可

注意不要用这个算法求无向图最小环，不然会变成s走向最近的节点，再原路返回，答案变成了最短边的两倍。

代码

找不到例题，写了个大概意思

void solve(int s){   		memset(dis,0x3f,sizeof(dis));		priority_queue
   
    
,greater
    
 > q;		for(int i=1;i<=n;i++){   			if(i==s)				continue;			if(mp[s][i]!=inf){   				dis[i]=mp[s][i];				q.push({   dis[i],i});			}		}		dis[s]=inf;		while(!q.empty()){   			P p=q.top(); q.pop();			int u=p.second;			if(dis[u]
     
      dis[u]+mp[u][i]){   					dis[i]=dis[u]+mp[u][i];					q.push(P(dis[i],i));				}			}		}	}