Given a Weighted Directed Acyclic Graph (DAG) and a source vertex s in it, find the longest distances from s to all other vertices in the given graph.
The longest path problem for a general graph is not as easy as the shortest path problem because the longest path problem doesn’t have optimal substructure property. In fact, the Longest Path problem is NP-Hard for a general graph. However, the longest path problem has a linear time solution for directed acyclic graphs. The idea is similar to linear time solution for shortest path in a directed acyclic graph., we use Tological Sorting.
We initialize distances to all vertices as minus infinite and distance to source as 0, then we find a topological sorting of the graph. Topological Sorting of a graph represents a linear ordering of the graph (See below, figure (b) is a linear representation of figure (a) ). Once we have topological order (or linear representation), we one by one process all vertices in topological order. For every vertex being processed, we update distances of its adjacent using distance of current vertex.
[ad type=”banner”]
Following figure shows step by step process of finding longest paths.
Following is complete algorithm for finding longest distances.
1) Initialize dist[] = {NINF, NINF, ….} and dist[s] = 0 where s is the source vertex. Here NINF means negative infinite.
2) Create a toplogical order of all vertices.
3) Do following for every vertex u in topological order.
………..Do following for every adjacent vertex v of u
………………if (dist[v] < dist[u] + weight(u, v))
………………………dist[v] = dist[u] + weight(u, v)
Following is C++ implementation of the above algorithm.
[pastacode lang=”cpp” manual=”%2F%2F%20A%20C%2B%2B%20program%20to%20find%20single%20source%20longest%20distances%20in%20a%20DAG%0A%23include%20%3Ciostream%3E%0A%23include%20%3Clist%3E%0A%23include%20%3Cstack%3E%0A%23include%20%3Climits.h%3E%0A%23define%20NINF%20INT_MIN%0Ausing%20namespace%20std%3B%0A%23inc%0A%2F%2F%20Graph%20is%20represented%20using%20adjacency%20list.%20Every%20node%20of%20adjacency%20list%0A%2F%2F%20contains%20vertex%20number%20of%20the%20vertex%20to%20which%20edge%20connects.%20It%20also%0A%2F%2F%20contains%20weight%20of%20the%20edge%0Aclass%20AdjListNode%0A%7B%0A%20%20%20%20int%20v%3B%0A%20%20%20%20int%20weight%3B%0Apublic%3A%0A%20%20%20%20AdjListNode(int%20_v%2C%20int%20_w)%20%20%7B%20v%20%3D%20_v%3B%20%20weight%20%3D%20_w%3B%7D%0A%20%20%20%20int%20getV()%20%20%20%20%20%20%20%7B%20%20return%20v%3B%20%20%7D%0A%20%20%20%20int%20getWeight()%20%20%7B%20%20return%20weight%3B%20%7D%0A%7D%3B%0A%20%0A%2F%2F%20Class%20to%20represent%20a%20graph%20using%20adjacency%20list%20representation%0Aclass%20Graph%0A%7B%0A%20%20%20%20int%20V%3B%20%20%20%20%2F%2F%20No.%20of%20vertices’%0A%20%0A%20%20%20%20%2F%2F%20Pointer%20to%20an%20array%20containing%20adjacency%20lists%0A%20%20%20%20list%3CAdjListNode%3E%20*adj%3B%0A%20%0A%20%20%20%20%2F%2F%20A%20function%20used%20by%20longestPath%0A%20%20%20%20void%20topologicalSortUtil(int%20v%2C%20bool%20visited%5B%5D%2C%20stack%3Cint%3E%20%26Stack)%3B%0Apublic%3A%0A%20%20%20%20Graph(int%20V)%3B%20%20%20%2F%2F%20Constructor%0A%20%0A%20%20%20%20%2F%2F%20function%20to%20add%20an%20edge%20to%20graph%0A%20%20%20%20void%20addEdge(int%20u%2C%20int%20v%2C%20int%20weight)%3B%0A%20%0A%20%20%20%20%2F%2F%20Finds%20longest%20distances%20from%20given%20source%20vertex%0A%20%20%20%20void%20longestPath(int%20s)%3B%0A%7D%3B%0A%20%0AGraph%3A%3AGraph(int%20V)%20%2F%2F%20Constructor%0A%7B%0A%20%20%20%20this-%3EV%20%3D%20V%3B%0A%20%20%20%20adj%20%3D%20new%20list%3CAdjListNode%3E%5BV%5D%3B%0A%7D%0A%20%0Avoid%20Graph%3A%3AaddEdge(int%20u%2C%20int%20v%2C%20int%20weight)%0A%7B%0A%20%20%20%20AdjListNode%20node(v%2C%20weight)%3B%0A%20%20%20%20adj%5Bu%5D.push_back(node)%3B%20%2F%2F%20Add%20v%20to%20u’s%20list%0A%7D%0A%20%0A%2F%2F%20A%20recursive%20function%20used%20by%20longestPath.%20See%20below%20link%20for%20details%0A%2F%2F%20http%3A%2F%2Fwww.geeksforgeeks.org%2Ftopological-sorting%2F%0Avoid%20Graph%3A%3AtopologicalSortUtil(int%20v%2C%20bool%20visited%5B%5D%2C%20stack%3Cint%3E%20%26Stack)%0A%7B%0A%20%20%20%20%2F%2F%20Mark%20the%20current%20node%20as%20visited%0A%20%20%20%20visited%5Bv%5D%20%3D%20true%3B%0A%20%0A%20%20%20%20%2F%2F%20Recur%20for%20all%20the%20vertices%20adjacent%20to%20this%20vertex%0A%20%20%20%20list%3CAdjListNode%3E%3A%3Aiterator%20i%3B%0A%20%20%20%20for%20(i%20%3D%20adj%5Bv%5D.begin()%3B%20i%20!%3D%20adj%5Bv%5D.end()%3B%20%2B%2Bi)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20AdjListNode%20node%20%3D%20*i%3B%0A%20%20%20%20%20%20%20%20if%20(!visited%5Bnode.getV()%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20topologicalSortUtil(node.getV()%2C%20visited%2C%20Stack)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Push%20current%20vertex%20to%20stack%20which%20stores%20topological%20sort%0A%20%20%20%20Stack.push(v)%3B%0A%7D%0A%20%0A%2F%2F%20The%20function%20to%20find%20longest%20distances%20from%20a%20given%20vertex.%20It%20uses%0A%2F%2F%20recursive%20topologicalSortUtil()%20to%20get%20topological%20sorting.%0Avoid%20Graph%3A%3AlongestPath(int%20s)%0A%7B%0A%20%20%20%20stack%3Cint%3E%20Stack%3B%0A%20%20%20%20int%20dist%5BV%5D%3B%0A%20%0A%20%20%20%20%2F%2F%20Mark%20all%20the%20vertices%20as%20not%20visited%0A%20%20%20%20bool%20*visited%20%3D%20new%20bool%5BV%5D%3B%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20V%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20visited%5Bi%5D%20%3D%20false%3B%0A%20%0A%20%20%20%20%2F%2F%20Call%20the%20recursive%20helper%20function%20to%20store%20Topological%20Sort%0A%20%20%20%20%2F%2F%20starting%20from%20all%20vertices%20one%20by%20one%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20V%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20if%20(visited%5Bi%5D%20%3D%3D%20false)%0A%20%20%20%20%20%20%20%20%20%20%20%20topologicalSortUtil(i%2C%20visited%2C%20Stack)%3B%0A%20%0A%20%20%20%20%2F%2F%20Initialize%20distances%20to%20all%20vertices%20as%20infinite%20and%20distance%0A%20%20%20%20%2F%2F%20to%20source%20as%200%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20V%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20dist%5Bi%5D%20%3D%20NINF%3B%0A%20%20%20%20dist%5Bs%5D%20%3D%200%3B%0A%20%0A%20%20%20%20%2F%2F%20Process%20vertices%20in%20topological%20order%0A%20%20%20%20while%20(Stack.empty()%20%3D%3D%20false)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Get%20the%20next%20vertex%20from%20topological%20order%0A%20%20%20%20%20%20%20%20int%20u%20%3D%20Stack.top()%3B%0A%20%20%20%20%20%20%20%20Stack.pop()%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Update%20distances%20of%20all%20adjacent%20vertices%0A%20%20%20%20%20%20%20%20list%3CAdjListNode%3E%3A%3Aiterator%20i%3B%0A%20%20%20%20%20%20%20%20if%20(dist%5Bu%5D%20!%3D%20NINF)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20for%20(i%20%3D%20adj%5Bu%5D.begin()%3B%20i%20!%3D%20adj%5Bu%5D.end()%3B%20%2B%2Bi)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(dist%5Bi-%3EgetV()%5D%20%3C%20dist%5Bu%5D%20%2B%20i-%3EgetWeight())%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20dist%5Bi-%3EgetV()%5D%20%3D%20dist%5Bu%5D%20%2B%20i-%3EgetWeight()%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Print%20the%20calculated%20longest%20distances%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20V%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20(dist%5Bi%5D%20%3D%3D%20NINF)%3F%20cout%20%3C%3C%20%22INF%20%22%3A%20cout%20%3C%3C%20dist%5Bi%5D%20%3C%3C%20%22%20%22%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20%2F%2F%20Create%20a%20graph%20given%20in%20the%20above%20diagram.%20%20Here%20vertex%20numbers%20are%0A%20%20%20%20%2F%2F%200%2C%201%2C%202%2C%203%2C%204%2C%205%20with%20following%20mappings%3A%0A%20%20%20%20%2F%2F%200%3Dr%2C%201%3Ds%2C%202%3Dt%2C%203%3Dx%2C%204%3Dy%2C%205%3Dz%0A%20%20%20%20Graph%20g(6)%3B%0A%20%20%20%20g.addEdge(0%2C%201%2C%205)%3B%0A%20%20%20%20g.addEdge(0%2C%202%2C%203)%3B%0A%20%20%20%20g.addEdge(1%2C%203%2C%206)%3B%0A%20%20%20%20g.addEdge(1%2C%202%2C%202)%3B%0A%20%20%20%20g.addEdge(2%2C%204%2C%204)%3B%0A%20%20%20%20g.addEdge(2%2C%205%2C%202)%3B%0A%20%20%20%20g.addEdge(2%2C%203%2C%207)%3B%0A%20%20%20%20g.addEdge(3%2C%205%2C%201)%3B%0A%20%20%20%20g.addEdge(3%2C%204%2C%20-1)%3B%0A%20%20%20%20g.addEdge(4%2C%205%2C%20-2)%3B%0A%20%0A%20%20%20%20int%20s%20%3D%201%3B%0A%20%20%20%20cout%20%3C%3C%20%22Following%20are%20longest%20distances%20from%20source%20vertex%20%22%20%3C%3C%20s%20%3C%3C%22%20%5Cn%22%3B%0A%20%20%20%20g.longestPath(s)%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D” message=”” highlight=”” provider=”manual”/]
Output:
Following are longest distances from source vertex 1
INF 0 2 9 8 10
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. Total adjacent vertices in a graph is O(E). So the inner loop runs O(V+E) times. Therefore, overall time complexity of this algorithm is O(V+E).
[ad type=”banner”]