图的最小环问题

最小环问题

1. 最小环定义:

  • 最小环是指在一个图中,有n个节点构成的边权和最小的环(n>=3)

  • 一般来说,最小环分为有向图最小环和无向图最小环。

2. 最小环算法

  1. Dijkstra解法
    • uv之间有一条边长为w的边,dis(u,v)表示删除uv之间的连边之后,uv之间的最短路。
    • 那么最小环是枚举每一条边,并删除此条边后,以其中一个端点为起点跑一边单源最短路最小环的值为:min(dis(u,v)+w)
    • 时间效率为:\(O(m*n*log\ n)\) ,对稠密图来说边数 \(m\) 趋近 \(n^2\), 所以时间效率为 \(O(n^3log\ n)\)。
  2. Floyd 解法
    • 记原图u,v之间边权为mp(u,v),floyd算法在外层循环到第k个点时(还没开始第k次循环),最短路数组dis中,dis(u,v)表示的是从uv且仅经过编号[1,k)区间中的点的最短路。
    • 最小环至少有三个顶点,设其中编号最大的顶点编号为w,环上与w相邻两侧的两个点为u,v,则在最外层循环枚举到k=w时,该环的长度为dis(u,v)+mp(v,w)+mp(w,u),所以在循环时候i,j只需枚举到i<k,j<k更新答案即可。
    • 复杂度:\(O(n^3)\)

3. 例题

  1. find the mincost route(hdu1599)

    Description
    • 杭州有N个景区,景区之间有一些双向的路来连接,现在8600想找一条旅游路线,这个路线从A点出发并且最后回到A点,假设经过的路线为\(V_1,V_2,....V_K,V_1\),那么必须满足\(K>2\) ,就是说至除了出发点以外至少要经过2个其他不同的景区,而且不能重复经过同一个景区。现在8600需要你帮他找一条这样的路线,并且花费越少越好。
    Input
    • 第一行是2个整数NM(N <= 100, M <= 1000),代表景区的个数和道路的条数。
    • 接下来的M行里,每行包括3个整数a,b,c.代表ab之间有一条通路,并且需要花费c(c <= 100)
    Output
    • 对于每个测试实例,如果能找到这样一条路线的话,输出花费的最小值。如果找不到的话,输出It's impossible.
    Sample Input
    3 3
    1 2 1
    2 3 1
    1 3 1
    3 3
    1 2 1
    1 2 3
    2 3 1
    
    Sample Output
    3
    It's impossible.
    
    Hint
    • 有可能存在重边,保留权值最小那条。
    Code
    #include <bits/stdc++.h>
    #define Inf 0x3f3f3f3f
    typedef long long LL;
    const int maxn=100+5;
    LL dis[maxn][maxn],mp[maxn][maxn]; //注意开longlong
    int n, m;
    void Init(){	
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                mp[i][j] = i == j ? 0 : Inf;
    }
    void Solve(){
    	while(~scanf("%d%d", &n, &m)){
    		Init();//多组数据注意初始化
    		for (int i = 0; i < m; i++){
    	        int u, v; LL w;
    	        scanf("%d%d%lld", &u, &v, &w);
    	        if (w < mp[u][v])//处理重边,保留权值小的
    	            mp[v][u] = mp[u][v] = w;
    	    }
    	    for (int i = 1; i <= n; i++)
    	        for (int j = 1; j <= n; j++)
    	            dis[i][j] = mp[i][j];//初始化两点间的距离
    	    LL ans = Inf;
    	    for (int k = 1; k <= n; k++){//枚举中间点
    	        for (int i = 1; i < k; i++)//枚举k的其中一个相邻点
    	            for (int j = i + 1; j < k; j++)//枚举k的另一相邻点
    	                ans = std::min(ans, dis[i][j] + mp[i][k] + mp[k][j]);
                		//上面暂时不能以k为中间点更新dis[i][j],如果更新可能不是环
    	        for (int i = 1; i <= n; i++)//k无用了,可以用来更新
    	            for (int j = 1; j <= n; j++)
    	                dis[i][j] = std::min(dis[i][j], dis[i][k] + dis[k][j]);
    	    }
    	    if (ans == Inf)
    	        printf("It's impossible.\n");
    	    else
    	        printf("%lld\n", ans);
    	}
        
    }
    int main(){
        Solve();
        return 0;
    }
    

4. 总结

  • 求最小环问题我们一般用Floyd,相较于DijskraFloyd 更简单且高效
  • 对有有向图的最小环问题,我们直接用Floyd跑一遍最短路,然后遍历一遍1~n,求出min(dis[i][i])即可,显然初始是dis[i][i]=Inf
  • 并查集、Tarjan均可求环,但他们只能求只有简单环的图,对有切环、套环的图无法求最小环。
  • 要想求图中节点最少的环,我们可以把边权设为1,然后用Floyd求最小环。
上一篇:Floyd : 传递闭包


下一篇:最完整+全解析的Floyd算法(C++版)