Finding shortest and longest paths between two vertices in a DAG

Question Detail: 

Given an unweighted DAG (directed acyclic graph) $D = (V,A)$ and two vertices $s$ and $t$, is it possible to find the shortest and longest path from $s$ to $t$ in polynomial time? Path lengths are measured by the number of edges.

I am interested in finding the range of possible path lengths in polynomial time.

Ps., this question is a duplicate of the StackOverflow question Longest path in a DAG.

Asked By : robowolverine

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11295

Answered By : jmite

For the shortest path problem, if we do not care about weights, then breadth first search is a surefire way. Otherwise Dijkstra's algorithm works as long as there are no negative edges.

For longest path, you could always do Bellman-Ford on the graph with all edge weights negated. Recall that Bellman-Ford works as long as there are no negative weight cycles, and therefore works with any weights on a DAG.