Dijkstra 算法 Python

Dijkstra algorithm with Python

这是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')) ??
...

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

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

第二个参数是找不到密钥时使用的默认值。

>>> d.get('dog', 1)
1

这些都用get

D.get(key,default)

会查看字典D。如果它有键 key 它将 return D[key]。如果不是的话 returns default.

D={'a':0}

D.get('a', 4)
> 0
D.get('b', 4)
>4 

所以第二行

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

检查 new_distance 是否小于当前最佳选项,或者如果没有当前最佳选项,它将计算为 True (因为它将小于无穷大) .

第三行

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

给出 unvisited[k] 当前到 k 的距离,如果没有定义距离则给出无穷大。

回到第一行

pred=predecessors.get(pred,None)

如果定义了predecessors[pred],则给出pred = predecessors[pred]。如果不是,它设置 pred=NoneNone 是 Python 中使用的标准值,表示某些内容没有值。任何没有明确 return 任何内容的函数都会 return None

pred=predecessors.get(pred,None) 等同于

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

相同
if pred in predecessors:
    pred = predecessors[pred]
else:
    pred = None

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

distance = distances[neighbor] if neighbor in distances else float('inf')
if new_distance < distance:

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

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