有向加权多重图中全节点覆盖环的算法问询：全环与最短环查找

1. 找出所有经过所有节点至少一次的环 #

这类问题属于哈密顿环的泛化场景（允许重复访问节点，仅要求所有节点至少被覆盖一次），但问题本身是NP难的，仅适合小规模图的处理：

• 回溯+剪枝算法：从任意节点出发，递归遍历所有出边，用二进制掩码记录已访问的节点集合。当掩码标记了所有节点时，检查当前路径是否能回到起点形成环，记录所有符合条件的路径。注意因为是多重图，遍历过程中要处理每个节点的所有出边，而非仅每个邻居一次，同时要对重复的环结构（比如起点不同但节点序列一致的环）做去重处理。
• 状态压缩枚举法：结合动态规划思想记录已访问节点集合和当前位置，枚举所有可能的路径扩展方向，最终收集所有能回到起点且覆盖全节点的环。

2. 找出总边权最小的此类环 #

这是有向旅行商问题（TSP）的变种，适配允许两节点环的场景，具体解法如下：

1. 预处理多重图：对每对节点(u, v)，保留所有u到v边中的最小权值，将多重图转化为普通有向图——选择最小权边不会影响最短环的结果，还能简化后续计算。
2. 分场景处理：
   • 当图中仅含2个节点时：直接计算u到v的最小边权加上v到u的最小边权，即为最短环的总权值。
   • 当图中节点数≥3时：使用状态压缩动态规划求解有向TSP：
     • 状态定义：dp[mask][u]表示访问过mask（二进制掩码，每一位对应一个节点是否被访问）标记的所有节点，且最终停在节点u的最小路径权值。
     • 状态转移：对每个状态(mask, u)，遍历所有未被访问的节点v，更新dp[mask | (1<<v)][v] = min(dp[mask | (1<<v)][v], dp[mask][u] + weight(u, v))。
     • 最终结果：遍历所有节点u，取dp[full_mask][u] + weight(u, start)的最小值（full_mask是所有节点都被标记的掩码，start为初始起点，环可从任意节点出发，最终回到起点）。

内容的提问来源于stack exchange，提问作者Alexander Jafari