This is a problem of topological sorting.

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 ...read more

First we create an integer array ‘maxDistances’ of size ‘N’ and fill it with -1, maxDistances[i] will give the maximum distance of node ‘i’ from the given source node. We will then recursiv...read more

Topological Sorting of  DAG is a linear ordering of vertices such that for every directed edge from vertex ‘u’ to vertex ‘v’, vertex ‘u’ comes before ‘v’ in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG.   We can find topological sorting of any DAG using this algorithm.

We can solve this problem of finding the longest paths in a directed graph in linear time if we process nodes in topological order, and update distances of their adjacent.

Note that if the graph is not DAG, then this problem is an NP-hard problem.

Algorithm

• Create an adjacency list ‘adj’, such that adj[i][j] is a list of two integers [v, w], representing that that ‘jth’ adjacent node of ‘i’ is node ‘v’ and the weight of directed edge i -> v is ‘w’.
• Create a list of integers 'maxDistances' of size 'N' and fill it with -1.
• Create a list ‘order’ of size ‘N’ that will have topological sorting of graph, Topological sorting can be found using this algorithm.
• Assign ‘maxDistances[Src]’ := 0.
• Run a loop where ‘i’ ranges from to ‘N’-1, and for each ‘i’ do following -:
  • Initialize an integer variable current := order[i].
  • If  ‘maxDistances[current] == -1,   then continue because this node is not reachable from the source node.
  • Visit over all the adjacent nodes 'neighbor’ of node current, and update their distances maxDistances[neighbor] := max( maxDistances[neighbors], maxDistances[current] + weight of directed edge between node at current and neighbor)
• Return ‘maxDistances’.

O(N + E),  where  ‘N’ is the number of nodes in the given directed graph and E is the number of edges.

The space used by the adjacency list ‘adj’ is of the order of O(N + E) and the space used by array ‘maxDistances’ is of order O(N). Thus, the final space complexity will be O(N+E) + O(N) = O(N+E).

O(N+E), where  ‘N’ is the number of nodes in the given directed graph and E is the number of edges.

Topological sorting will take the time of the order of O(N+E), and also we iterate over neighbors of all the nodes which also takes time O(N + E). Thus, the final complexity will be O(N+E) + O(N+E) = O(N+E).

/*
    Time Complexity : O(N+E)
    Space Complexity : O(N+E)

    Where 'N' is the number of nodes in the given directed graph 
    and 'E' is the number of edges.
*/

import java.util.ArrayList;
import java.util.Stack;

public class Solution {
	private static void topologicalSortUtil(int current, ArrayList>> adj,
			ArrayList visited, Stack stk) {
		/*
		 * Parameters of this function are -: 'current': current node. 'adj': adjacency
		 * list of given directed graph. 'visited': Booleanean array to track whether
		 * node is visited or not. 'stk': stack that will keep topological order of
		 * nodes.
		 */

		// Mark current node visited
		visited.set(current, true);

		// Iterating over adjacent vertices.
		for (int i = 0; i < adj.get(current).size(); i++) {
			if (visited.get(adj.get(current).get(i).get(0)) == false) {
				topologicalSortUtil(adj.get(current).get(i).get(0), adj, visited, stk);
			}
		}

		// Push vertex in stack after pushing all its adjacent (and their adjacent and
		// so on) verices.
		stk.push(current);
	}

	private static ArrayList topologicalSort(ArrayList>> adj) {
		// Number of nodes in a graph.
		int n = adj.size();

		ArrayList visited = new ArrayList();
		for (int i = 0; i < n; i++) {
			visited.add(false);
		}
		Stack stk = new Stack();

		// Recursively finding topological sorting.
		for (int i = 0; i < n; i++) {
			if (!visited.get(i)) {
				topologicalSortUtil(i, adj, visited, stk);
			}
		}

		// List 'result' will keep topological sort of given graph.
		ArrayList result = new ArrayList();
		while (!stk.isEmpty()) {
			result.add(stk.peek());
			stk.pop();
		}

		return result;
	}

	public static ArrayList findMaxDistances(int n, int src, ArrayList> edges) {

		// Create Adjacency List.
		ArrayList>> adj = new ArrayList>>();

		for (int i = 0; i < n; i++) {
			adj.add(new ArrayList>());
		}

		for (int i = 0; i < edges.size(); i++) {
			ArrayList temp = new ArrayList();
			temp.add(edges.get(i).get(1));
			temp.add(edges.get(i).get(2));
			adj.get(edges.get(i).get(0)).add(temp);
		}

		// Find topological sorting.
		ArrayList order = topologicalSort(adj);

		// Create a list 'maxDistances' of size 'N'and fill it with -1.
		ArrayList maxDistances = new ArrayList();
		for (int i = 0; i < n; i++) {
			maxDistances.add(-1);
		}

		maxDistances.set(src, 0);

		// Find maximum distances of each node from 'Src'.
		for (int i = 0; i < n; i++) {
			int current = order.get(i);
		
			if (maxDistances.get(current) == -1) {
				// Skip this node as it is not reachable from source node.
				continue;
			}
			for (int j = 0; j < adj.get(current).size(); j++) {
				int neighbor = adj.get(current).get(j).get(0);

				maxDistances.set(neighbor, Math.max(maxDistances.get(neighbor),
						maxDistances.get(current) + adj.get(current).get(j).get(1)));
			}
		}

		return maxDistances;
	}
}

/*
    Time Complexity : O(N+E)
    Space Complexity : O(N+E)

    Where ‘N’ is the number of nodes in the given directed graph 
    and 'E' is the number of edges.
*/

#include 

void topologicalSortUtil(int current, vector>> &adj, vector &visited, stack &stk) {
    /*
        Parameters of this function are -:
        'current': current node.
        'adj': adjacency list of given directed graph.
        'visited': boolean array to track whether node is visited or not.
        'stk': stack that will keep topological order of nodes.  
    */

    // Mark current node visited
    visited[current] = true;  

    // Iterating over adjacent vertices.
    for(int i = 0; i < adj[current].size(); i++) {
        if(visited[adj[current][i][0]] == false) {
            topologicalSortUtil(adj[current][i][0], adj, visited, stk);
        }
    }

    // Push vertex in stack after pushing all its adjacent (and their adjacent and so on) verices.
    stk.push(current);
}

vector topologicalSort(vector>> &adj) {
    // Number of nodes in a graph.
    int n = adj.size();

    vector visited(n);
    stack stk;

    // Recursively finding topological sorting.
    for(int i = 0; i < n; i++) {
        if(!visited[i]) {
            topologicalSortUtil(i, adj, visited, stk);
        }
    }

    // List 'result' will keep topological sort of given graph.
    vector result;
    while(!stk.empty()) {
        result.push_back(stk.top());
        stk.pop();
    }

    return result;
}

vector findMaxDistances(int n, int src, vector> &edges) {
    // Create Adjacency List.
    vector>> adj(n);
    for(int i = 0; i < edges.size(); i++) {
        adj[edges[i][0]].push_back(vector({edges[i][1], edges[i][2]}));
    }

    // Find topological sorting.
    vector order = topologicalSort(adj);

    // Create a list 'maxDistances' of size 'N' and fill it with negative infinity.  
    vector maxDistances(n, -1);
    maxDistances[src] = 0;

    // Find maximum distances of each node from 'Src'.
    for(int i = 0; i < n; i++) {
        int current = order[i];
        if(maxDistances[current] == -1) {
            // Skip this node as it is not reachable from source node.
            continue;
        }
        for(int j = 0; j < adj[current].size(); j++) {
            int neighbor = adj[current][j][0];
            maxDistances[neighbor] = max(maxDistances[neighbor], maxDistances[current] + adj[current][j][1]);
        }
    }

    return maxDistances;
}

'''
    Time Complexity : O(N+E)
    Space Complexity : O(N+E)

    Where ‘N’ is the number of nodes in the given directed graph 
    and 'E' is the number of edges.
'''


def topologicalSortUtil(current, adj, visited, stk):
    '''
        Parameters of this function are -:
        'current': current node.
        'adj': adjacency list of given directed graph.
        'visited': boolean array to track whether node is visited or not.
        'stk': stack that will keep topological order of nodes.
    '''
    # Mark current node visited
    visited[current] = True

    # Iterating over adjacent vertices.
    for i in range(len(adj[current])):
        if(visited[adj[current][i][0]] == False):
            topologicalSortUtil(adj[current][i][0], adj, visited, stk)

    # Push vertex in stack after pushing all its adjacent (and their adjacent and so on) verices.
    stk.append(current)


def topologicalSort(adj):
    # Number of nodes in a graph.
    n = len(adj)

    visited = [False for i in range(n)]
    stk = []

    # Recursively finding topological sorting.
    for i in range(n):
        if(visited[i] == False):
            topologicalSortUtil(i, adj, visited, stk)

    # List 'result' will keep topological sort of given graph.
    result = []
    while(len(stk) > 0):
        result.append(stk[-1])
        stk.pop()

    return result


def findMaxDistances(n, src, edges):
    # Create Adjacency List.
    adj = [[] for i in range(n)]

    for i in range(len(edges)):
        adj[edges[i][0]].append([edges[i][1], edges[i][2]])

    # Find topological sorting.
    order = topologicalSort(adj)

    # Create a list 'maxDistances' of size 'N' and fill it with negative infinity.
    maxDistances = [-1 for i in range(n)]
    maxDistances[src] = 0

    # Find maximum distances of each node from 'Src'.
    for i in range(n):
        current = order[i]
        if(maxDistances[current] == -1):
            # Skip this node as it is not reachable from source node.
            continue
        for j in range(len(adj[current])):
            neighbor = adj[current][j][0]
            maxDistances[neighbor] = max(
                maxDistances[neighbor], maxDistances[current] + adj[current][j][1])

    return maxDistances