python - 如何在Python中的仅节点图中找到输入节点列表的最短路径

Question

我对图表这个话题很陌生，所以也许这是一个已知问题，我只是没有找到合适的名称。所以来解释一下。想象一下，我们有一个包含n 个节点的图 - 存储为邻接表。这是一个无向加权图，位于笛卡尔平面上（因此您可以获得每个节点之间的距离）。但是你只有顶点，没有边，就像这张图片：

现在我输入一个节点列表（随机排序），例如[n2,n7,n1]，算法应该找到如何以最小距离连接这些节点的路径，然后返回有序数组 - 例如[n1, n2, n7]

对我来说，这似乎与寻路算法不同，因为您正在输入节点列表，知道如何解决这个问题吗？谢谢！

标签： pythonalgorithmgraphpath

Answer 1

这看起来像旅行商问题。你可以找到很多关于它的文献，但你可以从维基百科页面开始。

为了适应您的问题，您可以创建一个包含所有节点的图，并添加一个与所有其他节点具有相等距离的任意节点，这将作为您的旅行推销员的起点。

旅行商问题的求解技术取决于问题的大小、您希望与最优解的接近程度、您希望算法的速度等。