I have this function here:
def shortestpath(graph,start,end,visited=[],distances={},predecessors={}):
"""Find the shortest path btw start & end nodes in a graph"""
# detect if first time through, set current distance to zero
if not visited: distances[start]=0
# if we've found our end node, find the path to it, and return
if start==end:
path=[]
while end != None:
path.append(end)
end=predecessors.get(end,None)
return distances[start], path[::-1]
# process neighbors as per algorithm, keep track of predecessors
for neighbor in graph[start]:
if neighbor not in visited:
neighbordist = distances.get(neighbor,float("inf"))
tentativedist = distances[start] + graph[start][neighbor]
if tentativedist < neighbordist:
distances[neighbor] = tentativedist
predecessors[neighbor]=start
# neighbors processed, now mark the current node as visited
visited.append(start)
# finds the closest unvisited node to the start
print(graph)
unvisiteds = dict((k, distances.get(k,float("inf"))) for k in graph if k not in visited)
closestnode = min(unvisiteds, key=unvisiteds.get)
# now take the closest node and recurse, making it current
return shortestpath(graph,closestnode,end,visited,distances,predecessors)
And when running the function in just a single line, like the following:
shortestpath(graph, "A", "B")
it gives an expected output of: (4, ['A', 'B']) where the cost is 4 and the two nodes visited are A and B. However, when I try run it through a for loop I get errors.
This is my for loop:
def djikstra(graph):
keys = [i for i in graph.keys()]
keys.pop(len(keys)-1)
for i in keys:
tmp=[]
for j in keys:
print(shortestpath(graph, i, j))
The error is the following:
File "weightedGraph.py", line 89, in shortestpath
closestnode = min(unvisiteds, key=unvisiteds.get)
ValueError: min() arg is an empty sequence
I am aware that the error is that unvisited is empty, but not sure why.
