dijkstra icon indicating copy to clipboard operation
dijkstra copied to clipboard

REPORT BUG: running isolated graph will bring in KeyError

Open Serbipunk opened this issue 7 years ago • 0 comments

$ 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

Serbipunk avatar Mar 04 '18 23:03 Serbipunk