怎么将任意两点间的最短路径改成任意两点间遍历完所有点后的最优路径呢

Question

class Graph:
            def __init__(self,filename):#将地图建成一个邻接表
        
               graph_edges=[]#边的长度
               with open(filename) as fhandle:#读取文件，一行一行的读
                      for line in fhandle:
                          if line=="\n":#读取截止条件，注意必须加否则会报错
                            break
                #将map.txt文件中的数据按空格分离并存储，*_代表这一行后面所有的元素。
                          edge_from,edge_to,cost,*_=line.strip().split(" ")
                          graph_edges.append((edge_from,edge_to,cost))#以元组的形式加入到graph_edges
        #建立节点，set() 函数创建一个无序不重复元素集，
        #可进行关系测试，删除重复数据，还可以计算交集、差集、并集等。
               self.nodes =set()
               for edge in graph_edges:
            #初始化节点
            #update() 方法用于修改当前集合，可以添加新的元素或集合到当前集合中，
            #如果添加的元素在集合中已存在，则该元素只会出现一次，重复的会忽略。
                  self.nodes.update([edge[0],edge[1]])
        #建立邻接表
               self.adjacency_list = {node: set() for node in self.nodes}
               for edge in graph_edges:
           #字典中的键表示图中的节点，而键值则是以字典的形式存在里面包括几组一元组的形式储存的
           #表示可达到节点以及权值
                   self.adjacency_list[edge[0]].add((edge[1],edge[2]))
            def shortest_path(self, start_node, end_node):
                start_node=nameEntry3.get()
                end_node=nameEntry4.get()
               
        #使用Dijkstra算法找到从起始点到终点的最短路径，返回（path,distance）
               
        #创造一个未访问节点的集合初始化为所有节点
                unvisited_nodes = self.nodes.copy()  
        #创建一个字典表示每个点到起始点的距离，每个点先初始化为inf除了点本身初始化为0
        #当我们找到一个更短路径的时候更新这个字典所对应的值，数据结构为 节点：距离
                distance_from_start = {node: (0 if node == start_node else INFINITY) for node in self.nodes}
 
        #初始化前置节点也就是用来寻找路径的方法，结构为节点：节点其中后面的节点是前面
        #的前置节点，由此可以一步步找到路径，如果找到更短路径就更新这个字典
                previous_node = {node: None for node in self.nodes}
                while unvisited_nodes:
            #将当前节点设置为到目前为止在未访问节点这个字典中路径最短的节点
                     current_node = min(
                #从unvisited_nodes中找到键值最小的节点作为当前节点
                          unvisited_nodes, key=lambda node: distance_from_start[node]
                       )
            #从未访问的节点中，移除当前节点
                     unvisited_nodes.remove(current_node)
            #如果当前节点的距离为无穷大，则其余未访问的节点不会连接到开始节点，停止
                     if distance_from_start[current_node] == INFINITY:
                       break
 
            #遍历每个当前节点的邻居，检查一下从起始节点到当前节点再到邻居节点的距离的大小
            #与distance_form_start中的比较看看是否更小，是讲究更新distance中所对应的值
                     for neighbor, distance in self.adjacency_list[current_node]:
                #新的路径的距离
                        new_path = distance_from_start[current_node] + int(distance)
                        if new_path < distance_from_start[neighbor]:
                             distance_from_start[neighbor] = new_path#更新值
                             previous_node[neighbor] = current_node#更新路径，将当前节点作为邻居的前置节点
 
        #为了找到我们所建立的最短路径，使用迭代器遍历每个点的前置节点即可找到路径
        #并且把他存入一个队列中之所以可以保证找得到前置节点，是因为算法完成时候每个点的前置节点都代表着
        #到起始点的最短路径
                path = deque()
                current_node = end_node
                while previous_node[current_node] is not None:
                       path.appendleft(current_node)
                       current_node = previous_node[current_node]
                path.appendleft(start_node)
                return path, distance_from_start[end_node]
       
                   

怎么将任意两点间的最短路径改成任意两点间遍历完所有点后的最优路径呢

Answer 1

如果想要在遍历图中的所有点之后得到最优路径，可以使用一种叫做旅行商问题（Travelling Salesman Problem，TSP）的算法。TSP 问题是指寻找遍历一个给定的城市列表的最短路径的问题。

以下是一个示例实现：

def tsp(self, start, end):
    # 初始化未遍历的点的集合
    unvisited = set(self.nodes)
    # 将起始点加入到已遍历的点的集合中
    visited = {start}
    # 初始化当前点为起始点
    current = start
    #初始化路径和距离为 0
    path = []
    distance = 0
while unvisited:
    # 寻找当前点的最近的未遍历的点
    next_node, next_distance = min([(node, cost) for node, cost in self.adjacency_list[current] if node not in visited], key=lambda x: x[1])
    # 将最近的未遍历的点加入到已遍历的点的集合中
    visited.add(next_node)
    # 从未遍历的点的集合中删除最近的未遍历的点
    unvisited.remove(next_node)
    # 更新当前点为最近的未遍历的点
    current = next_node
    # 更新路径和距离
    path.append(next_node)
    distance += next_distance

# 如果最后一个遍历的点不是终点，添加一条从最后一个遍历的点到终点的边
if current != end:
    # 寻找最后一个遍历的点到终点的最短距离
    next_distance = min([cost for node, cost in self.adjacency_list[current] if node == end])
    # 更新路径和距离
    path.append(end)
    distance += next_distance

return path, distance

可以使用这个方法来解决 TSP 问题：

graph = Graph('map.txt')
path, distance = graph.tsp('A', 'D')
print(path)  # ['A', 'B', 'C', 'D']
print(distance)  # 8

仅供参考，望采纳，谢谢。