Describe, in plain English, an algorithm that given a weighted, directed, acyclic graph G=(V,E,w) (with integer weights) and a vertex s in V calculates the length of the longest path from s to every other vertex v (if a vertex is unreachable from s, then the length of the longest path for that vertex should be infinity). Your algorithm should run in O( |V| + |E| ) time in total, assuming that G is implemented with an adjacency list, as usual. Explain why your algorithm has this running time.[Hint: you might want to consider a new graph G', more or less similar to G, and reduce the problem for G to a problem for G' that we have solved in the lectures]

The algorithm to solve this problem is a variation of the topological sort algorithm, which is used to find the shortest path in a directed acyclic graph (DAG). However, in this case, we want to find the longest path, so we will modify the algorithm accordingly.

Here are the steps of the algorithm:

1. Initialize a list or array dist[] such that dist[i] is set to negative infinity for all vertices except the starting vertex s. For the starting vertex s, dist[s] is set to 0.

2. Perform a topological sort on the graph. This can be done using depth-first search (DFS). Start DFS from the given vertex s. In DFS, maintain a stack. When a vertex has been visited and all its adjacent vertices have been visited, push the vertex into the stack.

3. Once the topological sort is complete, all vertices will be stored in the stack. The vertex that was pushed last into the stack would be the starting vertex s.

4. While the stack is not empty, for each vertex u popped from the stack, update dist[] for all adjacent vertices v of u, i.e., for every adjacent vertex v, if dist[v] < dist[u] + weight(u, v), then update dist[v] = dist[u] + weight(u, v).

5. After the above step, dist[v] for each vertex v will hold the length of the longest path from s to v.

The running time of this algorithm is O(|V| + |E|) because each vertex and each edge is visited only once. The topological sort takes O(|V| + |E|) time and the process of relaxing all the edges of every vertex also takes O(|V| + |E|) time. Therefore, the total time complexity of the algorithm is O(|V| + |E|).