我有一个包含80个城市的图表。我需要找到一条穿过10个城市的最短路线。我必须从已经定义为起始城市的城市开始，用户将从城市列表中输入10个城市名称。我必须在这10个城市旅行，然后我必须回到我开始的城市。我只获得了有关相邻城市之间道路距离的所有信息，除此之外没有任何其他信息。我知道dijkstra等人发现了两个城市之间的最短路径，并且某些启发式算法需要的数据更多。我可以使用dijkstra作为起始城市和其他10个城市之间的最短路径，而不是查找该城市的最小生成树并在其上遍历吗？我可以对这些数据使用任何启发式算法吗？
给出您的10个城市，找出每对之间的最短路径。这仅是Dijkstra算法的100次调用。这为您提供了10个顶点的完整图形。
现在您遇到了一个旅行推销员问题，但是10个城市并不多，而且您已获得起始城市，因此只有9个城市！ （362880）可能性。我只是尝试所有排列并找到最小的排列。
您可以做一些更聪明的事情，但是这种简单的暴力解决方案将快速且易于编码。