$1.[$Dijkstra$\text{'}$s single$-$source shortest paths: programming$]$ Write a program code to implement the Dijkstra's single$-$source shortest paths finding algorithm discussed in class and show the trace of the algorithm against the directed graph shown below. Your code should follow the instructions stated below.

$-$ Use the node $\backslash ($ s $\backslash )$ as the source node.

$-$ Use any data structure of your choice $($e$.$g$.,$ adjacency list, adjacency matrix, edge list$)$ to represent the graph.

$-$ Use a minimum$-$oriented priority queue of nodes as studied in class. Feel free to use Java PriorityQueue class, or implement one of your own.

$-$ Use the pseudocode discussed in class $($shown below$)$ as the base of your program code; your code should maintain the same code structure as the base code and explicitly include the functions ExtractMin and ChangeKey that implement the two priority queue operations.

$-$ The base code does not keep track of the predecessors of each node. Extend the base code to keep track of them.

$-$ When executed, your program should display the following information on the console:

i$.$ The data structure you used to represent the graph. Example: "Graphs is represented using an adjacency list."

ii$.$ Each time a new node is included into the cut S$,$ the shortest path $($i$.$e$.,$ sequence of node numbers$)$ from $\backslash ($ s $\backslash )$ to the node included. Example: "Node $\backslash ($ v $\backslash )$ included in $\backslash ($ S $\backslash )$ with the shortest path length $\backslash ($ x $\backslash )$ on the path $\backslash ($ s$-$v$\_\{1\}-$v$\_\{2\}-\backslash$ldots$-$v $\backslash )."$

Base code $($keep the program code structure as shown below$)$:

$```$

Dijkstra$($G$,$ s$)\{$

Initialize Q of V with $\}\backslash$pi$($v$)\backslash$leftarrow$\backslash$infty$\backslash$mathrm$\{$ for each node V in V$.$

S$\}\backslash$leftarrow$\{\},\backslash$pi$($s$)\backslash$leftarrow$0$

while $(\}$Q$\backslash$mathrm$\{$ is not empty$)$

v$=$ ExtractMin$($Q$)$

Add v to S$.$

for each edge e$=($v$,$w$)$ such that w$\}$

otinS

if $(\backslash$pi$($v$)+\backslash$mp@subsup$\{$I$\}\{$e$\}\{\}<mi>\backslash </mi>$pi$($w$))\{$

$\backslash$pi $($ w $)=\backslash$pi $($ v $)+$ l $\_\{$ e $\}.$

ChangeKey$($Q$,$ w$,\backslash$pi$($w$)).$

$\}$

$\}$

endwhile

$\}$

$```$

Graph for algorithm tracing: