Answer Happy

Please help
Analysis of Algorithms
Problem 1. Category: Simulating and Coding: Shortest path Dijkstra's algorithm 1. Simulating: Consider the directed graph below. Simulate Dijkstra's algorithm (efficient implementation on the demo slides) 80 as to find, for each nodev, the length of the shortest path from to v. 15 points) 3 3 3 1 3 1 6 Follow our demo slides, Dijkstra's algorithm works by maintaining . for each node, the distance slu] which is an upper approximation of the length of the shortest part from s tov; • a set S which contains modes (the nodes that we get from Del.Min (po) where pe is the priority queue in our lecture 10 slides), such that if v E S then te equals the length of the shortest path from s to w, and if u then [w) is the length of the shortest path from s to v that is in 5 until . it reaches U. an array pres that keep track of the edges on the shortest path, where preulu) is the last edge on a shortest path from tou. You will write down how S, slv evolves (we simplify prev[w) using action for now to simplify the table). Step O: Initially S = [s] = 0, and Vu 3, = Step 1: we will add to the set S (equivalent thinking is is extracted and delete from the priority queue as [s] = 0 is minimum one), and updates as bc have edges from Similarly in step 2, we add noded, and update (cd as there is a new path from stoc now which goes through node now Complete the blank to simulate the algorithm running 1 action step 0 0 S also del 0 XO add mode 1 {s} 0 3 8 DO add node o 2 {s, b} 0 3 6 4 DO DO add node 3 is, b.) a 3 - add node 4 {s, b.) 0 0 3 - add node 5 {s, 0 3 - - add mode 6 {s, b.) 0 3 2. Coding: Dijlestra's algorithm (10 points Give a weighted directed graph, where the nodes are the cities, and the weight of an edge from one city to another one is the cost of the corresponding flight. Implement Dijkstra's algorithm with priority queue to compute the minimum cost of the flights from a city to all other cities If you want to construct the graph from standard input, you can use the starter file, which requires the first line from stdin is two numbers: node number n, and edge number m, and the start from the second line and follows, each line contains two node, v (integer numbers) and also a weight w (positive integer number). The Python starter file will parse the stdin, use a list of list (Arraylist in Javn and vector of vector in C++)to represent the graph, and another list of list (Arraylist in Jawa and vector of vector in C++) to represent the weights of corresponding edges in the graph. Problem 2. Category: Simulating Prim's and Kruskal's algorithm Consider the indirected graph given below where each edge is assigned a cost: (15 points) 9 7 V M 3 기 Refer to the Demo slides for these two algorithms 1. Simulate the steps performed by Prim's algorithm for constructing a minimal-cost spanning tree for this graph. (You can draw just like the slides showed, or if you just write with words, then you must 2 provide enough detail to justify why the algorithm selects certain nodes and not others; in particular, for each step you should indicate which nodes are connected by the current tree) 2. Simulate the stepe performed by Kruskals algorithm for constructing a minimal-cost spanning tree for this graph. (You can draw just like the slides showed, or if you just write with words, then you must provide provide enough detail to justify why the algorithm selects certain edges and not others in particular, for each step you should indicate which nodes are connected by the current tree)