Question

(Q4 - 30 pts: 15, 15) a) Give an O (n) time algorithm for finding the longest (simple) path in a tree on n vertices. Prove the correctness of your algorithm. Give a polynomial time algorithm for finding the longest (simple) path in a graph whose blocks have size bounded by a constant. Prove the correctness of your algorithm. b)

Answer 1

a)

b)

We change weight of every edge of given graph to its negation and initialize distances to all vertices as infinite and distance to source as 0, then we find a topological sorting of the graph which represents a linear ordering of the graph. When we consider a vertex u in topological order, it is guaranteed that we have considered every incoming edge to it. i.e. We have already found shortest path to that vertex and we can use that info to update shorter path of all its adjacent vertices. Once we have topological order, we one by one process all vertices in topological order. For every vertex being processed, we update distances of its adjacent vertex using shortest distance of current vertex from source vertex and its edge weight. i.e.

for every adjacent vertex v of every vertex u in topological order
    if (dist[v] > dist[u] + weight(u, v))
    dist[v] = dist[u] + weight(u, v)

Once we have found all shortest paths from the source vertex, longest paths will be just negation of shortest paths.

Time Complexity: Time complexity of topological sorting is O(V + E). After finding topological order, the algorithm process all vertices and for every vertex, it runs a loop for all adjacent vertices. As total adjacent vertices in a graph is O(E), the inner loop runs O(V + E) times. Therefore, overall time complexity of this algorithm is O(V + E).