ANALYSIS OF ALGORITHM
- Please Do Asap Analysis Of Algorithm 1 (152.7 KiB) Viewed 43 times
PLEASE DO ASAP ANALYSIS OF ALGORITHM
-
answerhappygod
- Site Admin
- Posts: 899604
- Joined: Mon Aug 02, 2021 8:13 am
PLEASE DO ASAP ANALYSIS OF ALGORITHM
PLEASE DO ASAP
ANALYSIS OF ALGORITHM
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) so as to find, for each node u, the length of the shortest path from s to v. [5 points) 8 3 32 3 3 1 2 1 3 b d f 1 6 Follow our demo slides, Dijkstra's algorithm works by maintaining • for each node v, the distance which is an upper approximation of the length of the shortest part from s to v; • a set S which contains nodes (the nodes that we get from Del Min(pg) where pq is the priority queue in our lecture 10 slides), such that if v E S then equals the length of the shortest path from s to v, and if v & S then is the length of the shortest path from s to v that is in S until it reaches v. • an array prev that keep track of the edges on the shortest path, where prev is the last edge on a shortest path from s to v. You will write down how S, T evolves (we simplify prev using action for now to simplify the table). Step 0: Initially S = 0,7[s] = 0, and Vu 5, = . Step 1: we will add s to the set S (equivalent thinking is s is extracted and delete from the priority queue as [s] =0 is minimum one), and update (b), (c) as b,c have edges from s. Similarly in step 2, we add node b, and update (c), (d) as there is a new path from s to c now which goes through node b now. Complete the blank to simulate the algorithm running. 1 action step 0 0 S {} 1 [s] [ ctd] [e] T[f] 0 00 00 00 add nodes 1 1 {s} 0 3 8 00 00 00 add node b 2 {s, b} 0 3 6 4 00 00 add node 3 {s, b, -} 0 3 add node 4 {s, b, -} 0 3 add node 5 {s, b, -} 0 3 add node 6 {s, b, } 0 3 2. Coding: Dijkstra'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 s 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 u, 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 Java and vector of vector in C++) to represent the graph, and another list of list (Arraylist in Java and vector of vector in C++) to represent the weights of corresponding edges in the graph.
ANALYSIS OF ALGORITHM
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) so as to find, for each node u, the length of the shortest path from s to v. [5 points) 8 3 32 3 3 1 2 1 3 b d f 1 6 Follow our demo slides, Dijkstra's algorithm works by maintaining • for each node v, the distance which is an upper approximation of the length of the shortest part from s to v; • a set S which contains nodes (the nodes that we get from Del Min(pg) where pq is the priority queue in our lecture 10 slides), such that if v E S then equals the length of the shortest path from s to v, and if v & S then is the length of the shortest path from s to v that is in S until it reaches v. • an array prev that keep track of the edges on the shortest path, where prev is the last edge on a shortest path from s to v. You will write down how S, T evolves (we simplify prev using action for now to simplify the table). Step 0: Initially S = 0,7[s] = 0, and Vu 5, = . Step 1: we will add s to the set S (equivalent thinking is s is extracted and delete from the priority queue as [s] =0 is minimum one), and update (b), (c) as b,c have edges from s. Similarly in step 2, we add node b, and update (c), (d) as there is a new path from s to c now which goes through node b now. Complete the blank to simulate the algorithm running. 1 action step 0 0 S {} 1 [s] [ ctd] [e] T[f] 0 00 00 00 add nodes 1 1 {s} 0 3 8 00 00 00 add node b 2 {s, b} 0 3 6 4 00 00 add node 3 {s, b, -} 0 3 add node 4 {s, b, -} 0 3 add node 5 {s, b, -} 0 3 add node 6 {s, b, } 0 3 2. Coding: Dijkstra'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 s 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 u, 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 Java and vector of vector in C++) to represent the graph, and another list of list (Arraylist in Java and vector of vector in C++) to represent the weights of corresponding edges in the graph.
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!