Please help with only the #yourcodehere and do not change other provided codes. The code must work for test implementation in the picture.

$**$Provided Codes$**$

class Vertex: # This is the outline for a vertex data structure

def $\_\_$init$\_\_($self$,$i$,$j$)$:

self.x $=$i # The x coordinate

self.y $=$j # The y coordinate

self.d $=$float$(\text{'}$inf$\text{'})$# the shortest path estimate

self.processed $=$False

self.idx$\_$in$\_$priority$\_$queue $=-1$

self.pi $=$None

def reset$($self$)$:

self.d $=$float$(\text{'}$inf$\text{'})$

self.processed $=$False

self.idx$\_$in$\_$priority$\_$queue $=-1$

self.pi $=$None

class PriorityQueue:

# Constructor: Implement a empty heap data structure

def $\_\_$init$\_\_($self$)$:

self.q $=[$None$]$# pad it with one element

def insert$($self$,$v$)$:

n $=$len$($self$.$q$)$

self.q$.$append$($v$)$

v$.$idx$\_$in$\_$priority$\_$queue $=$n

self.bubble$\_$up$($n$)$

# self.check$\_$invariant$()$

def swap$($self$,$i$,$j$)$:

tmp $=$self$.$q$[$i$]$

self.q$[$i$]=$self$.$q$[$j$]$

self.q$[$i$].$idx$\_$in$\_$priority$\_$queue $=$i

self.q$[$j$]=$tmp

self.q$[$j$].$idx$\_$in$\_$priority$\_$queue $=$j

def bubble$\_$up$($self$,$j$)$:

assert j $>=1$

assert j $<$len$($self$.$q$)$

if j $==1$:

return

val $=$self$.$q$[$j$].$d

parent$\_$idx $=$j $//2$

parent$\_$val $=$self$.$q$[$parent$\_$idx$].$d

if val $<$parent$\_$val:

self.swap$($j$,$parent$\_$idx$)$

self.bubble$\_$up$($parent$\_$idx$)$

return

def bubble$\_$down$($self$,$j$)$:

n $=$len$($self$.$q$)$

left$\_$child$\_$idx $=2*$j

right$\_$child$\_$idx $=2*$j $+1$

if left$\_$child$\_$idx $>=$n:

return

if right$\_$child$\_$idx $>=$n:

child$\_$idx $=$left$\_$child$\_$idx

child$\_$d $=$self$.$q$[$left$\_$child$\_$idx$].$d

else:

$($child$\_$d$,$child$\_$idx$)=$min $(($self$.$q$[$left$\_$child$\_$idx$].$d$,$left$\_$child$\_$idx$),$

$($self$.$q$[$right$\_$child$\_$idx$].$d$,$right$\_$child$\_$idx$)$

$)$

if self.q$[$j$].$d $>$child$\_$d:

self.swap$($j$,$child$\_$idx$)$

self.bubble$\_$down$($child$\_$idx$)$

return

def get$\_$and$\_$delete$\_$min$($self$)$:

n $=$len$($self$.$q$)$

assert n $>1$

v $=$self$.$q$[1]$

if n $>2$:

self.q$[1]=$self$.$q$[$n$-1]$

self.q$[$n$-1].$idx$\_$in$\_$priority$\_$queue $=1$

del self.q$[$n$-1]$

self.bubble$\_$down$(1)$

#self.check$\_$invariant$()$

return v

# Is the heap empty?

def is$\_$empty$($self$)$:

return len$($self$.$q$)==1$

def update$\_$vertex$\_$weight$($self$,$v$)$:

j $=$v$.$idx$\_$in$\_$priority$\_$queue

n $=$len$($self$.$q$)$

assert j $>=0$and j $<$n

self.bubble$\_$down$($j$)$

self.bubble$\_$up$($j$)$

# self.check$\_$invariant$()$

class DirectedGraphFromImage:

def $\_\_$init$\_\_($self$,$img$)$:

self.img $=$img

self.coords$2$vertex $=\{\}$# construct a dictionary that maps coordinates $[($i$,$j$)]$to corresponding vertices in graph

def get$\_$vertex$\_$from$\_$coords$($self$,$i$,$j$)$:

if $($i$,$j$)$in self.coords$2$vertex: # is pixel $($i$,$j$)$already there?

return self.coords$2$vertex$[($i$,$j$)]$# if yes, just return the vertex corresponding

v $=$Vertex$($i$,$j$)$

self.coords$2$vertex$[($i$,$j$)]=$v

return v

## Given $($x$,$y$)$coordinates of two neighboring pixels, calculate the edge weight.

# We take the squared euclidean distance between the pixel values and add $0\mathrm{.}1$

def getEdgeWeight$($self$,$u$,$v$)$:

img $=$self$.$img

# get edge weight for edge between u$,$v

i$0,$j$0=$u$.$x$,$u$.$y

i$1,$j$1=$v$.$x$,$v$.$y

height, width, $\_=$img$.$shape

# First make sure that the edge is legit

# Edges can only go from each pixel to neighboring pixel

assert i$0>=0$and j$0>=0$and i$0<$width and j$0<$height # pixel position valid?

assert i$1>=0$and j$1>=0$and i$1<$width and j$1<$height # pixel position valid?

assert $-1<=$i$0-$i$1<=1$# edge between node and neighbor?

assert $-1<=$j$0-$j$1<=1$

px$1=$fixPixelValues$($img$[$j$0,$i$0])$

px$2=$fixPixelValues$($img$[$j$1,$i$1])$

return $0\mathrm{.}1+($px$1[0]-$px$2[0])**2+($px$1[1]-$px$2[1])**2+($px$1[2]-$px$2[2])**2$

def get$\_$list$\_$of$\_$neighbors$($self$,$vert$)$:

img $=$self$.$img

i $=$vert$.$x

j $=$vert$.$y

height, width, $\_=$img$.$shape

lst $=[]$

if i $>0$:

# Get the adjacent vertex directly to the WEST

# What is the weight of the edge from pixel $($i$,$j$)$to $($i$-1,$j$)$

v$0=$self$.$get$\_$vertex$\_$from$\_$coords$($i$-1,$j$)$

w$0=$self$.$getEdgeWeight$($vert$,$v$0)$

# Append the adjacent vertex and its weight.

lst$.$append$(($v$0,$w$0))$

if j $>0$:

# Get the adjacent vertex directly to the SOUTH

v$1=$self$.$get$\_$vertex$\_$from$\_$coords$($i$,$j$-1)$

w$1=$self$.$getEdgeWeight$($vert$,$v$1)$

# Append the adjacent vertex and its weight.

lst$.$append$(($v$1,$w$1))$

if i