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

Question

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

我有一个针对我的算法主题的项目,它是为dijkstra最短路径algorthim设计一个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

所以关键是顶点,值是链接的vetrices和权重.这是一个图形的例子,但我打算要求用户输入他们自己的图形细节并检查每个节点之间的最短路径[开始 - >结束]然而问题是我甚至不知道如何访问内部字典,所以我可以在内部参数上工作,我尝试了很多这样的方法:

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.我们希望'B'从'A'节点获得连接的权重:

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

使用g['A']获取字典中键的值g.我们可以通过引用'B'密钥直接对此值进行操作.

Answer 2

使用for循环将迭代字典的键，并且通过使用该键，您可以获取与该键关联的值。如果值本身是字典，则可以使用另一个循环。

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

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