Dijkstra algorithm with Python

Question

Here is a part of a Dijkstra algorithm, i have some question about some code, which I don't understand:

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

Can somebody tell me, what these tree line do?

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

`distances.get(k,float('inf'))` means "get the item in the `distances` dictionary with the key `k`, and if it's not there give me back infinity instead." — Cameron, Jan 07 '15 at 23:36
By the way, it's worth taking a look at networkx if you're going to be doing a lot of network stuff in python. — Joel, Jan 07 '15 at 23:44
[Here](http://stackoverflow.com/a/15534662/298607) is an example of Dijkstra's algorithm in Python — dawg, Jan 07 '15 at 23:46

score 1 · Answer 1 · answered Jan 07 '15 at 23:36

1

.get is a dict method that gets the value based on the given key. For example

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

The second argument is the default value to use if the key is not found.

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

answered Jan 07 '15 at 23:36

Cory Kramer

114,268
16
167
218

ok but why does there is "float('inf')"? Do I get "float('inf')" if somebody calls distance?? – WirJun Jan 07 '15 at 23:37
No, you get `inf` if there is no `k` key in the `dict` variable `distances`. It is a default value, not a neighbor value. – Cory Kramer Jan 07 '15 at 23:38

Joel · Accepted Answer · 2015-01-07T23:42:35.470

1

These all use get.

D.get(key,default)

will look at the dict D. If it has key key it will return D[key]. If not it returns default.

D={'a':0}

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

So the second line

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

checks if the new_distance is less than the current best option, or if there is no a current best option, it will evaluate to True (since it's going to be less than infinity).

The third line

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

gives unvisited[k] whatever the current distance is to k or else infinity if no distance is defined.

Back to the first line

pred=predecessors.get(pred,None)

If predecessors[pred] is defined, it gives pred = predecessors[pred]. If not, it sets pred=None. None is a standard value used in Python to signal that something doesn't have a value. Any function that doesn't return anything explicitly will instead return None

edited Jan 07 '15 at 23:42

answered Jan 07 '15 at 23:36

Joel

22,598
6
69
93

ok, whould it be possible to write int('inf') instead of foat('inf')? – WirJun Jan 07 '15 at 23:52
1

@WirJun, why don't you try it – Padraic Cunningham Jan 07 '15 at 23:54
it's not possible, but i have no explanation why. I expected the distances in "graph" are int() so I can use int. – WirJun Jan 07 '15 at 23:59
Python doesn't think infinity is an integer (and neither do I). But there's no problem comparing an integer to a float. `4<4.5` will return `True` – Joel Jan 08 '15 at 00:01

score 1 · Answer 3 · answered Jul 02 '15 at 19:54

pred=predecessors.get(pred,None) is equivalent to

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

which is the same as

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

Likewise, if new_distance < distances.get(neighbor,float('inf')): is equivalent to

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

and unvisited[k] = distances.get(k,float('inf')) is equivalent to

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

Dijkstra algorithm with Python

3 Answers3