There's a very simple algorithm to solve the recurrence described in David's answer: We can use depth-first search with memoization to ensure that at every time all the subproblems that we need to solve the result for the current node are already known. This implicitly results in the topological order we need:
for all nodes x:
dis[x] = UNKNOWN
def dfs(x):
if x == goal: return 0
if dis[x] != UNKNOWN: return x
dis[x] = infinity
for all edges (x,y) with weight w:
dis[x] = min(dis[x], w + dfs(y))
return dis[x]
The result is just dfs(root)
For the case where you want to find a shortest path with no prefix ever exceeding weight k, you can use a reverse DFS from the goal:
for all nodes x:
dis[x] = UNKNOWN
def rdfs(x):
if x == root: return 0
if dis[x] != UNKNOWN: return x
dis[x] = infinity
for all edges (y,x) with weight w:
dis[x] = min(dis[x], w + rdfs(y))
if dis[x] > k:
dis[x] = infinity
return dis[x]
The solution is rdfs(goal)
.