Longest path in DAG or finding DAG diameter

Question

A directed acyclic graph (DAG), is a directed graph with no directed cycles.

That is, it consists of vertices and edges, with each edge directed from one vertex to another, such that there is no way to start at any vertex v and follow a consistently-directed sequence of edges that eventually loops back to v again.

we have several algorithms to finding shortest path from one vertex to another(Dijkstra algorithm and Bellman-ford algorithm) or such algorithms to find shortest path from every to vertices( floyd-Warshall algorithm and Johnson algorithm)

But which method could help us to find the maximum path between all two vertices and pick the maximum one as graph Diam.

here we have a DAG so there is no cycle with Positive edge weight to drop in infinite loop for finding longest path. and we could use many other features in DAG.

Is any polynomial time order algorithm for this problem....?

thanks

Answer 1

But which method could help us to find the maximum path between all two vertices and pick the maximum one as graph Diam.

That's not how the diameter is usually defined; it's rather the maximum distance, i.e. the length of the longest shortest path. As such, any general-purpose APSP algorithm helps you find the diameter of DAGs.

here we have a DAG so there is no cycle with Positive edge weight to drop in infinite loop for finding longest path.

Infinite loops are not the problem; finding longest paths is NP-hard in general graphs.

Is any polynomial time order algorithm for this problem....?

As explained on Wikipedia [1], the Longest Path problem can indeed be solved efficiently on DAGs by finding the shortest path in the graph obtained by multiplying all weights by $-1$.

---

1. Algorithms by R. Sedgewick and K. Wayne (2011)

Answer 2

It can be solved in $O( V + E)$

We initialize distances to all vertices as minus infinite and distance to source as 0, then we find a topological sorting of the graph. Topological Sorting of a graph represents a linear ordering of the graph (See below, figure (b) is a linear representation of figure (a) ). Once we have topological order (or linear representation), we one by one process all vertices in topological order. For every vertex being processed, we update distances of its adjacent using the distance of current vertex.

The following figure shows step by step process of finding the longest paths. source geeksforgeeks.

pseudocode:

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)

• look at Longest path in a directed acyclic graph (DAG) article to see the algorithm and elaboration.

• and look at geeksforgeeks article to see the C++ code.