algorithm - 在访问某些顶点时找到加权图中的最短路径

我试图在无向加权图中找到从 A 到 Z 的最短路径。但是，生成的路径也应该通过一组无序的顶点（比如说 B、C 和 D）。
我还没有找到这个确切问题的任何答案，但我遇到了类似的问题，这些问题将问题定义为 NP-Hard （所以据我所知，对于每个图来说并不是真正可解决的）。

那么是否还有一种算法可以至少尝试找到一条访问所有这些顶点并中断的路径，以防在用尽合理数量的选项后找不到路径？

如果没有，在我的情况下，另一种方法是对这些必须访问的顶点进行排序。有没有比仅仅拆分路径并计算每个段（A->B、B->C 等）的最佳路径更好的方法来寻找路径？

标签： algorithmgraphpath-finding

给定一组顶点S和一个原点v，您可以使用深度优先搜索将S中的顶点从距离v的最近到最远排序，即制作距离表。

实际上，创建该表会为您提供一个仅由O(nm)中的顶点S组成的新图，其中n是图的大小，m是集合S的大小。

您现在正在寻找通过这个新图的所有顶点的最短路径。因此，您的问题等同于该较小图上的旅行推销员问题。

现在由您来选择一个已知的启发式算法以应用于较小的图表。