def dijkstra_shortest_path(graph, id1, id2, heuristic=None, directed=False):
 def flatten(list):
  while (len(list) > 0):
   (yield list[0])
   list = list[1]
 G = adjacency(graph, directed=directed, heuristic=heuristic)
 q = [(0, id1, ())]
 visited = set()
 while True:
  (cost1, n1, path) = heappop(q)
  if (n1 not in visited):
   visited.add(n1)
  if (n1 == id2):
   return (list(flatten(path))[::(-1)] + [n1])
  path = (n1, path)
  for (n2, cost2) in G[n1].items():
   if (n2 not in visited):
    heappush(q, ((cost1 + cost2), n2, path))

def dijkstra_shortest_path ( graph , id1 , id2 , heuristic = None , directed = False ) : def flatten ( list ) : while ( len ( list ) > 0 ) : ( yield list [ 0 ] ) list = list [ 1 ] G = adjacency ( graph , directed = directed , heuristic = heuristic ) q = [ ( 0 , id1 , ( ) ) ] visited = set ( ) while True : ( cost1 , n1 , path ) = heappop ( q ) if ( n1 not in visited ) : visited . add ( n1 ) if ( n1 == id2 ) : return ( list ( flatten ( path ) ) [ : : ( - 1 ) ] + [ n1 ] ) path = ( n1 , path ) for ( n2 , cost2 ) in G [ n1 ] . items ( ) : if ( n2 not in visited ) : heappush ( q , ( ( cost1 + cost2 ) , n2 , path ) )
dijkstra algorithm for finding the shortest path between two nodes .