Referencing dictionary in a for loop

[johnjoepaddyfrancie]

Hey!

I'm trying to implement a programme to calculate distances between security and each individual gate in an airport. I'm using Dijkstra's Algorithm to calculate the shortest path to each gate. The code below is taken directly from Gilles Bertrand:  Dijkstra algorithm: How to implement it with Python? (I can't post the link on my first post)

I'm trying to implement a 'for loop' to calculate the distance of each, individual point from a single starting point. The function works for each point when manually input, but the for loop seems to only capture two or three keys in the dictionary before failing with the error:

ValueError: min() arg is an empty sequence

The keys that are captured are out of sequence and are no different from the others. I'm relatively new to Python so appreciate any help you guys can offer!

Thanks very much

def dijkstra(graph,src,dest,visited=[],distances={},predecessors={}):
   """ calculates a shortest path tree routed in src
   """    
   # a few sanity checks
   if src not in graph:
       raise TypeError('The root of the shortest path tree cannot be found')
   if dest not in graph:
       raise TypeError('The target of the shortest path cannot be found')    
   # ending condition
   if src == dest:
       # We build the shortest path and display it
       path=[]
       pred=dest
       while pred != None:
           path.append(pred)
           pred=predecessors.get(pred,None)
       print('shortest path: '+str(path)+" cost="+str(distances[dest])) 
   else :     
       # if it is the initial  run, initializes the cost
       if not visited: 
           distances[src]=0
       # visit the neighbors
       for neighbor in graph[src] :
           if neighbor not in visited:
               new_distance = distances[src] + graph[src][neighbor]
               if new_distance < distances.get(neighbor,float('inf')):
                   distances[neighbor] = new_distance
                   predecessors[neighbor] = src
       # mark as visited
       visited.append(src)
       # now that all neighbors have been visited: recurse                         
       # select the non visited node with lowest distance 'x'
       # run Dijskstra with src='x'
       unvisited={}
       for k in graph:
           if k not in visited:
               unvisited[k] = distances.get(k,float('inf'))        
       x=min(unvisited, key=unvisited.get)
       dijkstra(graph,x,dest,visited,distances,predecessors)
       


if __name__ == "__main__":
   #import sys;sys.argv = ['', 'Test.testName']
   #unittest.main()
   graph = {'s': {'a': 2, 'b': 1},
           'a': {'s': 3, 'b': 4, 'c':8},
           'b': {'s': 4, 'a': 2, 'd': 2},
           'c': {'a': 2, 'd': 7, 't': 4},
           'd': {'b': 1, 'c': 11, 't': 5},
           't': {'c': 3, 'd': 5}}

## This is the only part I have added to this code
for key in graph.iterkeys():
   print(key)
   dijkstra(graph,'s', key)

[ichabod801]

I'm thinking your defaults are the problem. They are retaining information between calls. So when I ran it, the first run of the final loop was for 'a'. At the end of that visited was ['s', 'b']. The second run of the final loop was for 'c'. At the start of that visited was ['s', 'b'], retained from the first run. It should be empty. Using mutable defaults is a problem, because the default is stored with the function. If the mutable default is changed during execution, those changes are retained in the function's definition.

You want the default of visited to be None. Then add this at the start of the function:

if visited is None:
    visited = []

That way the list isn't stored with the function, but rather created new each time the recursive cycle is started. Then do the same for the other defaults.

[johnjoepaddyfrancie]

Thank you so much for your reply! It really helped me figure out how to solve my problem. I found that if I simply include the extra variables while calling the function in my 'for loop', it reset them on each run.

for key in graph:
   print(key)
   dijkstra(graph, 's', key, visited=[], distances = {}, predecessors = {})

Simple solution in the end; just needed some help seeing what was going wrong. Thanks very much!