# 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)