# 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
13. {
14.         int v;
15.         int weight;
16.     public:
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
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;
56. }
57.
58. void Graph::addEdge(int u, int v, int weight)
59. {
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
74.     {
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
117.         if (dist[u] != NINF)
118.         {
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);
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)