C++ Program to Find the Longest Path in a Directed Acyclic Graph

«
»
This is a C++ Program to find longest path in DAG. 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. 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) Here is source code of the C++ Program to Find the Longest Path in a DAG. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.
  1. // A C++ program to find single source longest distances in a DAG
  2. #include <iostream>
  3. #include <list>
  4. #include <stack>
  5. #include <limits.h>
  6. #define NINF INT_MIN
  7. using namespace std;
  8.  
  9. // Graph is represented using adjacency list. Every node of adjacency list
  10. // contains vertex number of the vertex to which edge connects. It also
  11. // contains weight of the edge
  12. class AdjListNode
  13. {
  14.         int v;
  15.         int weight;
  16.     public:
  17.         AdjListNode(int _v, int _w)
  18.         {
  19.             v = _v;
  20.             weight = _w;
  21.         }
  22.         int getV()
  23.         {
  24.             return v;
  25.         }
  26.         int getWeight()
  27.         {
  28.             return weight;
  29.         }
  30. };
  31.  
  32. // Class to represent a graph using adjacency list representation
  33. class Graph
  34. {
  35.         int V; // No. of vertices’
  36.  
  37.         // Pointer to an array containing adjacency lists
  38.         list<AdjListNode> *adj;
  39.  
  40.         // A function used by longestPath
  41.         void topologicalSortUtil(int v, bool visited[], stack<int> &Stack);
  42.     public:
  43.         Graph(int V); // Constructor
  44.  
  45.         // function to add an edge to graph
  46.         void addEdge(int u, int v, int weight);
  47.  
  48.         // Finds longest distances from given source vertex
  49.         void longestPath(int s);
  50. };
  51.  
  52. Graph::Graph(int V) // Constructor
  53. {
  54.     this->V = V;
  55.     adj = new list<AdjListNode> [V];
  56. }
  57.  
  58. void Graph::addEdge(int u, int v, int weight)
  59. {
  60.     AdjListNode node(v, weight);
  61.     adj[u].push_back(node); // Add v to u’s list
  62. }
  63.  
  64. // A recursive function used by longestPath. See below link for details
  65. // http://www.geeksforgeeks.org/topological-sorting/
  66. void Graph::topologicalSortUtil(int v, bool visited[], stack<int> &Stack)
  67. {
  68.     // Mark the current node as visited
  69.     visited[v] = true;
  70.  
  71.     // Recur for all the vertices adjacent to this vertex
  72.     list<AdjListNode>::iterator i;
  73.     for (i = adj[v].begin(); i != adj[v].end(); ++i)
  74.     {
  75.         AdjListNode node = *i;
  76.         if (!visited[node.getV()])
  77.             topologicalSortUtil(node.getV(), visited, Stack);
  78.     }
  79.  
  80.     // Push current vertex to stack which stores topological sort
  81.     Stack.push(v);
  82. }
  83.  
  84. // The function to find longest distances from a given vertex. It uses
  85. // recursive topologicalSortUtil() to get topological sorting.
  86. void Graph::longestPath(int s)
  87. {
  88.     stack<int> Stack;
  89.     int dist[V];
  90.  
  91.     // Mark all the vertices as not visited
  92.     bool *visited = new bool[V];
  93.     for (int i = 0; i < V; i++)
  94.         visited[i] = false;
  95.  
  96.     // Call the recursive helper function to store Topological Sort
  97.     // starting from all vertices one by one
  98.     for (int i = 0; i < V; i++)
  99.         if (visited[i] == false)
  100.             topologicalSortUtil(i, visited, Stack);
  101.  
  102.     // Initialize distances to all vertices as infinite and distance
  103.     // to source as 0
  104.     for (int i = 0; i < V; i++)
  105.         dist[i] = NINF;
  106.     dist[s] = 0;
  107.  
  108.     // Process vertices in topological order
  109.     while (Stack.empty() == false)
  110.     {
  111.         // Get the next vertex from topological order
  112.         int u = Stack.top();
  113.         Stack.pop();
  114.  
  115.         // Update distances of all adjacent vertices
  116.         list<AdjListNode>::iterator i;
  117.         if (dist[u] != NINF)
  118.         {
  119.             for (i = adj[u].begin(); i != adj[u].end(); ++i)
  120.                 if (dist[i->getV()] < dist[u] + i->getWeight())
  121.                     dist[i->getV()] = dist[u] + i->getWeight();
  122.         }
  123.     }
  124.  
  125.     // Print the calculated longest distances
  126.     for (int i = 0; i < V; i++)
  127.         (dist[i] == NINF) ? cout << "INF " : cout << dist[i] << " ";
  128. }
  129.  
  130. // Driver program to test above functions
  131. int main()
  132. {
  133.     // Create a graph given in the above diagram.  Here vertex numbers are
  134.     // 0, 1, 2, 3, 4, 5 with following mappings:
  135.     // 0=r, 1=s, 2=t, 3=x, 4=y, 5=z
  136.     Graph g(6);
  137.     g.addEdge(0, 1, 5);
  138.     g.addEdge(0, 2, 3);
  139.     g.addEdge(1, 3, 6);
  140.     g.addEdge(1, 2, 2);
  141.     g.addEdge(2, 4, 4);
  142.     g.addEdge(2, 5, 2);
  143.     g.addEdge(2, 3, 7);
  144.     g.addEdge(3, 5, 1);
  145.     g.addEdge(3, 4, -1);
  146.     g.addEdge(4, 5, -2);
  147.  
  148.     int s = 1;
  149.     cout << "Following are longest distances from source vertex " << s << " \n";
  150.     g.longestPath(s);
  151.  
  152.     return 0;
  153. }

Output:

$ g++ LongestPathDAG.cpp
$ a.out
 
Following are longest distances from source vertex 1 
INF 0 2 9 8 10 
------------------
(program exited with code: 0)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.