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.

Question

Computers and Technology

Erik Mitchell

18 May, 19:09

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.

+1

Answers (1)

Know the Answer?

Stout · Answer 1

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)