Step $2$: Implement Dijkstra$$s algorithm in PathFindingService $($Fig $5).$ Use the algorithm to

implement the findPath$($Tile startNode$)$ method. The method uses Dijkstra$$s algorithm

on the Graph stored in the field g to find a minimum weight path to the destination from the

input Tile. Note that the result of running Dijkstra$$s algorithm is that each node in the graph will

contain the information needed to find the minimun weight path from the source to this node. So$,$

after running the algorithm you will need to use the infomation stored in the predecessor field

to backtrack and find the list of Tiles that make up the path to be traversed from the start node to

the destination.

$11$

DIJKSTRA$($V$,$ E$,$w$,$s$)$:

INIT$-$SINGLE$-$SOURCE$($V$,$s$)$

S $$ Q $$ V

while Q do

u $$ REMOVE$-$MIN$($Q$)$

S $$ S $\{$u$\}$

for each vertex v Adj$[$u$]$ do

RELAX$($u$,$v$,$w$)$

Figure $5$: Pseudo$-$code for Dijkstra$$s algorithm

INIT$-$SINGLE$-$SOURCE$($V$,$s$)$

for each v V do

d$[$v$]$

$[$v$]$ null

d$[$s$]0$

Figure $6$: Pseudo$-$code for the initialization

RELAX$($u$,$v$,$w$)$

if d$[$v$]>$ d$[$u$]+$w$($u$,$v$)$ then

d$[$v$]$ d$[$u$]+$w$($u$,$v$)$

$[$v$]$ u

Figure $7$: Pseudo$-$code for the relaxing operation