基于Python的Dijkstra算法

Question

这是Dijkstra算法的一部分，我对一些代码有一些疑问，我不明白：

http://geekly-yours.blogspot.co.at/2014/03/dijkstra-algorithm-python-example-source-code-shortest-path.html

谁能告诉我，这些树线是干什么的？在

...
pred=predecessors.get(pred,None)
...

if new_distance < distances.get(neighbor,float('inf')):
...

unvisited[k] = distances.get(k,float('inf')) #what does this .get(k,float('inf')) ??
...

Answer 1

这些都使用get。在

D.get(key,default)

将查看dict D。如果它有键key，它将返回D[key]。如果不是，则返回default。在

^{pr2}$

所以第二行

^{3}$

检查new_distance是否小于当前最佳选项，或者如果没有当前最佳选项，则将计算为True（因为它将小于无穷大）。在

第三条线

unvisited[k] = distances.get(k,float('inf'))

给出unvisited[k]无论当前距离是k，或者如果没有定义距离，则为无穷大。在

回到第一行

pred=predecessors.get(pred,None)

如果定义了predecessors[pred]，则它给出pred = predecessors[pred]。如果不是，则设置pred=None。None是Python中使用的一个标准值，用来表示某些东西没有值。任何不显式返回任何内容的函数都将返回None

Answer 2

pred=predecessors.get(pred,None)相当于

pred=predecessors[pred] if pred in predecessors else None

这和

^{pr2}$

同样，if new_distance < distances.get(neighbor,float('inf')):相当于

^{3}$

并且unvisited[k] = distances.get(k,float('inf'))相当于

unvisited[k] = distances[k] if k in distances else float('inf')

Answer 3

.get是一个dict方法，它根据给定的键获取值。例如

>>> d = {'cat': 5}
>>> d.get('cat')
5
>>> d['cat']
5

第二个参数是找不到键时要使用的默认值。在

^{pr2}$