Python的DFS最短路徑與加權搜索，無向圖

我無法通過這個圖表字典解析：Python的DFS最短路徑與加權搜索，無向圖

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)]}

如何分離出每條邊的價值通過DFS搜索運行字典一邊尋找在2鍵？我對dict不是很熟悉。

到目前爲止，我有，

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)

我需要回到最小加權路徑，所以我需要在分離出來，在程序運行時總結出的值的數字。

來源

2015-02-06 N.B.48

你想要什麼字典？鍵，值或部分值（哪些部分）？ – nbro 2015-02-06 21:12:57

鍵是冒號左邊的東西，右邊的東西是，你猜對了，我需要返回最小的加權路徑的值 – nbro 2015-02-06 21:17:18

，所以我需要在程序運行時將數值分離出來並相加。 – 2015-02-06 21:18:57

可以使用類型的字典字典構建圖：

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

來源

2015-02-06 21:17:36

routes是你的圖形，在鄰接表格式。每個鍵都是一個節點，該值是一個(other_node, edge_weight)元組列表。所以你要找的是「graph.childrenOf」應該如何工作。

假設start, end是簡單的字符串節點名稱（如'a'），您可以在字典中查找它們;例如graph[a]會給你[('b', 5.0), ('c', 8.0)]。你可以直接在節點和權重上使用python的漂亮的內置元組進行迭代，如下所示：

# replace your for loop with this: 
for node, weight in graph[start]:

來源

2015-02-06 21:20:01 tzaman

Python的DFS最短路徑與加權搜索，無向圖

回答

相關問題