Variation on longest path in a DAG Consider a directed acyclic graph with $n$ nodes and $m$ edges. Each edge is assigned a positive weight. There is a start node $s$ and an end node $e$. We want to find the path from $s$ to $e$ that has the maximum number of nodes such that


  
  the total distance is less than some constant $d$, and
  starting from $s$, each node in the path is closer than the previous one to the node $e$. (As in, when you traverse the path you are getting closer to your destination $e$ in terms of the edge weight of the remaining path.)
  


Does a polynomial time algorithm already exist for this problem? Is there a formal name for this problem?
You could solve it using a dynamic programming approach:

First lay out vertices in a topological order like $v_1, v_2, ..., v_n$. If start and end vertices are  $s=v_a$ and $e=v_b$, you could get rid of all vertices after $v_b$ and before $v_a$. So let's assume $s=v_1$ and $e=v_n$. Next, define $L_{i,j,p}$ to be the shortest path between $v_i$ and $v_j$ which has $p$ nodes. In other words, among paths between $v_i, v_j$ which have $p$ nodes, it's the length of shortest one. Assume $w_{i,j}$ is the weight between $v_i, v_j$, and it is infinity if there is no edge. Now


Set $L_{i,i,1}=0$.
For $p&gt;1$ we have $L_{i,j,p} = min_k \{L_{i,k,p-1}+w_{k,j} \}$, where  $i\le k&lt;j$.


Now the final answer is $max\{k\}$ for all $k$s that we have $L_{1,n,k}&lt;d$. The table (actually half of it need to be filled, because $i&lt;j$) has $n^3$ elements, and for each element $O(n)$ time it takes to be computed. So the time complexity will be $O(n^4)$, but guess tighter bounds could be achieved. 

UPDATE: As Neals pointed out in the comments an $O(n^2 m)$ bound is achievable. Also the algorithm can be thought of as a LDP algorithm running on transformed graph $G'$: make $n$ copies of the original graph $G$ and for each edge $e=(v,w)$ in $G$ connect the $i$th copy of $v$ and $(i+1)$th copy of $w$, for $1 \le i &lt; n$.