I was trying shortest path finder using dijkstra algorithm but It seems not working. Can't figure out what the problem is. Here are the code and the error message. (I'm working on Python 3.5. https://www.youtube.com/watch?v=LHCVNtxb4ss)
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
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)