使用字典的最短路径算法 [Python]

Question

这是我的第一个问题，实际上是我第一次尝试这个问题，但我阅读了问题规则，希望我的问题符合所有规则。

我有一个算法主题的项目，它是为dijkstra最短路径算法设计一个gui。我选择使用 python 是因为它是我想掌握的语言。我其实已经尝试了一个多星期，一路上都遇到了麻烦。但无论如何，这很有趣 :)！

我选择用这种方式将我的有向图表示为字典：

 g= {'A': {"B": 20, 'D': 80, 'G' :90}, # A can direct to B, D and G
'B': {'F' : 10},
'F':{'C':10,'D':40},
'C':{'D':10,'H':20,'F':50},
'D':{'G':20},
'G':{'A':20},
'E':{'G':30,'B':50},
'H':None}  # H is not directed to anything, but can accessed through C

所以键是顶点，值是链接的顶点和权重。这是一个图表示例，但我打算让用户输入他们自己的图表详细信息并检查每两个节点之间的最短路径 [开始 -> 结束] 然而问题是我什至不知道如何访问内部字典，这样我就可以处理内部参数，我尝试了很多方法，比如这两个：

for i in g:
    counter = 0
    print g[i[counter]]     # One
    print g.get(i[counter]) # Two

但是两者都给我相同的输出：（请注意，我无法真正访问和使用内部参数）

{"B": 20, 'D': 80, 'G' :90}
{'F' : 10}
{'C':10,'D':40}
{'D':10,'H':20,'F':50}
{'G':20}
{'A':20}
{'G':30,'B':50}
None

所以我的问题是，能否请您帮助我了解如何访问内部词典，以便我可以开始研究算法本身。非常感谢，感谢阅读。

Answer 1

这其实并不难，一旦你看到它应该完全有意义。让我们来看看你的 g。我们想从 'A' 节点获取 'B' 连接的权重：

>>> d = g['A']
>>> d
{"B": 20, 'D': 80, 'G' :90}
>>> d['B']
20
>>> g['A']['B']
20

使用g['A'] 获取字典g 中键的值。我们可以通过引用 'B' 键直接作用于这个值。

Answer 2

我想这些会给你一些想法：

for dict in g:
     print dict.get("B","")

for dict in g:
     print dict.keys() #or dict.values()

for dict in g:
     print dict["B"]

Answer 3

使用 for 循环将遍历字典的键，通过使用键，您可以获取与键关联的值。如果值本身是一个字典，你可以使用另一个循环。

for fromNode in g:
    neighbors = g[fromNode]
    for toNode in neighbors:
        distance = neighbors[toNode]
        print("%s -> %s (%d)" % (fromNode, toNode, distance))

请注意，要使其正常工作，当没有邻居时，您应该使用空字典 {} 而不是 None。

使用字典的最短路径算法 [Python]

Shortest path algorithm using dictionaries [Python]

python

algorithm

dictionary

dijkstra