344 观光之旅（floyd算法求解最小环）

系统管理员 2022-09-17 04:27 177阅读 0赞

**1. 问题描述：**

给定一张无向图，求图中一个至少包含 3 个点的环，环上的节点不重复，并且环上的边的长度之和最小。该问题称为无向图的最小环问题。你需要输出最小环的方案，若最小环不唯一，输出任意一个均可。

**输入格式**

第一行包含两个整数 N 和 M，表示无向图有 N 个点，M 条边。接下来 M 行，每行包含三个整数 u，v，l，表示点 u 和点 v 之间有一条边，边长为 l。

**输出格式**

输出占一行，包含最小环的所有节点（按顺序输出），如果不存在则输出 No solution.。

**数据范围**

1 ≤ N ≤ 100，  
1 ≤ M ≤ 10000，  
1 ≤ l < 500

**输入样例：**

5 7  
1 4 1  
1 3 300  
3 1 10  
1 2 16  
2 3 100  
2 5 15  
5 3 20

**输出样例：**

1 3 5 2  
来源：[https://www.acwing.com/problem/content/description/346/][https_www.acwing.com_problem_content_description_346]

**2. 思路分析：**

分析题目可以知道这是一道最优化的问题，所以可以以集合的角度来分析这个问题（类似于动态规划的分析过程），以集合的角度来分析问题的一个关键的步骤是将当前的状态划分为若干个子集，求解每一个子集的最值那么就可以得到整个集合的最值，对于这道题目来说我们可以将所有的的环按照环上最大的编号进行分类，那么可以分为1，2，3...n，求解每一个子集的最小值那么就可以得到所有环的最小值，我们回忆一下floyd算法的流程，最外层的循环是中间点k，第二层循环是起点i，第三层循环是终点j，当我们进入第二层循环之前那么其实得到的是中间点编号为1~k-1的任意两点之间的最短路径，我们恰恰是可以利用floyd算法第二层循环外的位置来求解第k类的最小值，枚举以中间点k为最大的编号的环的路径的最小值，这样就可以求解出当前环中编号最大的为k的路径的最小值，求解每一个子集的最小值那么就可以求解出整个集合的最小值，这道题目比较棘手的地方是需要求解最小环的方案，我们知道图论中更新最小距离的时候：d(i，j) >= d(i，k) + d(k，j)，所以我们可以使用一个二维数组pos，其中pos\[i\]\[j\]存储起点为i终点为j的最短路径中是由哪一个中间点k更新过来的，并且由循环的特点可以知道k一定是所有中间点中编号最大的，所以我们可以利用这个特点递归求解方案即可，借助于pos数组求解i->k的环的编号和k->j的环的编号，因为需要保证环的顺序，所以在递归求解的时候需要使用中序遍历的顺序来依次添加i->j的环的编号。在添加环中i，j，k三个点的编号的时候也需要注意添加的顺序防止出现错误。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_19_color_FFFFFF_t_70_g_se_x_16][]

**3. 代码如下：**

from typing import List
    
    
    class Solution:
        # 使用一个全局变量来记录当前环中节点编号的对应位置
        count = 0
    
        def getPath(self, i: int, j: int, path: List[int], pos: List[List[int]]):
            if pos[i][j] == 0: return
            k = pos[i][j]
            # 类似于中序遍历的顺序添加i->j的环的编号的顺序这样就可以保证环的顺序
            self.getPath(i, k, path, pos)
            path[self.count] = k
            self.count += 1
            self.getPath(k, j, path, pos)
    
        def floyd(self, n: int, g: List[List[int]], dis: List[List[int]]):
            res = 10 ** 10
            path = [0] * n
            # pos记录两点之间的最短距离是由哪一个中间点转移过来的
            pos = [[0] * (n + 1) for i in range(n + 1)]
            for k in range(1, n + 1):
                # 在floyd算法求解的过程中当前其实得到的是1~k-1编号的任意两点之间的最短路径
                for i in range(1, k):
                    for j in range(i + 1, k):
                        # 说明有了路径长度更小的环
                        if dis[i][j] + g[j][k] + g[k][i] < res:
                            # 注意环是按顺序的, 所以需要特别注意下面的代码的编号顺序(只需要按照顺序记录环的编号即可)
                            res = dis[i][j] + g[i][k] + g[k][j]
                            
                            self.count = 0
                            path[self.count] = j
                            self.count += 1
                            path[self.count] = k
                            self.count += 1
                            path[self.count] = i
                            self.count += 1
                            self.getPath(i, j, path, pos)
    
                for i in range(1, n + 1):
                    for j in range(1, n + 1):
                        if dis[i][j] > dis[i][k] + dis[k][j]:
                            dis[i][j] = dis[i][k] + dis[k][j]
                            # pos记录的是当前中间点编号最大的k
                            pos[i][j] = k
            INF = 10 ** 10
            if res == INF: print("No solution.")
            else:
                for i in range(self.count): print(path[i], end=" ")
    
        def process(self):
            n, m = map(int, input().split())
            INF = 10 ** 10
            # 因为后面需要用到下标对应的值相加所以使用邻接矩阵存储会比较方便一点
            g = [[INF] * (n + 1) for i in range(n + 1)]
            for i in range(1, n + 1):
                # 自己到自己的点距离为0
                g[i][i] = 0
            for i in range(m):
                x, y, z = map(int, input().split())
                g[x][y] = g[y][x] = min(g[x][y], z)
            # 拷贝二维列表到dis中
            dis = [x[:] for x in g]
            self.floyd(n, g, dis)
    
    
    if __name__ == "__main__":
        Solution().process()

[https_www.acwing.com_problem_content_description_346]: https://www.acwing.com/problem/content/description/346/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_19_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/1328c3a5a66343459dc381bade5673c5.png