Question

For each vertex v of the DAG, in the topological ordering, compute the length of the longest path ending at v by looking at its incoming neighbors and adding one to the maximum length recorded for those neighbors. If v has no incoming neighbors, set the length of the longest path ending at v to zero. In either case, record this number so that later steps of the algorithm can access it.

Answer 1

Answer:

Following are the step by step algorithms is explain below.

Explanation:

Following are the algorithm for searching shortest distances.

• Firstly, Initialize the array variable distance[] = {INF, INF, ….} as well as distance[s] = 0 in which the variable 's' is the beginning vertex

• Then, you have to develop a topological order of the following vertices.

• So, Do in the following for mostly vertex that is the variable 'u' in the topological order.

          Do on the following for mostly contiguous vertex that is 'v' of 'u'

                         if (dist[v] > dist[u] + weight(u, v))

                               dist[v] = dist[u] + weight(u, v)