基于字典存储的图最短路径求解：递归问题及全路径生成需求

你的问题核心在于递归时没有跟踪已访问的节点，导致程序反复走回头路陷入无限循环，同时也没有正确累加路径的总长度。下面是修复后的完整代码，我会一步步解释改进点：

towns = {'kendal': [['penrith', 28], ['milnthorpe', 8], ['barrow', 35]], 
         'penrith': [['kendal', 28]], 
         'barrow': [['kendal', 35], ['milnthorpe', 31]], 
         'milnthorpe': [['kendal', 8], ['barrow', 31], ['lancaster', 14]], 
         'lancaster': [['milnthorpe', 14]] }

places = ['kendal', 'penrith', 'barrow', 'milnthorpe', 'lancaster']
from_town = ''
while from_town not in places:
    from_town = input('Where are you going from?').lower()
to_town = ''
while to_town not in places:
    to_town = input('Where are you going to?').lower()

routes = []

def get_route(start, finish, visited=None, current_distance=0):
    # 初始化已访问列表（第一次调用时）
    if visited is None:
        visited = []
    # 把当前城镇加入已访问列表，避免回头走
    visited = visited + [start]
    
    # 如果当前就是终点，记录总距离
    if start == finish:
        routes.append(current_distance)
        return
    
    # 遍历当前城镇的所有邻居
    for neighbor, distance in towns[start]:
        # 跳过已经访问过的邻居，防止循环
        if neighbor not in visited:
            # 递归调用：更新已访问列表，累加当前边的距离
            get_route(neighbor, finish, visited, current_distance + distance)

get_route(from_town, to_town)

if routes:
    routes.sort()
    print(f"{routes[0]} miles")
else:
    print("No valid route found between the two towns.")

关键改进说明： #

• 跟踪已访问节点：新增visited参数，每次递归时把当前城镇加入列表，这样就不会重复访问同一个节点，彻底解决无限递归的问题。注意这里用visited + [start]创建新列表，而不是修改原列表，避免递归调用之间互相干扰。
• 累加路径长度：新增current_distance参数，每次递归时把当前边的权重加到总距离里，这样到达终点时就能得到整条路径的总长度。
• 终止条件明确：当start == finish时，直接把总距离加入结果列表并返回，结束当前递归分支。
• 容错处理：最后加了判断，如果routes为空（理论上你的图是连通的，但可以预防极端情况），提示没有可行路径。

原代码的问题复盘： #

1. 没有记录已访问节点，比如从kendal到milnthorpe后，又会递归回到kendal，无限循环下去。
2. 只收集了直接相连的终点边的权重，没有累加间接路径的总长度，比如kendal→milnthorpe→lancaster的总长度应该是8+14=22，但原代码只会单独收集8和14，无法得到正确的总距离。

现在运行这段代码，就能正确生成所有可行路径的总长度，然后找到最短的那个了。

内容的提问来源于stack exchange，提问作者HarryBarry