带权有向图中仅经指定节点的最短环求解及可行性疑问

关于删除非S节点的可行性 #

• 完全可以删除V-S中的节点及其关联边，在仅包含S节点的子图上求解最短环。
• 因为题目明确要求环仅经过S中全部节点、不涉及其他节点，V-S内的节点本就不允许出现在路径中。删除这些节点后，剩余子图的边都是原图中两端均属于S的边，此时在该子图上寻找从w出发、遍历所有S节点并返回w的最短环，完全匹配需求。

关于目标链接问题的相关性 #

• 该链接的问题与当前需求不相关。
• 链接中的问题是寻找至少经过X个节点的最短回路，且回路可经过其他非目标节点；而你的需求是必须仅遍历指定集合S的全部节点，路径中不能包含任何V-S的节点，二者的约束条件、目标范围完全不同。

内容的提问来源于stack exchange，提问作者AmirHosein Adavoudi