Python Program only.

1. (75) [Dijkstra'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 s 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 binary heap priority queue to keep track of the nodes yet to be explored at each iteration of the program execution. - 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 s to the node included. Example: "Node v included in S with the shortest path length x on the path svIv2v. . 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. S{},(s)0. while (Q is not empty) v= ExtractMin(Q). Add v to S. for each edge e=(v,w) such that w/S{ if ((v)+Ie