I am getting this result everytime: Using A$*$ to find path from $13$ to $3$

A$*$ Path is $-1$ long in $-1$ edges; found in $1$ pops

$[]$def aStar$($G$,$ s$,$ t$,$ debug$=$False$)$:

$"""$

given a weighted graph G find the shortest path $($by edge weights$)$ from s to t

This time we use an Informed Search

the debug flag can be used to print optional output while testing your program

You will need data structures to track both prior and pathcost$--$ I suggest you use

a dictionary where the key is the node $($vertex$)$ id$,$ and the value is either

the previous node id $($for prior$)$ or the current lowest cost to reach the node

$($for pathcost$).$ Your frontier can take advantage of the provided IndexMinPQ

return: path $-$ a list of the nodes from s to t; should include both s & t

distance $-$ the distance from s to t

popcount $-$ the number of pops from the search frontier

$"""$

def H$($u$,$v$)$:

$"""$ given two vertices u & v$,$ calculate the optimistic length between them.

Each vertex has an attribute, tags, a dictionary of various values associated with

the vertex. The Graph.getTags$($vertex$)$ method provides access to them.

Use the 'lat' and 'lon' values associated with each vertex

to calculate the euclidian distance between the two vertices. $"""$

#TODO Your code goes here

ulat, ulon $=$ G$.$getTags$($u$)[\text{'}$lat$\text{'}],$ G$.$getTags$($u$)[\text{'}$lon$\text{'}]$

vlat, vlon $=$ G$.$getTags$($v$)[\text{'}$lat$\text{'}],$ G$.$getTags$($v$)[\text{'}$lon$\text{'}]$

distance $=$ math.sqrt$(($ulat$-$vlat$)**2+($ulon$-$vlon$)**2)$

return distance # You will need to update this return statement $($returing $0$ makes A$*$ & Dijkstra equivelant, do you see why?$)$

popcount $=0$ # increment this every time you pop a node from the search frontier

print$($f$\text{'}$

Using A$*$ to find path from $\{$s$\}$ to $\{$t$\}\text{'})$

# TODO your code goes here. Using A$*,$ find the path from s$>$t; return that

# path as a python list. Be sure to increment popcount

#

prior $=\{\}$

pathcost $=\{\}$

path $=[]$

distance $=-1$

frontier $=$ IndexMinPQ$($G$.$sizeV$())$

frontier.push$($s$,0+$ H$($s$,$t$))$

while not frontier.isEmpty$()$:

cvertex, ccost $=$ frontier.pop$()$

popcount $+=1$

if cvertex $==$ t:

path $=[$t$]$

while prior$[$cvertex$]$ is not None:

path.append$($prior$[$cvertex$])$

cvertex $=$ prior$[$cvertex$]$

path.reverse$()$

return path, pathcost$[$t$],$ popcount

for edge in G$.$edgesOf$($cvertex$)$:

neighbor $=$ edge.t

ncost $=$ pathcost.get$($cvertex$,$ float$(\text{'}$inf$\text{'}))+$ edge.weight

if ncost $<$ pathcost.get$($neighbor$,$ float$(\text{'}$inf$\text{'}))$:

prior$[$neighbor$]=$ cvertex

pathcost$[$neighbor$]=$ ncost

frontier.push$($neighbor$,$ ncost $+$ H$($neighbor$,$t$))$

return path, distance, popcount