Myi*_*Eye 7 algorithm graph path shortest-path
我正在寻找一种对我来说非常典型的算法,但似乎常见的解决方案都有点不同.
在无向图中,我想要访问每个节点的最短路径.可以重新访问节点,我不必返回到起始节点.
该旅行商问题似乎增加每个节点只能使用一次,并且路径必须返回到它开始访问的限制.
最小生成树可能是解决方案的一部分,但此类算法仅提供树,而不是最小路径.另外,因为它们是树,因此没有循环,它们强制回溯,循环可能更有效.
小智 5
您可以通过转换图形将其简化为正常的旅行商问题。
首先，计算每对节点的最小距离。您可以使用 Floyd-Warshall 算法来实现这一点。获得后，只需构建完整的图，其中节点u和v之间的边是从u到v的最小成本。
然后，您可以应用普通的 TSP 算法，因为您不必再重新访问节点，这已经隐藏在边的成本中。