Skip to main content
 首页 » 编程设计

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

2025年05月04日8kerrycode

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

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) 

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

请您参考如下方法:

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

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'].