带有加权无向图的 Python DFS 最短路径搜索

Question

我在解析这个图字典时遇到问题:

routes = {'a': [('b', 5.0), ('c', 8.0)], 'c': [('a', 8.0), ('d', 2.0)], 
'b' [('a', 5.0), ('d', 6.0)], 'e': [('d', 12.0), ('g', 3.0)], 
'd':  [('b', 6.0),('c', 2.0), ('e', 12.0), ('f', 2.0)], 'g': [('e', 3.0),
('f', 7.0)],'f': [('d',2.0), ('g', 7.0)]}

在通过查看 2 个键的 DFS 搜索运行字典时，如何分离出每条边的值？我对字典不是很熟悉。

到目前为止，

def dfs(graph, start, end, path):
    path = path + [start]
    if start == end: 
        paths.append(path)
    for node in graph.childrenOf(start):
        if node not in path:
            dfs(graph, node, end, path)

我需要返回最小的加权路径，所以我需要在程序运行时将值中的数字分开并求和。

Answer 1

您可以使用字典的字典构建图表:

routes = {'a': {'b': 5.0, 'c': 8.0}, 'c': {'a': 8.0, 'd': 2.0}}

然后 routes['a']['b'] 将返回权重，在本例中为 5.0。如果您需要获取一个节点的所有子节点，您可以执行 routes['a'].keys() ，这将返回 ['c', 'b'].