// A C++ program to find single source longest distances // in a DAG #include    using namespace std; // Graph is represented using adjacency list. Every node of // adjacency list contains vertex number of the vertex to // which edge connects. It also contains weight of the edge class AdjListNode {  int v;  int weight; public:  AdjListNode(int _v int _w)  {  v = _v;  weight = _w;  }  int getV()  {  return v;  }  int getWeight()  {  return weight;  } }; // Graph class represents a directed graph using adjacency // list representation class Graph {  int V; // No. of vertices  // Pointer to an array containing adjacency lists  list<AdjListNode>* adj;  // This function uses DFS  void longestPathUtil(int vector<bool> & stack<int> &); public:  Graph(int); // Constructor  ~Graph(); // Destructor  // function to add an edge to graph  void addEdge(int int int);  void longestPath(int); }; Graph::Graph(int V) // Constructor {  this->V = V;  adj = new list<AdjListNode>[V]; } Graph::~Graph() // Destructor {  delete[] adj; } void Graph::addEdge(int u int v int weight) {  AdjListNode node(v weight);  adj[u].push_back(node); // Add v to u's list } // A recursive function used by longestPath. See below // link for details. // https://www.geeksforgeeks.org/dsa/topological-sorting/ void Graph::longestPathUtil(int v vector<bool> &visited  stack<int> &Stack) {  // Mark the current node as visited  visited[v] = true;  // Recur for all the vertices adjacent to this vertex  for (AdjListNode node : adj[v])  {  if (!visited[node.getV()])  longestPathUtil(node.getV() visited Stack);  }  // Push current vertex to stack which stores topological  // sort  Stack.push(v); } // The function do Topological Sort and finds longest // distances from given source vertex void Graph::longestPath(int s) {  // Initialize distances to all vertices as infinite and  // distance to source as 0  int dist[V];  for (int i = 0; i < V; i++)  dist[i] = INT_MAX;  dist[s] = 0;  stack<int> Stack;  // Mark all the vertices as not visited  vector<bool> visited(V false);  for (int i = 0; i < V; i++)  if (visited[i] == false)  longestPathUtil(i visited Stack);  // Process vertices in topological order  while (!Stack.empty())  {  // Get the next vertex from topological order  int u = Stack.top();  Stack.pop();  if (dist[u] != INT_MAX)  {  // Update distances of all adjacent vertices  // (edge from u -> v exists)  for (AdjListNode v : adj[u])  {  // consider negative weight of edges and  // find shortest path  if (dist[v.getV()] > dist[u] + v.getWeight() * -1)  dist[v.getV()] = dist[u] + v.getWeight() * -1;  }  }  }  // Print the calculated longest distances  for (int i = 0; i < V; i++)  {  if (dist[i] == INT_MAX)  cout << 'INT_MIN ';  else  cout << (dist[i] * -1) << ' ';  } } // Driver code int main() {  Graph g(6);  g.addEdge(0 1 5);  g.addEdge(0 2 3);  g.addEdge(1 3 6);  g.addEdge(1 2 2);  g.addEdge(2 4 4);  g.addEdge(2 5 2);  g.addEdge(2 3 7);  g.addEdge(3 5 1);  g.addEdge(3 4 -1);  g.addEdge(4 5 -2);  int s = 1;  cout << 'Following are longest distances from '  << 'source vertex ' << s << ' n';  g.longestPath(s);  return 0; } 

# A Python3 program to find single source  # longest distances in a DAG import sys def addEdge(u v w): global adj adj[u].append([v w]) # A recursive function used by longestPath.  # See below link for details. # https:#www.geeksforgeeks.org/topological-sorting/ def longestPathUtil(v): global visited adjStack visited[v] = 1 # Recur for all the vertices adjacent # to this vertex for node in adj[v]: if (not visited[node[0]]): longestPathUtil(node[0]) # Push current vertex to stack which  # stores topological sort Stack.append(v) # The function do Topological Sort and finds # longest distances from given source vertex def longestPath(s): # Initialize distances to all vertices  # as infinite and global visited Stack adjV dist = [sys.maxsize for i in range(V)] # for (i = 0 i < V i++) # dist[i] = INT_MAX dist[s] = 0 for i in range(V): if (visited[i] == 0): longestPathUtil(i) # print(Stack) while (len(Stack) > 0): # Get the next vertex from topological order u = Stack[-1] del Stack[-1] if (dist[u] != sys.maxsize): # Update distances of all adjacent vertices # (edge from u -> v exists) for v in adj[u]: # Consider negative weight of edges and # find shortest path if (dist[v[0]] > dist[u] + v[1] * -1): dist[v[0]] = dist[u] + v[1] * -1 # Print the calculated longest distances for i in range(V): if (dist[i] == sys.maxsize): print('INT_MIN ' end = ' ') else: print(dist[i] * (-1) end = ' ') # Driver code if __name__ == '__main__': V = 6 visited = [0 for i in range(7)] Stack = [] adj = [[] for i in range(7)] addEdge(0 1 5) addEdge(0 2 3) addEdge(1 3 6) addEdge(1 2 2) addEdge(2 4 4) addEdge(2 5 2) addEdge(2 3 7) addEdge(3 5 1) addEdge(3 4 -1) addEdge(4 5 -2) s = 1 print('Following are longest distances from source vertex' s) longestPath(s) # This code is contributed by mohit kumar 29 

// C# program to find single source longest distances // in a DAG using System; using System.Collections.Generic; // Graph is represented using adjacency list. Every node of // adjacency list contains vertex number of the vertex to // which edge connects. It also contains weight of the edge class AdjListNode {  private int v;  private int weight;  public AdjListNode(int _v int _w)  {  v = _v;  weight = _w;  }  public int getV() { return v; }  public int getWeight() { return weight; } } // Graph class represents a directed graph using adjacency // list representation class Graph {  private int V; // No. of vertices  // Pointer to an array containing adjacency lists  private List<AdjListNode>[] adj;  public Graph(int v) // Constructor  {  V = v;  adj = new List<AdjListNode>[ v ];  for (int i = 0; i < v; i++)  adj[i] = new List<AdjListNode>();  }  public void AddEdge(int u int v int weight)  {  AdjListNode node = new AdjListNode(v weight);  adj[u].Add(node); // Add v to u's list  }  // A recursive function used by longestPath. See below  // link for details.  // https://www.geeksforgeeks.org/dsa/topological-sorting/  private void LongestPathUtil(int v bool[] visited  Stack<int> stack)  {  // Mark the current node as visited  visited[v] = true;  // Recur for all the vertices adjacent to this  // vertex  foreach(AdjListNode node in adj[v])  {  if (!visited[node.getV()])  LongestPathUtil(node.getV() visited  stack);  }  // Push current vertex to stack which stores  // topological sort  stack.Push(v);  }  // The function do Topological Sort and finds longest  // distances from given source vertex  public void LongestPath(int s)  {    // Initialize distances to all vertices as infinite  // and distance to source as 0  int[] dist = new int[V];  for (int i = 0; i < V; i++)  dist[i] = Int32.MaxValue;  dist[s] = 0;  Stack<int> stack = new Stack<int>();  // Mark all the vertices as not visited  bool[] visited = new bool[V];  for (int i = 0; i < V; i++) {  if (visited[i] == false)  LongestPathUtil(i visited stack);  }  // Process vertices in topological order  while (stack.Count > 0) {  // Get the next vertex from topological order  int u = stack.Pop();  if (dist[u] != Int32.MaxValue) {  // Update distances of all adjacent vertices  // (edge from u -> v exists)  foreach(AdjListNode v in adj[u])  {  // consider negative weight of edges and  // find shortest path  if (dist[v.getV()]  > dist[u] + v.getWeight() * -1)  dist[v.getV()]  = dist[u] + v.getWeight() * -1;  }  }  }  // Print the calculated longest distances  for (int i = 0; i < V; i++) {  if (dist[i] == Int32.MaxValue)  Console.Write('INT_MIN ');  else  Console.Write('{0} ' dist[i] * -1);  }  Console.WriteLine();  } } public class GFG {  // Driver code  static void Main(string[] args)  {  Graph g = new Graph(6);  g.AddEdge(0 1 5);  g.AddEdge(0 2 3);  g.AddEdge(1 3 6);  g.AddEdge(1 2 2);  g.AddEdge(2 4 4);  g.AddEdge(2 5 2);  g.AddEdge(2 3 7);  g.AddEdge(3 5 1);  g.AddEdge(3 4 -1);  g.AddEdge(4 5 -2);  int s = 1;  Console.WriteLine(  'Following are longest distances from source vertex {0} '  s);  g.LongestPath(s);  } } // This code is contributed by cavi4762. 

// A Java program to find single source longest distances // in a DAG import java.util.*; // Graph is represented using adjacency list. Every // node of adjacency list contains vertex number of // the vertex to which edge connects. It also // contains weight of the edge class AdjListNode {  private int v;  private int weight;  AdjListNode(int _v int _w)  {  v = _v;  weight = _w;  }  int getV() { return v; }  int getWeight() { return weight; } } // Class to represent a graph using adjacency list // representation public class GFG {  int V; // No. of vertices'  // Pointer to an array containing adjacency lists  ArrayList<AdjListNode>[] adj;  @SuppressWarnings('unchecked')  GFG(int V) // Constructor  {  this.V = V;  adj = new ArrayList[V];  for (int i = 0; i < V; i++) {  adj[i] = new ArrayList<>();  }  }  void addEdge(int u int v int weight)  {  AdjListNode node = new AdjListNode(v weight);  adj[u].add(node); // Add v to u's list  }  // A recursive function used by longestPath. See  // below link for details https://  // www.geeksforgeeks.org/topological-sorting/  void topologicalSortUtil(int v boolean visited[]  Stack<Integer> stack)  {  // Mark the current node as visited  visited[v] = true;  // Recur for all the vertices adjacent to this  // vertex  for (int i = 0; i < adj[v].size(); i++) {  AdjListNode node = adj[v].get(i);  if (!visited[node.getV()])  topologicalSortUtil(node.getV() visited  stack);  }  // Push current vertex to stack which stores  // topological sort  stack.push(v);  }  // The function to find Smallest distances from a  // given vertex. It uses recursive  // topologicalSortUtil() to get topological sorting.  void longestPath(int s)  {  Stack<Integer> stack = new Stack<Integer>();  int dist[] = new int[V];  // Mark all the vertices as not visited  boolean visited[] = new boolean[V];  for (int i = 0; i < V; i++)  visited[i] = false;  // Call the recursive helper function to store  // Topological Sort starting from all vertices  // one by one  for (int i = 0; i < V; i++)  if (visited[i] == false)  topologicalSortUtil(i visited stack);  // Initialize distances to all vertices as  // infinite and distance to source as 0  for (int i = 0; i < V; i++)  dist[i] = Integer.MAX_VALUE;  dist[s] = 0;  // Process vertices in topological order  while (stack.isEmpty() == false) {  // Get the next vertex from topological  // order  int u = stack.peek();  stack.pop();  // Update distances of all adjacent vertices  if (dist[u] != Integer.MAX_VALUE) {  for (AdjListNode v : adj[u]) {  if (dist[v.getV()]  > dist[u] + v.getWeight() * -1)  dist[v.getV()]  = dist[u] + v.getWeight() * -1;  }  }  }  // Print the calculated longest distances  for (int i = 0; i < V; i++)  if (dist[i] == Integer.MAX_VALUE)  System.out.print('INF ');  else  System.out.print(dist[i] * -1 + ' ');  }  // Driver program to test above functions  public static void main(String args[])  {  // Create a graph given in the above diagram.  // Here vertex numbers are 0 1 2 3 4 5 with  // following mappings:  // 0=r 1=s 2=t 3=x 4=y 5=z  GFG g = new GFG(6);  g.addEdge(0 1 5);  g.addEdge(0 2 3);  g.addEdge(1 3 6);  g.addEdge(1 2 2);  g.addEdge(2 4 4);  g.addEdge(2 5 2);  g.addEdge(2 3 7);  g.addEdge(3 5 1);  g.addEdge(3 4 -1);  g.addEdge(4 5 -2);  int s = 1;  System.out.print(  'Following are longest distances from source vertex '  + s + ' n');  g.longestPath(s);  } } // This code is contributed by Prithi_Dey 

class AdjListNode {  constructor(v weight) {  this.v = v;  this.weight = weight;  }  getV() { return this.v; }  getWeight() { return this.weight; } } class GFG {  constructor(V) {  this.V = V;  this.adj = new Array(V);  for (let i = 0; i < V; i++) {  this.adj[i] = new Array();  }  }  addEdge(u v weight) {  let node = new AdjListNode(v weight);  this.adj[u].push(node);  }  topologicalSortUtil(v visited stack) {  visited[v] = true;  for (let i = 0; i < this.adj[v].length; i++) {  let node = this.adj[v][i];  if (!visited[node.getV()]) {  this.topologicalSortUtil(node.getV() visited stack);  }  }  stack.push(v);  }  longestPath(s) {  let stack = new Array();  let dist = new Array(this.V);  let visited = new Array(this.V);  for (let i = 0; i < this.V; i++) {  visited[i] = false;  }  for (let i = 0; i < this.V; i++) {  if (!visited[i]) {  this.topologicalSortUtil(i visited stack);  }  }  for (let i = 0; i < this.V; i++) {  dist[i] = Number.MAX_SAFE_INTEGER;  }      dist[s] = 0;  let u = stack.pop();  while (stack.length > 0) {  u = stack.pop();  if (dist[u] !== Number.MAX_SAFE_INTEGER) {  for (let v of this.adj[u]) {  if (dist[v.getV()] > dist[u] + v.getWeight() * -1) {  dist[v.getV()] = dist[u] + v.getWeight() * -1;  }  }  } }      for (let i = 0; i < this.V; i++) {  if (dist[i] === Number.MAX_SAFE_INTEGER) {  console.log('INF');  }  else {  console.log(dist[i] * -1);  }  }  } } let g = new GFG(6); g.addEdge(0 1 5); g.addEdge(0 2 3); g.addEdge(1 3 6); g.addEdge(1 2 2); g.addEdge(2 4 4); g.addEdge(2 5 2); g.addEdge(2 3 7); g.addEdge(3 5 1); g.addEdge(3 4 -1); g.addEdge(4 5 -2); console.log('Longest distances from the vertex 1 : '); g.longestPath(1); //this code is contributed by devendra