2. Define the "incoming length" of a vertex v, in a weighted directed acyclic graph, to be the length of the longest path that ends at v, regardless of the starting point of the path. The longest path algorithm that we described in the lecture doesn't find this number. Instead, it has a specified starting vertex s, and finds the length of the longest path from s to v. (163 students): Describe how to modify G to make a graph G', with the following property: if the longest path algorithm from the lecture is run on G' (with an appropriate choice of the starting vertex s), then for every vertex v in G, the path length from s to v in G' found by the longest path algorithm will equal the incoming length to v in G. Your modified graph must be acyclic (assuming that G is acyclic). (265 students): Describe how to modify the longest path algorithm, so that if your modified algorithm is run on the original graph G, it produces the incoming lengths for each vertex in G. Your description may either be in English or pseudocode. = L empty dictionary for each vertex v in topological order: if v is the starting vertex: L[v] = 0 else: L[v] max L[u] + length(u + v) edge uv = This computes longest path distances from start to all other vertices in linear time Topological ordering implies that all predecessor vertices u already have the correct distance by the time we need them in the calculation for the distance for v Change max to min in last line to get shortest path distances 2. Define the "incoming length" of a vertex v, in a weighted directed acyclic graph, to be the length of the longest path that ends at v, regardless of the starting point of the path. The longest path algorithm that we described in the lecture doesn't find this number. Instead, it has a specified starting vertex s, and finds the length of the longest path from s to v. (163 students): Describe how to modify G to make a graph G', with the following property: if the longest path algorithm from the lecture is run on G' (with an appropriate choice of the starting vertex s), then for every vertex v in G, the path length from s to v in G' found by the longest path algorithm will equal the incoming length to v in G. Your modified graph must be acyclic (assuming that G is acyclic). (265 students): Describe how to modify the longest path algorithm, so that if your modified algorithm is run on the original graph G, it produces the incoming lengths for each vertex in G. Your description may either be in English or pseudocode. = L empty dictionary for each vertex v in topological order: if v is the starting vertex: L[v] = 0 else: L[v] max L[u] + length(u + v) edge uv = This computes longest path distances from start to all other vertices in linear time Topological ordering implies that all predecessor vertices u already have the correct distance by the time we need them in the calculation for the distance for v Change max to min in last line to get shortest path distances