Please using Java to solve it.

1. (25: optional after two required) [Single-source shortest paths: programmingl Implement the Dijkstra's single-source shortest paths finding algorithm and show the trace of the algorithm against the directed graph below. The node s is the single source. You can use any data structure (e.g., adjacency list, adjacency matrix, edge list) to represent the graph. The program should display on console (i) the data structure you used to represent the graph (e.g., "l've used an adjacency list!") and (ii) the shortest path (i.e., sequence of node numbers) from s to the node included in the cut S each time a new node is included (e.g., "Node v included in S with the shortest path length x on the path s -V V2 Use a minimum binary heap priority queue to keep the nodes to be explored. Use the priority queue based implementation of the algorithm discussed in class (shown below) as the base of your program code; your code should maintain the same code structure and include ExtractMin and ChangeKey as two priority queue operations. Note that you should extend the algorithm to keep track of the predecessor of each node. - -V. Base code (keep the program code structure as shown below): Dijkstra(G, s) [ Initialize Q of V with (v) for each node v in V. while (Q is not empty) v ExtractMin(Q) Add v to S. for each edge e (v, w) such that w S{ ChangeKey(Q, w, T(w)) endwhile raph for algorithm tracin 23 18 30 4 19 15 20 16