利用字典求图上最短路径的距离

Question

我需要找到最短的距离，从一个给定的节点到另一个使用权的边缘。我已将以下图表存储为字典： A visual representation of the graph

我尝试过使用递归方法，但到目前为止似乎失败了。 这是我正在使用的词典：

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):
    others = []

    for x in range(len(towns[start])):

        if towns[start][x][0] == finish:
            routes.append(towns[start][x][1])
        else:
            if towns[start][x][0] not in others:
                others.append(towns[start][x][0])

    for y in range(len(others)):
        get_route(others[y], to_town)

get_route(from_town, to_town)
routes.sort()
print(routes[0], 'miles')

我知道我还没有停止递归的方法，但是我需要的是让程序列出所有可能的路由

Answer 1

你有几个问题；我建议您备份并使用增量编程，这样一次只能处理一个。从几行代码开始；在添加更多之前调试这些。例如，编写一个例程来检查直接路由，否则返回失败。在进行任何递归之前，先让它完全工作

目前，你的主要问题是：

for y in range(len(others)):
    get_route(others[y], to_town)

因为你的递归不涉及你去过的地方的“记忆”，你的递归执行无限的回溯和循环。唯一的解决方法是如果所有活动调用的others都是空的

我建议你查一下Dijkstra's algorithm来获得关于跟踪你已经去过的地方的帮助

还要注意，函数不返回任何内容。您有一个未初始化的局部变量routes；这与主程序中的变量不同