找到最短距离，同时访问每个节点一次

Question

出于练习的原因，我正在研究 Advent of Code 2015，但我被困在了第 9 天。目标是找到最短距离，同时访问图中的每个位置一次。每个点都直接相互连接，并且终点必须与起点不同。我已经制定了解决方案，但最终值不正确，并且我没有看到根本问题。首先，我创建一个包含位置和距离的图形对象。然后，我将位置的每个排列收集到一个列表中，然后查找并总结每个排列的距离。最后，我打印出最小距离值，这就是练习的解决方案。代码：from collections import defaultdictfrom itertools import permutationswith open("input.txt") as file:    input_ = file.read().split("\n")[:-1]class Graph():    def __init__(self):        self.edges = defaultdict(list)        self.weights = {}        def add_edge(self, from_node, to_node, weight):        self.edges[from_node].append(to_node)        self.edges[to_node].append(from_node)        self.weights[(from_node, to_node)] = weight        self.weights[(to_node, from_node)] = weightgraph = Graph()edges = [(i.split()[0], i.split()[2], int(i.split()[-1])) for i in input_]for edge in edges:    graph.add_edge(*edge)    loc_set = set([i[0] for i in edges])routes = list(permutations(loc_set, len(loc_set)))dists = []for i in routes:    print(i)    dist_temp = []    for k in range(len(i))[1:]:        dist_temp.append(graph.weights[(i[k-1], i[k])])    dists.append(sum(dist_temp))    print(dist_temp)    print(sum(dist_temp))    print(min(dists))获得无效值后，我手动检查了一些排列及其相应的距离，因此在代码中打印出来。输入（将其复制并粘贴到记事本并将其另存为 input.txt 对于我的代码应该可以正常工作）：Faerun to Tristram = 65Faerun to Tambi = 129Faerun to Norrath = 144Faerun to Snowdin = 71Faerun to Straylight = 137Faerun to AlphaCentauri = 3Faerun to Arbre = 149Tristram to Tambi = 63Tristram to Norrath = 4Tristram to Snowdin = 105Tristram to Straylight = 125Tristram to AlphaCentauri = 55Tristram to Arbre = 14Tambi to Norrath = 68Tambi to Snowdin = 52Tambi to Straylight = 65Tambi to AlphaCentauri = 22Tambi to Arbre = 143我非常确定，这个问题有更完善的解决方案，并且我愿意接受建议，因为我只是一个业余爱好者。然而，如果我们能够解决我的方法的缺点并使其正常工作，我会非常高兴。

Answer 1

我发现了错误！事实证明，该方法是有效的，我只是在定义位置集时粗心了。

我假设每个位置在指令字符串的开头至少出现一次。然而，一个位置（“Arbre”）仅出现在指令末尾。因此，图表不完整，因此输出错误。

作为快速修复，我按以下方式修改了代码：

loc_set = set([i[0] for i in edges])

到

loc_set = list(set([i[0] for i in edges]))
loc_set.append("Arbre")

另外，事实证明，顺便说一句，该方法对于本次练习很有用，因为第二部分要求最长距离，可以通过最后的一行附加代码找到最长距离：

print(max(dists))