I came across this problem recently and I wanted to know whether it was a well known NP-complete problem. I checked the library but could not find anything that matched exactly.
Given a directed weighted graph G. Find the minimal weight path of length 'n' in the graph. Which is without setting any specific start node or end node.
This is not my field, so you will pardon me if the solution is trivial.
The shortest (in terms of weight) path, constrained to have exactly n (or at most n) edges, can be found in polynomial time. For instance, given your graph $G=(V,E)$ make an expanded graph $H$ that has as its vertices the pairs $(v,i)$ where $v\in G$ and $0\le i\le n-1$. Draw an edge in $H$ from $(v,i)$ to $(w,i+1)$ whenever $G$ has an edge from $v$ to $w$, with the same weight. Then the shortest $n$-edge path in $G$ from $v$ to $w$ is the same as the shortest path in $H$ from $(v,0)$ to $(w,n)$. To look for paths in $G$ that are at most $n$ edges long, add to $H$ edges of weight zero from $(v,i)$ to $(v,i+1)$.
However, these paths allow repeated vertices and edges. If repetitions are disallowed, and $G$ has $n+1$ vertices, then the shortest length-$n$ path is just a Traveling salesman path, so of course it's NP-complete.
The problem of finding the longest path in a graph is NP-complete. (See http://en.wikipedia.org/wiki/Longest_path_problem.) It follows that the problem of determining whether there exists a path of length $k$ is NP-hard (since otherwise you could check all lengths $k$). But then give a huge weight to all non-edges, and your problem is seen to be NP-hard too.
This is not even in NP! The input is n, which is of length log(n). But a certificate is of length n, which is exponential compared to log(n). So you can't verify a solution in polynomial time and so it's not in NP.
