0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.