正权有向图仅经特定节点最短环算法：基于Dijkstra还是TSP？

这个问题的解决方案以旅行商问题（TSP）为核心框架，同时用Dijkstra算法作为关键子步骤，具体拆解如下：

• 从问题本质看，需求是找到仅包含指定节点的最短环，等同于要遍历所有指定节点并返回起点的最短闭合路径，这完全属于TSP的变种场景（标准TSP是遍历所有节点，这里限定为遍历指定节点子集）。
• 实现过程中，首先需要对每个指定节点，用Dijkstra算法计算它到其他所有指定节点的最短路径（因为图中权重为正，Dijkstra是该场景下的最优选择），生成一个指定节点间的最短路径权重矩阵。
• 拿到这个矩阵后，就可以用TSP的经典解法（比如动态规划解法）来求解“遍历所有指定节点并返回起点”的最短路径，这个路径对应的就是原问题要求的最短环。

总结：整体问题属于TSP范畴，Dijkstra是预处理节点间最短路径的必备工具。

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