I'm trying to code the shortest path finder using Dijkstra's algorithm but it doesn't seem to be working. I can't figure out what the problem is. I'm working on Python 3.5 and following this video.
Here is the code:
graph = {
'A': {'B': 10, 'D': 4, 'F': 10},
'B': {'E': 5, 'J': 10, 'I': 17},
'C': {'A': 4, 'D': 10, 'E': 16},
'D': {'F': 12, 'G': 21},
'E': {'G': 4},
'F': {'E': 3},
'G': {'J': 3},
'H': {'G': 3, 'J': 3},
'I': {},
'J': {'I': 8},
}
def dijkstra(graph, start, end):
D = {}
P = {}
for node in graph.keys():
D[node]= -1
P[node]=""
D[start]=0
unseen_nodes=graph.keys()
while len(unseen_nodes) > 0:
shortest=None
node=' '
for temp_node in unseen_nodes:
if shortest==None:
shortest = D[temp_node]
node = temp_node
elif D[temp_node]<shortest:
shortest=D[temp_node]
node=temp_node
unseen_nodes.remove(node)
for child_node, child_value in graph[node].items():
if D[child_node] < D[node] + child_value:
D[child_node] = D[node] + child_value
P[child_node]=node
path = []
node = end
while not (node==start):
if path.count(node)==0:
path.insert(0, node)
node=P[node]
else:
break
path.insert(0, start)
return path
and here is the error message:
AttributeError: 'dict_keys' object has no attribute 'remove'
In Python 3, dict.keys()
returns a dict_keys object (a view of the dictionary) which does not have remove
method; unlike Python 2, where dict.keys()
returns a list object.
>>> graph = {'a': []}
>>> keys = graph.keys()
>>> keys
dict_keys(['a'])
>>> keys.remove('a')
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
AttributeError: 'dict_keys' object has no attribute 'remove'
You can use list(..)
to get a keys list:
>>> keys = list(graph)
>>> keys
['a']
>>> keys.remove('a')
>>> keys
[]
unseen_nodes = graph.keys()
to
unseen_nodes = list(graph)