4. You are given a directed graph in which each vertex u Є V has an associated price pu, which is a positive integer. Define the array cost as follows: for each u Є V, cost [u] = price of the cheapest vertex reachable from u (including u itself). For instance, in the graph below (with prices shown for each vertex), the cost values of the vertices A, B, C, D, E, F are 2, 1, 4, 1, 4, 5, respectively. 2 6 4 A C E B D F 5 3 1 Your goal is to design an efficient algorithm that fills in the entire cost array (i.e., for all vertices). Give a linear-time algorithm that works for directed acyclic graphs. 5. (a) Simulate Dijkstra's algorithm on the following graph with vertices numbered 1 to 6. The edges are: 1: (6,2), (4,7) 2: (1, 3), (3,4) 3: (5,6) 4: (2,2), (3,5), (1,5), (5,1) 5: (4,4), (6,3) 6: (4,3) Here (3, 4) in vertex 2's adjacency list means that vertex 2 has a directed edge to vertex 3 with a weight of 4. Assuming that the source vertex in Dijkstra's algorithm is vertex 2, show the values of distance and predecessor for each vertex. Also draw the shortest paths tree (the tree of shortest paths to the vertices from the source vertex). (b) Find a minimum spanning tree for the graph shown below using Prim's algorithm and compute the weight of the resulting minimum spanning tree. Does this graph have a unique minimum spanning tree? 3 A B 6 5 3 4 2 1 2 C Ꭰ E F 4 5 5 6 4 5. 5 3 6 G H 3 I J
4. You are given a directed graph in which each vertex u Є V has an associated price pu, which is a positive integer. Define the array cost as follows: for each u Є V, cost [u] = price of the cheapest vertex reachable from u (including u itself). For instance, in the graph below (with prices shown for each vertex), the cost values of the vertices A, B, C, D, E, F are 2, 1, 4, 1, 4, 5, respectively. 2 6 4 A C E B D F 5 3 1 Your goal is to design an efficient algorithm that fills in the entire cost array (i.e., for all vertices). Give a linear-time algorithm that works for directed acyclic graphs. 5. (a) Simulate Dijkstra's algorithm on the following graph with vertices numbered 1 to 6. The edges are: 1: (6,2), (4,7) 2: (1, 3), (3,4) 3: (5,6) 4: (2,2), (3,5), (1,5), (5,1) 5: (4,4), (6,3) 6: (4,3) Here (3, 4) in vertex 2's adjacency list means that vertex 2 has a directed edge to vertex 3 with a weight of 4. Assuming that the source vertex in Dijkstra's algorithm is vertex 2, show the values of distance and predecessor for each vertex. Also draw the shortest paths tree (the tree of shortest paths to the vertices from the source vertex). (b) Find a minimum spanning tree for the graph shown below using Prim's algorithm and compute the weight of the resulting minimum spanning tree. Does this graph have a unique minimum spanning tree? 3 A B 6 5 3 4 2 1 2 C Ꭰ E F 4 5 5 6 4 5. 5 3 6 G H 3 I J
Related questions
Question
Please Answer all Parts of all Questions
![4. You are given a directed graph in which each vertex u Є V has an associated price pu, which
is a positive integer. Define the array cost as follows:
for each u Є V, cost [u] = price of the cheapest vertex reachable from u (including u itself).
For instance, in the graph below (with prices shown for each vertex), the cost values of the
vertices A, B, C, D, E, F are 2, 1, 4, 1, 4, 5, respectively.
2
6
4
A
C
E
B
D
F
5
3
1
Your goal is to design an efficient algorithm that fills in the entire cost array (i.e., for all
vertices). Give a linear-time algorithm that works for directed acyclic graphs.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F6f56d031-b647-4796-9490-6bff54b90583%2F48a1318d-9f1f-4b8c-8348-e72b5b1fa528%2Flrkicdp_processed.png&w=3840&q=75)
Transcribed Image Text:4. You are given a directed graph in which each vertex u Є V has an associated price pu, which
is a positive integer. Define the array cost as follows:
for each u Є V, cost [u] = price of the cheapest vertex reachable from u (including u itself).
For instance, in the graph below (with prices shown for each vertex), the cost values of the
vertices A, B, C, D, E, F are 2, 1, 4, 1, 4, 5, respectively.
2
6
4
A
C
E
B
D
F
5
3
1
Your goal is to design an efficient algorithm that fills in the entire cost array (i.e., for all
vertices). Give a linear-time algorithm that works for directed acyclic graphs.
Transcribed Image Text:5. (a) Simulate Dijkstra's algorithm on the following graph with vertices numbered 1 to 6. The
edges are:
1: (6,2), (4,7)
2: (1, 3), (3,4)
3: (5,6)
4: (2,2), (3,5), (1,5), (5,1)
5: (4,4), (6,3)
6: (4,3)
Here (3, 4) in vertex 2's adjacency list means that vertex 2 has a directed edge to vertex
3 with a weight of 4. Assuming that the source vertex in Dijkstra's algorithm is vertex
2, show the values of distance and predecessor for each vertex.
Also draw the shortest paths tree (the tree of shortest paths to the vertices from the
source vertex).
(b) Find a minimum spanning tree for the graph shown below using Prim's algorithm and
compute the weight of the resulting minimum spanning tree. Does this graph have a
unique minimum spanning tree?
3
A
B
6
5
3
4
2
1
2
C
Ꭰ
E
F
4
5
5
6
4
5.
5
3
6
G
H
3
I
J
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 2 steps
