OJ Board

Given a DAG (directed acyclic graph), a start and end vertex, enumerate all path lengths between them. What is the fastest algorithm? The best I've seen is to use matrix multiplication which is O(n^e(logn)) where e is the exponent for matrix multiplication. Is there a O(n^2 logn) solution? n is number of vertices. BFS seem to take O(n^3) times on this problem.

Note this is different from counting the number of paths between the two vertices, which can be done in O(E) time with topological sort.

bugzpodder wrote:Given a DAG (directed acyclic graph), a start and end vertex, enumerate all path lengths between them. What is the fastest algorithm?

I think DFS(depth first search) is the best, if you use adjacent list.

DFS won't even solve the problem in polynomial time (BFS will, however).