امن 1 1. (5 points) Find a minimum spanning tree for the following graph. Show the Adjacency List Representation, and Ad

[answerhappygod]

1 (49.63 KiB) Viewed 33 times

امن 1 1. (5 points) Find a minimum spanning tree for the following graph. Show the Adjacency List Representation, and Adjacency Matrix Representation. 2. (3 points) Use the same graph in question number 1 to solve the single source shortest path problem using Dijkstra's algorithm, starting from the node 0 Write the details of your answer 3. (4 points) Consider the knapsack problem with n objects whose profits and weights are pi= {10, 15, 25.12) and w{1.2.3.2), respectively. The capacity constraint is W-5.solve this problem using greedy algorithm, try to find the optimal solution. 4. (3 points) Consider a weighted undirected graph G (V. E) where the weight of each edge =1. Write an algoritim that takes O(IVI + El) time to solve the single source shortest path problem. 5. (3 points) Consider the below graph, use Bellman Ford Algorithm - Single Source Shortest Path Dynamic Programming to finds the shortest path from vertex Sto every other vertex. How many maximum iterations? 6. (3 points) What is the maximum flow from stot far below flow network? 7. (4 points) Let A ct 1) be the weight of a shortest path from vertex i to vertex for which all intermediate vertices are in the set (1.2...). When k = 0, a path from vertex i to vertex with no intermediate vertex numbered higher than o has no intermediate vertices at all, hence Afi. 1) for i, EV. We want to compute Al D.forije V. Use the following recurrence relation to solve All Pairs Shortest Paths in dynamic programming strategy (Floyd-Warshall algorithm); A I. = min (A-161, 1),A1(1,k) + A-1(1.0). How many matrices?