dijkstra
dijkstra copied to clipboard
REPORT BUG: running isolated graph will bring in KeyError
$ python dijkstra.py
graph = {'a': {'b': 14, 'c': 9, 'd': 7},
'b': {'a': 14, 'c': 2, 'e': 9},
'c': {'a': 9, 'b': 2, 'd': 10, 'f': 11},
'd': {'a': 7, 'c': 10, 'f': 15},
'e': {'b': 9, 'f': 6},
'f': {'c': 11, 'd': 15, 'e': 6},
'g': {'h': 3}, # -- + isolated graph
'h': {}} # -- +
dist, pred = dijkstra(graph, start='a')
and you will get:
Traceback (most recent call last):
File "dijkstra.py", line 141, in <module>
dist, pred = dijkstra(graph, start='a')
File "dijkstra.py", line 42, in dijkstra
(v, d) = Q.popitem() # node w/ min dist d on frontier
File "/home/magnus/git/dijkstra/pqdict.py", line 451, in popitem
raise KeyError('PQDict is empty')
KeyError: 'PQDict is empty