text: # -*- coding: utf-8 -*-
  """Shortest paths and path lengths using A* ("A star") algorithm.
  """
  #    Copyright (C) 2004-2011 by 
  #    Aric Hagberg <hagberg@lanl.gov>
  #    Dan Schult <dschult@colgate.edu>
  #    Pieter Swart <swart@lanl.gov>
  #    All rights reserved.
  #    BSD license.
  from heapq import heappush, heappop
  from networkx import NetworkXError
  import networkx as nx
  __author__ ="\n".join(["Salim Fadhley <salimfadhley@gmail.com>",
                         "Matteo Dell'Amico <matteodellamico@gmail.com>"])
  __all__ = ['astar_path','astar_path_length']
  
  def astar_path(G, source, target, heuristic=None, weight='weight'):
      """Return a list of nodes in a shortest path between source and target 
      using the A* ("A-star") algorithm.
  
      There may be more than one shortest path.  This returns only one.
      
      Parameters
      ----------
      G : NetworkX graph
  
      source : node
         Starting node for path
  
      target : node
         Ending node for path 
  
      heuristic : function
         A function to evaluate the estimate of the distance
         from the a node to the target.  The function takes
         two nodes arguments and must return a number.
  
      weight: string, optional (default='weight')
         Edge data key corresponding to the edge weight.
  
      Raises
      ------
      NetworkXNoPath
          If no path exists between source and target.
  
      Examples
      --------
      >>> G=nx.path_graph(5)
      >>> print(nx.astar_path(G,0,4))
      [0, 1, 2, 3, 4]
      >>> G=nx.grid_graph(dim=[3,3])  # nodes are two-tuples (x,y)
      >>> def dist(a, b):
      ...    (x1, y1) = a
      ...    (x2, y2) = b
      ...    return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5
      >>> print(nx.astar_path(G,(0,0),(2,2),dist))
      [(0, 0), (0, 1), (1, 1), (1, 2), (2, 2)]
  
  
      See Also
      --------
      shortest_path, dijkstra_path
  
      """
      if G.is_multigraph():
          raise NetworkXError("astar_path() not implemented for Multi(Di)Graphs")
  
      if heuristic is None:
          # The default heuristic is h=0 - same as Dijkstra's algorithm
          def heuristic(u,v):
              return 0
      # The queue stores priority, node, cost to reach, and parent.
      # Uses Python heapq to keep in priority order.
      # Add each node's hash to the queue to prevent the underlying heap from
      # attempting to compare the nodes themselves. The hash breaks ties in the
      # priority and is guarenteed unique for all nodes in the graph.
      queue = [(0, hash(source), source, 0, None)]
  
      # Maps enqueued nodes to distance of discovered paths and the
      # computed heuristics to target. We avoid computing the heuristics
      # more than once and inserting the node into the queue too many times.
      enqueued = {}
      # Maps explored nodes to parent closest to the source.
      explored = {}
      
      while queue:
          # Pop the smallest item from queue.
          _, __, curnode, dist, parent = heappop(queue)
  
          if curnode == target:
              path = [curnode]
              node = parent
              while node is not None:
                  path.append(node)
                  node = explored[node]
              path.reverse()
              return path
  
          if curnode in explored:
              continue
  
          explored[curnode] = parent
  
          for neighbor, w in G[curnode].items():
              if neighbor in explored:
                  continue
              ncost = dist + w.get(weight,1)
              if neighbor in enqueued:
                  qcost, h = enqueued[neighbor]
                  # if qcost < ncost, a longer path to neighbor remains
                  # enqueued. Removing it would need to filter the whole
                  # queue, it's better just to leave it there and ignore
                  # it when we visit the node a second time.
                  if qcost <= ncost:
                      continue
              else:
                  h = heuristic(neighbor, target)
              enqueued[neighbor] = ncost, h
              heappush(queue, (ncost + h, hash(neighbor), neighbor, 
                               ncost, curnode))
  
      raise nx.NetworkXNoPath("Node %s not reachable from %s"%(source,target))
  
  def astar_path_length(G, source, target, heuristic=None, weight='weight'):
      """Return a list of nodes in a shortest path between source and target 
      using the A* ("A-star") algorithm.
  
      Parameters
      ----------
      G : NetworkX graph
  
      source : node
         Starting node for path
  
      target : node
         Ending node for path 
  
      heuristic : function
         A function to evaluate the estimate of the distance
         from the a node to the target.  The function takes
         two nodes arguments and must return a number.
  
      Raises
      ------
      NetworkXNoPath
          If no path exists between source and target.
  
      See Also
      --------
      astar_path
  
      """
      path=astar_path(G,source,target,heuristic)
      return sum(G[u][v].get(weight,1) for u,v in zip(path[:-1],path[1:]))
      
  