2 B 7 12 3 a) For the graph above, classify all edges as tree edges,...

 

Transcribed Image Text:

2 B 7 12 3 a) For the graph above, classify all edges as tree edges, forward edges, backward edges or cross edges. b) Using the most appropriate algorithm, find the shortest path from A to all other vertices. c) Using the classification from (a), remove all backward edges from the graph. Now use the Shortest- path-DAG algorithm to find the shortest path from A to all other vertices. d) The Shortest-path-DAG algorithm can be adapted/modified to find the longest path in a DAG by appropriately modifying the initialization and relaxation steps. What should d[v] be initialized to and how is the Relax(u,v,w) function modified? e) Using your algorithm from (d), find the longest path in the DAG of (c) from A to all other vertices. 2 B 7 12 3 a) For the graph above, classify all edges as tree edges, forward edges, backward edges or cross edges. b) Using the most appropriate algorithm, find the shortest path from A to all other vertices. c) Using the classification from (a), remove all backward edges from the graph. Now use the Shortest- path-DAG algorithm to find the shortest path from A to all other vertices. d) The Shortest-path-DAG algorithm can be adapted/modified to find the longest path in a DAG by appropriately modifying the initialization and relaxation steps. What should d[v] be initialized to and how is the Relax(u,v,w) function modified? e) Using your algorithm from (d), find the longest path in the DAG of (c) from A to all other vertices.